概述

栈是一种用于存储数据的简单数据结构（与链表类似）。数据入栈的次序是栈的关键。可以把一堆盘子看成栈的例子。当盘子洗干净后，它们会添加到栈的顶端。当需要盘子时，也是从栈的顶端拿取。所以最后一个放入的盘子最先被拿走。

定义：具有一定操作约束的线性表。只在一端（栈顶，Top）做插入、删除。

认识几个名词

• 插入数据：入栈（Push），往顶端放盘子。
• 删除数据：出栈（Pop），拿走顶端的盘子。
• 后入先出：Last In First Out（LIFO）

栈的主要操作

栈中主要操作有：

• int pop() : 删除并返回栈顶元素
• void push(int item) : 将元素 item 压入堆栈
• int isFull() : 判断栈 S 是否已满
• int isEmpty() : 判断堆栈 S 是否为空

再来看个图加深理解：

实现

栈抽象数据类型有多种实现方式。常用的方法有数组和链表的实现方法

1）数组实现

简单来说就是使用数组来存储栈中的项。如下图所示，从左到右向数组中添加所有的元素，并定义一个变量用来记录数组当前栈顶（top）元素的下标。

当数组存满了栈元素时，执行入栈操作将抛出栈满异常。当对一个没有存储栈元素的数组执行出栈操作时，将抛出栈空异常。

public class ArrayStack {
    private int top;
    private int[] array;
    private int maxsize;
    public ArrayStack() {
        maxsize = 5;
        array = new int[maxsize];
        top = -1;             /*初始化栈为空，所以top标记为 -1*/
    }
    public boolean isEmpty() {
        return (top == -1);
    }
    public boolean isFull() {
        return (top == (maxsize-1));
    }
    public void push(int data) {
        if(isFull()) System.out.println("Stack Overflow");
        else array[++top] = data;            /* ++top 先自增后赋值*/
    }
    public int pop() {
        if(isEmpty()) {
            System.out.println("Stack is Empty");
            return 0;
        }else {
            return array[top--];            /* top-- 先赋值后自减 */
        }
    }
}

2）链表实现

使用链表也可以实现栈。下图左实现的是 push 操作， head 是堆栈的头结点，head 指向真正的堆栈元素 itemNode，也是堆栈 Top 元素，通过在 head 后插入新的 itemNode ，新 itemNode 会变成堆栈的 Top 元素；下图右实现的是 pop 操作，删除堆栈中 Top 元素（FisrtNode），让 head 指向下一个元素。

public class ListStack {
    private MyListNode headNode;
    public ListStack( hnode ) {
        headNode = hnode;
    }
    public void push(int data) {
        // 表头插入新节点            
        MyListNode itemNode = new MyListNode(data);
        itemNode.setNext(headNode.getNext());
        headNode.setNext(listNode);  
    }

    public int top() {
        if(headNode == null) return -1;
        else return headNode.getData();
    }

    public int pop() {
        if(headNode == null) {
            throw new EmptyStackException();
        }else {
            MyListNode firstNode = headNode.getNext();
            headNode.setNext( firstNode.getNext() );
            int data = firstNode.getData();
            return data;
        }
    }

    public boolean isEmpty() {
        if(headNode == null) return true;
        else return false;
    }

    // 删除整个堆栈
    public void deleteStack() {
        headNode = null;     
    }

    public void setHeadNode( hnode ) {
        headNode = hnode;
    }
}