棧和隊列:
一般是作為程序員的工具,用於輔助構思算法,生命週期較短,運行時才被創建;
訪問受限,在特定時刻,只有一個數據可被讀取或刪除;
是一種抽象的結構,內部的實現機制,對用戶不可見,比如用數組、鍊錶來實現棧。
模擬棧結構
同時,只允許一個數據被訪問,後進先出對於入棧和出棧的時間複雜度都為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); } }