Java模擬棧和隊列數據結構的基本示例講解

棧和隊列：
一般是作為程序員的工具，用於輔助構思算法，生命週期較短，運行時才被創建；
訪問受限，在特定時刻，只有一個數據可被讀取或刪除；
是一種抽象的結構，內部的實現機制，對用戶不可見，比如用數組、鍊錶來實現棧。

模擬棧結構
同時，只允許一個數據被訪問，後進先出對於入棧和出棧的時間複雜度都為O(1),即不依賴棧內數據項的個數，操作比較快例，使用數組作為棧的存儲結構

public class StackS<T> { private int max; private T[] ary; private int top; //指針，指向棧頂元素的下標public StackS(int size) { this.max = size; ary = (T[]) new Object[max]; top = -1; } // 入棧public void push(T data) { if (!isFull()) ary[++top] = data; } // 出棧public T pop() { if (isEmpty()) { return null; } return ary[top--]; } // 查看棧頂public T peek() { return ary[top]; } //棧是否為空public boolean isEmpty() { return top == -1; } //棧是否滿public boolean isFull() { return top == max - 1; } //size public int size() { return top + 1; } public static void main(String[] args) { StackS<Integer> stack = new StackS<Integer>(3); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } System.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } } }

上面的例子，有一個maxSize的規定，因為數組是要規定大小的，若想無限制，可以使用其他結構來做存儲，當然也可以new一個新的長度的數組。
例，使用LinkedList存儲來實現棧

public class StackSS<T> { private LinkedList<T> datas; public StackSS() { datas = new LinkedList<T>(); } // 入棧public void push(T data) { datas.addLast(data); } // 出棧public T pop() { return datas.removeLast(); } // 查看棧頂public T peek() { return datas.getLast(); } //棧是否為空public boolean isEmpty() { return datas.isEmpty(); } //size public int size() { return datas.size(); } public static void main(String[] args) { StackS<Integer> stack = new StackS<Integer>(3); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } System.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } } }

例，單詞逆序，使用Statck結構

public class WordReverse { public static void main(String[] args) { reverse("株式會社"); } static void reverse(String word) { if (word == null) return; StackSS<Character> stack = new StackSS<Character>(); char[] charArray = word.toCharArray(); int len = charArray.length; for (int i = 0; i <len; i++ ) { stack.push(charArray[i]); } StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { sb.append(stack.pop()); } System.out.println("反轉後：" + sb.toString()); } }

列印:

反轉後：社會式株

模擬隊列(一般隊列、雙端隊列、優先級隊列)
隊列：
先進先出，處理類似排隊的問題，先排的，先處理，後排的等前面的處理完了，再處理對於插入和移除操作的時間複雜度都為O(1)，從後面插入，從前面移除雙端隊列：
即在隊列兩端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight
含有棧和隊列的功能，如去掉insertLeft、removeLeft，那就跟棧一樣了；如去掉insertLeft、removeRight，那就跟隊列一樣了一般使用頻率較低，時間複雜度O(1)
優先級隊列：
內部維護一個按優先級排序的序列。插入時需要比較查找插入的位置，時間複雜度O(N)， 刪除O(1)

 /* * 隊列先進先出，一個指針指示插入的位置，一個指針指示取出數據項的位置*/ public class QueueQ<T> { private int max; private T[] ary; private int front; //隊頭指針指示取出數據項的位置private int rear; //隊尾指針指示插入的位置private int nItems; //實際數據項個數public QueueQ(int size) { this.max = size; ary = (T[]) new Object[max]; front = 0; rear = -1; nItems = 0; } //插入隊尾public void insert(T t) { if (rear == max - 1) {//已到實際隊尾，從頭開始rear = -1; } ary[++rear] = t; nItems++; } //移除隊頭public T remove() { T temp = ary[front++]; if (front == max) {//列隊到尾了，從頭開始front = 0; } nItems--; return temp; } //查看隊頭public T peek() { return ary[front]; } public boolean isEmpty() { return nItems == 0; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQ<Integer> queue = new QueueQ<Integer>(3); for (int i = 0; i < 5; i++) { queue.insert(i); System.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { Integer peek = queue.peek(); System.out.println("peek:" + peek); System.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { Integer remove = queue.remove(); System.out.println("remove:" + remove); System.out.println("size:" + queue.size()); } System.out.println("----"); for (int i = 5; i > 0; i--) { queue.insert(i); System.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { Integer peek = queue.peek(); System.out.println("peek:" + peek); System.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { Integer remove = queue.remove(); System.out.println("remove:" + remove); System.out.println("size:" + queue.size()); } } }

 /* * 雙端隊列<span style="white-space:pre"> </span>兩端插入、刪除*/ public class QueueQT<T> { private LinkedList<T> list; public QueueQT() { list = new LinkedList<T>(); } // 插入隊頭public void insertLeft(T t) { list.addFirst(t); } // 插入隊尾public void insertRight(T t) { list.addLast(t); } // 移除隊頭public T removeLeft() { return list.removeFirst(); } // 移除隊尾public T removeRight() { return list.removeLast(); } // 查看隊頭public T peekLeft() { return list.getFirst(); } // 查看隊尾public T peekRight() { return list.getLast(); } public boolean isEmpty() { return list.isEmpty(); } public int size() { return list.size(); } }

 /* * 優先級隊列隊列中按優先級排序，是一個有序的隊列*/ public class QueueQP { private int max; private int[] ary; private int nItems; //實際數據項個數public QueueQP(int size) { this.max = size; ary = new int[max]; nItems = 0; } //插入隊尾public void insert(int t) { int j; if (nItems == 0) { ary[nItems++] = t; } else { for (j = nItems - 1; j >= 0; j--) { if (t > ary[j]) { ary[j + 1] = ary[j]; //前一個賦給後一個小的在後相當於用了插入排序，給定序列本來就是有序的，所以效率O(N) } else { break; } } ary[j + 1] = t; nItems++; } System.out.println(Arrays.toString(ary)); } //移除隊頭public int remove() { return ary[--nItems]; //移除優先級小的} //查看隊尾優先級最低的public int peekMin() { return ary[nItems - 1]; } public boolean isEmpty() { return nItems == 0; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQP queue = new QueueQP(3); queue.insert(1); queue.insert(2); queue.insert(3); int remove = queue.remove(); System.out.println("remove:" + remove); } }