栈详解(Java实现)

1. 简介

给线性表的操作加上限定,只能从末尾删除(出栈),添加(入栈)。这种特殊的线性表就叫做栈(stack)又称后进后出(LILO:Last In Last Out)线性表。
栈的逻辑结构如下图所示:

栈的逻辑结构

2. 栈的API

public interface Stack<E> {
    /**
     * 获取栈顶元素
     * @return 栈为空返回null,否则返回栈顶元素
     */
    E getTop();

    /**
     * 入栈操作,将元素放入栈顶
     * @param item 放入元素
     */
    void push(E item);

    /**
     * 出栈操作
     * @return 栈为空返回null,否则返回栈顶元素
     */
    E pop();

    /**
     * 销毁栈
     */
    void destroy();

    /**
     * 判断栈是否为空
     * @return true<br/>栈不为空<br/>false<br/>栈为空
     */
    boolean isEmpty();

    /**
     * 返回栈的元素数量
     * @return 栈的元素数量
     */
    int length();
}

3. 伪代码

节点

class node
    elem;
    prev;

出栈操作伪代码,rear尾节点,head头结点

pop()
    node save = rear;
    save = rear;
    rear = rear.prev;
    save.prev = null;

入栈操作伪代码,rear尾节点,head头节点

push(elem)
     node push = new node;
     node.elem = elem;
     node.prev = rear;
     prev = node;

4. Java代码描述

public class StackImpl<E> implements Stack<E> {
    private Node<E> head;
    private Node<E> rear;
    private int size;

    private class Node<E> {
        E elem;
        Node<E> prev;
    }

    StackImpl() {
        head = rear = new Node<>();
    }

    @Override
    public E getTop() {
        if (head == rear) {
            return null;
        }
        return rear.elem;
    }

    @Override
    public void push(E item) {
        if (item == null) {
            return;
        }
        Node<E> push = new Node<>();
        push.elem = item;
        push.prev = rear;
        rear = push;
        size++;
    }

    @Override
    public E pop() {
        if (size == 0) {
            return null;
        }
        //保存尾节点
        Node<E> pop = rear;
        //尾节点指向上一个节点
        rear = rear.prev;
        //断开上一个尾节点的连接
        pop.prev = null;
        size--;
        return pop.elem;
    }

    @Override
    public void destroy() {
        head = rear = new Node<>();
        size = 0;
        //help GC
        rear.prev = null;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int length() {
        return size;
    }
}