1. 簡(jiǎn)介

給線性表的操作加上限定,只能從末尾刪除(出棧),添加(入棧)。這種特殊的線性表就叫做棧(stack)又稱后進(jìn)后出(LILO:Last In Last Out)線性表。
棧的邏輯結(jié)構(gòu)如下圖所示:

棧的邏輯結(jié)構(gòu)

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();

    /**
     * 返回棧的元素?cái)?shù)量
     * @return 棧的元素?cái)?shù)量
     */
    int length();
}

3. 偽代碼

節(jié)點(diǎn)

class node
    elem;
    prev;

出棧操作偽代碼,rear尾節(jié)點(diǎn),head頭結(jié)點(diǎn)

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

入棧操作偽代碼,rear尾節(jié)點(diǎn),head頭節(jié)點(diǎn)

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;
        }
        //保存尾節(jié)點(diǎn)
        Node<E> pop = rear;
        //尾節(jié)點(diǎn)指向上一個(gè)節(jié)點(diǎn)
        rear = rear.prev;
        //斷開上一個(gè)尾節(jié)點(diǎn)的連接
        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;
    }
}