栈（stack）是插入和删除只能在一个位置上进行的表（后进先出），该位置是表的末端，叫做栈的顶（top）。对栈的基本操作有 push（进栈） 和 pop（出栈），push 相当于插入，pop 相当于删除。

　　左图栈模型说明：通过 push 向栈输入，通过 pop 和 top 从栈输出

　　右图栈模型说明：栈顶是栈中唯一可见的元素

• 栈的数组实现

  public class ArrayStack<T> {    //设置为2是为了检验ensureCapacity()方法的正确性    private Object[] data = http://www.mamicode.com/new Object[2];    private int size;    //是否空栈    public boolean empty() {        return size == 0;    }    //进栈    public void push(T t) {        ensureCapacity();        data[size++] = t;    }    //出栈    public T pop() {        //noinspection unchecked        return (T) data[--size];    }    //确保容量    private void ensureCapacity() {        if (size < data.length) {            return;        }        data = Arrays.copyOf(data, data.length + (data.length >> 1));    }    public static void main(String[] args) {        ArrayStack<String> stack = new ArrayStack<>();        char c[] = "Array Stack".toCharArray();        for (int i = c.length - 1; i >= 0; i--) {            stack.push(String.valueOf(c[i]));        }        while (!stack.empty()) {            System.out.print(stack.pop());        }    }}

   

• 栈的链表实现

  public class LinkedStack<T> {    private Node<T> node;    private int size;    private class Node<T> {        T item;        Node<T> next;        public Node(T item, Node<T> next) {            this.item = item;            this.next = next;        }    }    //是否空栈    public boolean empty() {        return size == 0;    }    //进栈    public void push(T t) {        Node<T> n = new Node<>(t, node);        node = n;        size++;    }    //出栈    public T pop() {        T t = node.item;        node = node.next;        size--;        return t;    }    public static void main(String[] args) {        LinkedStack<String> stack = new LinkedStack<>();        char c[] = "Linked Stack".toCharArray();        for (int i = c.length - 1; i >= 0; i--) {            stack.push(String.valueOf(c[i]));        }        while (!stack.empty()) {            System.out.print(stack.pop());        }    }}

   

   

栈 ADT