杠上数据结构 - 栈

介绍

栈 : 是 一种只允许在一端进行插入，删除的线性表，具有先进后出的特性。

通常，栈的操作端称为 栈顶，另一端称为 栈底。栈的插入称为 进栈(push), 栈的删除操作称为 出栈(pop)。

栈.png

栈的存储结构

既然栈的本质是一种线性表，那么栈的存储结构也有两种：

• 顺序存储结构(顺序栈)
• 链式存储结构(链式栈)

栈顺序存储结构

栈的顺序存储结构一般使用 数组 实现。

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

栈链式存储结构

栈的链式结构是在 第一个节点处 插入，删除节点。因为如果在最后一个节点处进行插入，删除，则需要一个一个遍历获取到最后一个节点才行。

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;
    }
}