数据结构-栈

概述

栈(stack)是常用的 线性数据结构，它属于逻辑结构，物理实现既可以用 数组，也可以用 链表来完成。栈中的元素只能先进后出(First In Last Out, 简称FILO)，最早进入的元素存放的位置叫做 栈底， 最后进入的元素存放的位置叫做 栈顶。

Java栈

Java中栈继承自Vector，是线程安全的，底层基于数组实现。

Stack类

public
class Stack<E> extends Vector<E> {
    // 入栈
    public E push(E item) {
        // 在Vector中实现
        addElement(item);

        return item;
    }
    // 出栈(返回栈顶元素，并删除栈顶值)
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }
    // 返回栈顶元素，不删除栈顶值
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
}

Vector类

// 底层基于数组实现
protected Object[] elementData;
// vector类在方法上加synchronized同步锁
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

基于数组自定义实现

这里简单实现下，主要做原理演示

public class ArrayStack {

    private Object[] elementData; // 数据
    private int elementCount; // 数组长度

    public ArrayStack(int initialCapacity) {
        this.elementCount = 0;
        this.elementData = new Object[initialCapacity];
    }

    public Object push(Object item) {
        if (full()) {
            throw new IllegalArgumentException("栈满了");
        }
        elementData[elementCount++] = item;
        return item;
    }

    public Object pop() {
        if (empty()) {
            throw new IllegalArgumentException("栈空了");
        }
        Object data = peek();
        elementCount--;
        return data;
    }

    public Object peek() {
        return elementData[elementCount-1];
    }

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

    public boolean full() {
        return elementCount == elementData.length;
    }
}

测试

public class Test {

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(3);
        for (int i=0; i<3; i++) {
            stack.push(i);
        }

        for (int i=0; i<4; i++) {
            if (i==3) {
                stack.push(i);
            }
            System.out.print(stack.pop());
        }
        // 输出2103
    }
}

基于链表自定义实现

public class LinkedListStack<E> {

    StackNode<E> top = null;        //栈顶，也是一个node节点

    class StackNode<E>{
        E data;
        StackNode<E> next;

        public StackNode(E data) {
            this.data = data;
        }
    }

    public boolean isEmpty() {
        return top == null;
    }

    /**
     * 往栈中push一个数据：
     * 首先将要push的数据的next赋值为栈顶top
     * 然后将栈顶指针指向新push进来的节点
     * */
    public void push(E data) {
        StackNode<E> newNode = new StackNode<E>(data);
        newNode.next = top;
        top = newNode;
    }

    /**
     * 从栈中弹出一个数据，
     * 将栈顶指针指向弹出节点的下一个
     * */
    public E pop() {
        if(this.isEmpty()) {
            System.out.println("栈已经空啦");
            return null;
        }
        E data = top.data;
        top = top.next;
        return data;
    }

    /**
     * 返回栈顶数据，但是不出栈。数据任然保存在栈中
     * */
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        return top.data;
    }

    //将栈中所有数据出栈
    public void printStack() {
        System.out.println("开始出栈:");
        while(!isEmpty()) {
            System.out.println(top.data);
            top = top.next;
        }
        System.out.println("出栈结束！");
    }

    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();        //创建一个栈
        for (int i=0; i<3; i++) {
            stack.push(i);
        }
        for (int i=0; i<4; i++) {
            System.out.print(stack.pop());
        }
        // 输出： 210栈已经空啦
    }
}