介紹

棧 : 是 一種只允許在一端進行插入，刪除的線性表照棋，具有先進后出的特性胧卤。

通常，棧的操作端稱為 棧頂佣盒，另一端稱為 棧底。棧的插入稱為 進棧(push), 棧的刪除操作稱為 出棧(pop)顽聂。

棧.png

棧的存儲結構

既然棧的本質是一種線性表肥惭，那么棧的存儲結構也有兩種：

• 順序存儲結構(順序棧)
• 鏈式存儲結構(鏈式棧)

棧順序存儲結構

棧的順序存儲結構一般使用 數組 實現(xiàn)盯仪。

public class ArrayStack<E> {

    private int defaultCapacity = 10;

    /**
     * 存儲元素的容器
     */
    private Object[] elements;
    /**
     * 棧中元素個數
     */
    private int size;
    /**
     * 標示棧頂的變量
     */
    private int top;

    public ArrayStack() {
        elements = new Object[defaultCapacity];
        top = -1;
    }

    public ArrayStack(int capacity) {
        elements = new Object[capacity];
        top = -1;
    }

    /**
     * 進棧
     *
     * @param element
     * @return
     */
    public E push(E element) {
        ensureCapacity(size + 1);
        elements[size] = element;
        size++;
        return element;
    }

    /**
     * 出棧
     *
     * @return
     */
    public E pop() {
        if (size > 0) {
            E element = (E) elements[size - 1];
            size--;
            return element;
        }
        throw new IllegalArgumentException("the stack is empty");
    }

    public boolean empty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    /**
     * 確保容器大小是否可用，是否擴容
     *
     * @param newSize
     */
    private void ensureCapacity(int newSize) {
        if (newSize > elements.length) {
            increaseCapacity(newSize);
        }
    }

    /**
     * 擴大容器大小, 1.5 倍擴容
     */
    private void increaseCapacity(int newSize) {
        int increasedSize = newSize;
        increasedSize = increasedSize + increasedSize >> 1;
        try {
            elements = Arrays.copyOf(elements, increasedSize);
        } catch (OutOfMemoryError error) {
            // 擴容失敗
            error.printStackTrace();
        }
    }

    public Object[] toArray() {
        return Arrays.copyOf(elements, size);
    }
}

棧鏈式存儲結構

棧的鏈式結構是在 第一個節(jié)點處 插入蜜葱，刪除節(jié)點全景。因為如果在最后一個節(jié)點處進行插入，刪除牵囤，則需要一個一個遍歷獲取到最后一個節(jié)點才行爸黄。

public class LinkedStack<E> {
    private Node<E> head;
    private int size;

    public LinkedStack() {
        head = new Node<>();
    }

    public E push(E element) {
        Node<E> node = new Node<>(element);
        node.next = head.next;
        head.next = node;
        size++;
        return element;
    }

    public boolean empty() {
        return size == 0;
    }

    public E pop() {
        if (size > 0) {
            Node<E> topNode = head.next;
            head.next = topNode.next;
            size--;
            return topNode.element;
        }
        throw new IllegalArgumentException("the stack is empty");

    }

    public int size() {
        return size;
    }

    public Object[] toArray() {
        Object[] objects = new Object[size];
        Node<E> iterator = head.next;
        if (iterator != null) {
            int index = 0;
            objects[index] = iterator;
            while (iterator.next != null) {
                iterator = iterator.next;
                index++;
                objects[index] = iterator;
            }
        }
        return objects;
    }
}