栈

栈性质

• 栈（也叫堆栈，Stack）是一种特殊的线性表，它只能在在表尾进行插入和删除操作，就像下面这样：

• 只能在一端进行插入和删除，当我们依次插入1、2、3、4这四个元素后，连续进行四次删除操作，删除的顺序刚好相反：4、3、2、1，我们一般将其竖着看：
  

• 底部称为栈底，顶部称为栈顶，所有的操作只能在栈顶进行，也就是说，被压在下方的元素，只能等待其上方的元素出栈之后才能取出，就像我们往箱子里里面放的书一样，因为只有一个口取出里面的物品，所以被压在下面的书只能等上面的书被拿出来之后才能取出，这就是栈的思想，它是一种先进后出的数据结构（FILO，First In, Last Out）

实现栈也是非常简单的，可以基于我们前面的顺序表或是链表，这里我们需要实现两个新的操作：

• pop：出栈操作，从栈顶取出一个元素。
• push：入栈操作，向栈中压入一个新的元素。

栈可以使用顺序表实现，也可以使用链表实现，这里我们就使用链表，实际上使用链表会更加的方便，我们可以直接将头结点指向栈顶结点，而栈顶结点连接后续的栈内结点：

栈的属性

• private final Node<E> head = new Node<>(null); 大体内容跟链表类似

• 以下代码利用链表方式来表示栈

private static class Node<E> {
    E element;
    Node<E> next;

    public Node(E element) {
        this.element = element;
    }
}

栈的插入

• 插入思路

• 插入代码

  • Node<E> node = new Node<>(element);新创建一个节点

public void push(E element) {
    Node<E> node = new Node<>(element);   //直接创建新结点
    node.next = head.next;    //新结点的下一个变成原本的栈顶结点
    head.next = node;     //头结点的下一个改成新的结点
}

栈的推出

• 推出思路和插入相反

• 推出代码

public E pop() {
    if (head.next == null)   //如果栈已经没有元素了，那么肯定是没办法取的
        throw new NoSuchElementException("栈已经为空");
    E e = head.next.element;   //先把待出栈顶元素取出来
    head.next = head.next.next;   //直接让头结点的下一个指向下一个的下一个
    return e;
}

总代码

• Main代码

import ClassStudy.LinkStack;

public class Main {
    public static void main(String[] args) {
        LinkStack<String> stack = new LinkStack<>();
        stack.push("AA");
        stack.push("BBB");
        stack.push("CCeC");
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

• LinkStack类

package ClassStudy;

import java.util.NoSuchElementException;

public class LinkStack<E> {

    private final Node<E> head = new Node<>(null);   //大体内容跟链表类似

    private static class Node<E> {
        E element;
        Node<E> next;

        public Node(E element) {
            this.element = element;
        }
    }

    //推入操作
    public void push(E element) {
        Node<E> node = new Node<>(element);   //直接创建新结点
        node.next = head.next;    //新结点的下一个变成原本的栈顶结点
        head.next = node;     //头结点的下一个改成新的结点
    }

    //推出操作
    public E pop() {
        if (head.next == null)   //如果栈已经没有元素了，那么肯定是没办法取的
            throw new NoSuchElementException("栈已经为空");
        E e = head.next.element;   //先把待出栈顶元素取出来
        head.next = head.next.next;   //直接让头结点的下一个指向下一个的下一个
        return e;
    }
}