栈

示例练习>>>

栈（stack）是一种特殊的线性表，他只能对栈顶添加和删除。栈只有入栈和出栈两种操作，他就好像我们把书一本本的摞起来，最先放的书肯定是摞在下边，最后放的书肯定是摞在了最上面，摞的时候不允许从中间放进去，拿书的时候先从最上面开始拿，不允许从下边或中间抽出来，所以栈是一种后进先出（LIFO, Last In First Out）的数据结构，如下图所示。

栈的链表实现：

栈的实现方式可以使用链表也可以使用数组，先来看下链表的实现方式，链表实现的好处就是可以动态增加节点，栈中元素个数没有限制，因为只能在栈顶添加和删除，我们使用单向链表即可实现，如下图所示。

来看下代码：

public class Stack1<E> {

    // 栈中的节点类。
    private class LinkNode {
        E val;// 节点中存储的数据。
        LinkNode next;// 指向下一个节点的指针。

        public LinkNode(E val, LinkNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private LinkNode head;// 栈顶节点，无论添加还是删除，始终是变动的。

    // 往栈中添加元素。
    public void push(E val) {
        // 把数据放入栈顶，如果 head 为空会创建 head 节点。
        head = new LinkNode(val, head);
    }

    // 弹出栈顶元素。
    public E pop() {
        if (head == null)
            throw new NullPointerException();
        LinkNode next = head.next;
        E result = head.val;// 记录栈顶元素的值。
        head.val = null;// 清除栈顶节点数据。
        head = next;// 更新栈顶节点。
        return result;// 返回弹出的值。
    }

    // 获取栈顶元素的值，不出栈。
    public E top() {
        if (head == null)
            throw new NullPointerException();
        return head.val;
    }
}

栈的数组实现：

使用数组实现栈只需要一个变量 top ，他始终是指向栈顶的，如下图所示。

来看下代码：

public class Stack2<E> {

    private Object[] data;
    private int maxSize;// 栈的最大容量。
    private int top = -1;// 栈顶元素下标。

    public Stack2(int maxSize) {
        if (maxSize <= 0)
            throw new IllegalArgumentException("队列容量必须大于0 : " + maxSize);
        this.maxSize = maxSize;
        data = new Object[this.maxSize];
    }


    // 往栈中添加元素。
    public void push(E val) {
        if (top == maxSize - 1)
            throw new IllegalStateException("栈已经满了，无法再入栈……");
        data[++top] = val;
    }

    // 弹出栈顶元素。
    public E pop() {
        if (top == -1)
            throw new IllegalStateException("栈是空的，无法出栈……");
        E result = (E) data[top];// 获取栈顶元素。
        data[top--] = null;
        return result;// 返回弹出的值。
    }

    // 获取栈顶元素的值，不出栈。
    public E top() {
        if (top == -1)
            throw new IllegalStateException("栈是空的，无法出栈……");
        return (E) data[top];
    }
}

相关链接