以前大家学了动态数组的完成，下面让我们用它来完成二种算法设计——栈和队列。最先，大家先看来一下栈。

什么叫栈？

栈是计算机系统的一种算法设计，它能够 临时性存放数据信息。那麼它跟二维数组有什么差异呢？
我们知道，在字符串中不管加上原素或是删掉原素，都能够依据数据库索引部位或值开展实际操作，栈是不是也适用这种的使用呢？回答是不好，栈较大的特征便是后进先出（Last In First Out, LIFO）：

栈尽管看上去简易，可是在计算机世界中拥有十分关键的功效。例如在持续启用时，就使用了栈的特点：

    public static void addNum(){
        System.out.println("加法运算");
        Scanner scanner = new Scanner(System.in);
        System.out.print("输入您整数金额a：");
        int a = scanner.nextInt();
        System.out.print("输入您整数金额b：");
        int b = scanner.nextInt();
        System.out.println("a   b = "   (a   b));
    }

    public static void main(String[] args) {
        addNum();
    }

这儿，在启用 addNum 方式 时，內部又先后启用了2次 Scanner 完成键入。因此 还可以那么看，先启用了 addNum 方式 ，可是务必等候2次 Scanner 启用进行后，addNum 方式 才可以完毕：

了解了栈后进先出的特性，大家就可以应用动态数组开展仿真模拟了。

应用动态数组仿真模拟栈

仿真模拟的关键环节取决于“后入”和“先出”，换句话说，假如应用二维数组仿真模拟得话，入栈时必须从二维数组尾端加上原素（addLast），出栈时也从尾端出栈（removeLast）：

因此 这样一来，二维数组头顶部事实上是栈底，二维数组尾端是栈顶。
下面咱们就用编码完成。

编码完成

最先界定栈的插口，标准栈的实际操作：

package com.algorithm.stack;

public interface Stack <E> {
    void push(E element);   // 入栈
    E pop();                // 出栈
    E peek();               // 查询栈顶原素
    int getSize();          // 获得栈长短
    boolean isEmpty();      // 分辨栈是不是为空

}

依照刚刚说的，只需各自应用动态数组的 addLast() 和 removeLast() 方式 取代栈的 push() 和 pop() 方式 就可以：

package com.algorithm.stack;

import com.algorithm.dynamicarrays.Array;

// 应用动态数组完成栈构造
// 栈底: index = 0; 栈顶: index = size - 1 (push: O(1), pop: O(1))
// 假如栈顶建在index=0的部位，push和pop都将遭遇很大花销(O(n))
public class ArrayStack<E> implements Stack<E>{
    private Array<E> arr;    // 应用以前完成的Array动态数组仿真模拟栈

    public ArrayStack(int capacity){
        arr = new Array<>(capacity);
    }

    public ArrayStack(){
        arr = new Array<>();
    }

    // 从栈顶压进
    @Override
    public void push(E element){
        arr.addLast(element);
    }

    // 从栈顶弹出来
    @Override
    public E pop(){
        return arr.removeLast();
    }

    // 从栈顶回到
    @Override
    public E peek(){
        return arr.getLast();
    }

    // 栈长短
    @Override
    public int getSize(){
        return arr.getSize();
    }

    // 栈容量
    public int getCapacity(){
        return arr.getCapacity();
    }

    // 分辨栈是不是为空
    @Override
    public boolean isEmpty(){
        return arr.isEmpty();
    }

    @Override
    public String toString(){
        StringBuilder str = new StringBuilder();
        str.append(String.format("Stack: size = %d, capacity = %d\n[", getSize(), getCapacity()));
        for (int i=0; i<getSize(); i  ) {
            str.append(arr.get(i));
            if (i < getSize() - 1) {
                str.append(", ");
            }
        }
        str.append("] top");    // 标志出栈顶部位
        return str.toString();
    }

    // main函数检测
    public static void main(String[] args) {
        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        for (int i =0; i<5; i  ){
            arrayStack.push(i);
            System.out.println(arrayStack);
        }
        // pop
        arrayStack.pop();
        System.out.println(arrayStack);
    }
}

/*
輸出結果：
Stack: size = 1, capacity = 10
[0] top
Stack: size = 2, capacity = 10
[0, 1] top
Stack: size = 3, capacity = 10
[0, 1, 2] top
Stack: size = 4, capacity = 10
[0, 1, 2, 3] top
Stack: size = 5, capacity = 10
[0, 1, 2, 3, 4] top
Stack: size = 4, capacity = 10
[0, 1, 2, 3] top
*/

結果满足预估。

栈的算法复杂度剖析

入栈相匹配的二维数组实际操作是 addLast()，我们可以根据查询该办法的主要完成开展剖析：

    /**
     * 在指定的部位加上原素
     * 特定部位处的因素必须向右边挪动一个企业
     * @param index   数据库索引
     * @param element 要加入的原素
     */
    public void add(int index, E element) {
        if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and <= size!");
        // 二维数组爆满开启扩充
        if (getSize() == getCapacity()) {
            resize(2 * getCapacity());  // 扩充为原二维数组的2倍
        }
        // 从车尾逐渐，往右边挪动原素，直至index
        for (int i = getSize() - 1; i >= index; i--) {
            data[i   1] = data[i];
        }
        // 加上原素
        data[index] = element;
        size  ;
    }

    // 二维数组尾端加上原素
    public void addLast(E element) {
        add(getSize(), element);
    }

    /**
     * 删掉特定部位原素
     * 根据往左边挪动一位，遮盖特定部位处的原素，完成删掉原素(data[size - 1] = null)
     * @param index 数据库索引
     */
    public E remove(int index) {
        if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and < size!");
        // 数组长度为0时抛出异常
        if (getSize() == 0) throw new IllegalArgumentException("Empty array!");
        E removedElement = data[index];
        // 往左边挪动原素
        for (int i = index; i < getSize() - 1; i  ) {
            data[i] = data[i   1];
        }
        // 将尾端空余出的部位置为空，释放出来資源
        data[getSize() - 1] = null;
        size--;
        // size过小开启二维数组减缩
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) resize(getCapacity() / 2);
        return removedElement;
    }

    // 删掉尾端原素
    public E removeLast() {
        return remove(getSize() - 1);
    }

能够 看得出，每一次从二维数组尾端加上原素时，add() 方式 的 for 循环系统都没法符合条件，相当于立即在 size 处加上原素，因此 算法复杂度为 O(1)。假如再考虑到二维数组爆满后引起的 resize 实际操作，等同于是完成了 n 1 次 add() 实际操作后才会开启 n次实际操作的 resize（挪动n个原素至新二维数组），因此 每一次 add() 实际操作均值用时为 \(\frac{2n 1}{n 1} \approx 2\)，是一个与数组长度 n 不相干的数，因此 还可以看成是 O(1) 复杂性的。
同样，出栈相匹配的 removeLast() 的算法复杂度也是 O(1)。

什么叫序列？

了解了栈后，序列就更简便了。事实上，序列是大家日常日常生活基本上每一天都是遇到的。大家去超市购物结帐时必须排长队，去金融机构申请办理工作时必须排长队，做核苷酸、接种疫苗就更必须排长队了