棧（Stack）是限定僅在表尾進(jìn)行插入或刪除操作的線程表。因此對(duì)棧來說表尾端有其特殊含義，稱為棧頂（top），相應(yīng)的表頭端稱為棧底（bottom）。

image

棧是一種后進(jìn)先出（last in first out）的線性表，簡稱LIFO。

棧的抽象數(shù)據(jù)類型定義

package com.codestd.study.stack;

/**
 * 棧ADT
 */
public interface Stack<E> {
    /**
     * 查看棧頂元素，僅僅查看元素，不從棧中取出。
     */
    E peek();

    /**
     * 向棧中添加元素。
     */
    void push(E e);

    /**
     * 取出棧頂元素
     */
    E pop();

    /**
     * 清空棧
     */
    void clear();
    /**
     * 棧中元素的數(shù)量，如果棧為空，則返回0
     */
    int size();
    /**
     * 判斷棧是否為空
     */
    boolean isEmpty();
    /**
     * 判斷棧是否已滿
     */
    boolean isFull();
}

棧的表示和實(shí)現(xiàn)

前文講過，計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)有兩種方式，一種是順序存儲(chǔ)，一種是非順序存儲(chǔ)。棧對(duì)應(yīng)兩種存儲(chǔ)方式有兩種實(shí)現(xiàn)方式：一種是數(shù)組，一種是單向鏈表。

棧的數(shù)組實(shí)現(xiàn)

數(shù)組實(shí)現(xiàn)棧不需要記錄棧底，只需要記錄棧頂指針就可以了。入棧的時(shí)候棧頂指針后移，出棧的時(shí)候棧頂指針前移。使用數(shù)組實(shí)現(xiàn)是比較簡單的，也是比較容易實(shí)現(xiàn)的。

image

package com.codestd.study.stack;

import java.util.NoSuchElementException;

/**
 * 數(shù)組實(shí)現(xiàn)棧
 */
public class ArrayStack<E> implements Stack<E> {

    private final int maxSize;
    private final E[] elementData;
    private int top = -1;

    @SuppressWarnings("unchecked")
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        this.elementData = (E[]) new Object[this.maxSize];
    }

    @Override
    public E peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("?？?);
        }
        return this.elementData[this.top];
    }

    @Override
    public void push(E e) {
        if (this.isFull()) {
            throw new RuntimeException("棧滿");
        }
        this.top++;
        this.elementData[this.top] = e;
    }

    @Override
    public E pop() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("棧空");
        }
        E el = this.elementData[this.top];
        this.elementData[this.top] = null;
        this.top--;
        return el;
    }

    @Override
    public void clear() {
        for (int i = 0; i < this.top + 1; i++) {
            this.elementData[i] = null;
        }
        this.top = -1;
    }

    @Override
    public int size() {
        return this.top + 1;
    }

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

    @Override
    public boolean isFull() {
        return (this.top + 1) == this.maxSize;
    }
}

棧的鏈表實(shí)現(xiàn)

是用鏈表實(shí)現(xiàn)會(huì)相對(duì)復(fù)雜一點(diǎn)。這里我們使用的是單向鏈表。

與前面講的單向鏈表不同，這里我們不再是使用next指向下一個(gè)節(jié)點(diǎn)，而是使用prev指向上一個(gè)節(jié)點(diǎn)。然后指針top始終指向最新的節(jié)點(diǎn)。如果取出棧頂數(shù)據(jù)，則指針指向棧頂元素的prev。

image

下面我們使用代碼來實(shí)現(xiàn)。

package com.codestd.study.stack;

import java.util.NoSuchElementException;

/**
 * 鏈表實(shí)現(xiàn)棧
 */
public class LinkedStack<E> implements Stack<E>{

    private Node<E> top;
    private int size;
    private int maxSize = Integer.MAX_VALUE;

    public LinkedStack() {
    }

    public LinkedStack(int maxSize) {
        this.maxSize = maxSize;
    }

    @Override
    public E peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("棧中沒有元素");
        }
        return this.top.item;
    }

    @Override
    public void push(E e) {
        if (this.isFull()) {
            throw new RuntimeException("棧滿");
        }
        if (this.top == null) {
            this.top = new Node<>(e);
        } else {
            Node<E> node = new Node<>(e);
            node.prev = this.top;
            this.top = node;
        }
        this.size++;
    }

    @Override
    public E pop() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("棧中沒有元素");
        }
        Node<E> node = this.top;
        this.top = node.prev;
        node.prev = null;
        this.size--;
        return node.item;
    }

    @Override
    public void clear() {
        Node<E> node = this.top;
        while (node != null) {
            Node<E> prev = node.prev;
            node.prev = null;
            node = prev;
        }
        this.top = null;
        this.size = 0;
    }

    @Override
    public int size() {
        return this.size;
    }

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

    @Override
    public boolean isFull() {
        return this.size == this.maxSize;
    }

    private static class Node<E> {
        E item;
        Node<E> prev;

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