重庆住房城乡建设厅网站,app开发流程详解,网站备案 价格,朝阳区网站开发公司栈 Stack
栈是一种线性结构相比数组#xff0c;栈对应的操作是数组的子集只能从一端添加元素#xff0c;也只能从一端取出元素这一端称为栈顶栈是一种后进先出的数据结构
栈的应用
无处不在的Undo操作#xff08;撤销#xff09;括号匹配#xff08;编译器#xff09;程…栈 Stack
栈是一种线性结构相比数组栈对应的操作是数组的子集只能从一端添加元素也只能从一端取出元素这一端称为栈顶栈是一种后进先出的数据结构
栈的应用
无处不在的Undo操作撤销括号匹配编译器程序调用的系统栈funA(){ 1 ... 2 B() 3 ... } funB(){ 1 ... 2 C() 3 ... } funC(){ 1 ... 2 ... 3 ... } 栈的实现及复杂度分析
StackE ---implement--- ArrayStackE
void push(E) O(1) 均摊E pop() O(1) 均摊E peek() O(1)int getSize() O(1)boolean isEmpty() O(1)
实现源码
public class ArrayStackE implements StackE{private ArrayE 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){ArrayStackInteger 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);}}}
}
