棧 Stack

• 棧是一種線性結構
• 相比數組，棧對應的操作是數組的子集
• 只能從一端添加元素，也只能從一端取出元素
• 這一端稱為棧頂
• 棧是一種后進先出的數據結構

棧的應用

• 無處不在的Undo操作（撤銷）
• 括號匹配（編譯器）
• 程序調用的系統棧

funA(){ 1? ... 2? B() 3? ... }

funB(){ 1? ... 2? C() 3? ... }

funC(){ 1? ... 2? ... 3? ... }

棧的實現及復雜度分析

Stack<E>? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?<---implement---? ? ArrayStack<E>

• void push(E)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?O(1) 均攤
• E pop()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?O(1)?均攤
• E peek()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?O(1)
• int getSize()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??O(1)
• boolean isEmpty()? ? ? ? ? ? ? ? ? ? ? ??O(1)

實現源碼：

public class ArrayStack<E> implements Stack<E>{private Array<E> array;// 有參構造public ArrayStack(int capacity){array = new Array<>(capacity);}// 默認構造public ArrayStack(){this(10);}// 判斷棧是否為空@Overridepublic boolean isEmpty(){return array.isEmpty();}// 判斷棧是否已滿public boolean isFull(){return array.isFull();}// 獲取棧的容量@Overridepublic int getCapacity(){return array.getCapacity();}// 獲取棧內元素個數@Overridepublic int getSize(){return array.getSize();}// 查看棧頂元素@Overridepublic E peek(){return array.getLast();}// 棧頂元素出棧@Overridepublic E pop(){return array.removeLast();}// 入棧@Overridepublic void push(E e){array.addLast(e);}@Overridepublic String toString(){StringBuilder res = new StringBuilder();res.append(String.format("Stack Size = %d, Capacity = %d\n", array.getSize(), array.getCapacity()));res.append("Stack [");for (int i = 0; i < array.getSize(); i++) {res.append(array.get(i));if (i != array.getSize() - 1)res.append(", ");}res.append("] top");return res.toString();}public static void main(String[] args){ArrayStack<Integer> stack = new ArrayStack<>();for (int i = 0; i < 10; ++i) {stack.push(i);System.out.println(stack);if (i % 3 == 2) {stack.pop();System.out.println(stack);}}}
}

?