Java实现栈

在上篇文章中，我们了解了单向链表。在这篇文章中，我们了解下另一种数据结构，栈。通过单向链表我们可以实现栈

栈

栈是一种先进后出的数据结构，最后入栈的元素，最先读取出来。就像向箱子里放书一样，最后放进去的那本书，我们可以最先从箱子里取出来。

栈结构

栈可以分为静态栈(数组实现)和动态栈(链表实现)

Java实现动态栈

通过链表实现栈，我们可以想象有个栈顶节点，当入栈的时候，原先的栈顶节点成为新的节点后继节点，新的节点成为新的栈顶节点。同理，出栈的时候，讲栈顶节点弹出，第二个节点成为新的栈顶节点。

• 入栈

    /**
     * 入栈
     * @param value
     */
    public void push(Object value){
        Node pushedNode = new Node(value);
        pushedNode.next = top;
        top = pushedNode;

        size++;
    }

• 出栈

    /**
     * 出栈
     */
    public Object pop() throws Exception {

        if(size == 0){
            throw new Exception("空栈异常");
        }

        Node popedNode = top;
        top = top.next;
        size --;

        return  popedNode.data;
    }

• 返回栈顶元素

    /**
     * 返回栈顶元素
     */
    public Object peek() throws Exception {
        if(size == 0){
            throw new Exception("空栈异常");
        }

        return  top.data;
    }

• 遍历栈

    /**
     * 遍历栈
     */
    public void traverse(){
        Node temp = top;
        while (temp != null){
            System.out.println(""+temp.data);

            temp = temp.next;

        }
    }

Java 实现静态栈

通过数组实现栈，我们可以想象栈顶索引，当入栈的时候，栈顶索引加一，赋值给栈顶。当出栈的时候，返回栈顶的值，并且栈顶索引减一。

public class ArrayStatck {

    private Object[] data;
    private int top;
    private int maxSize;

    public ArrayStatck(int maxSize) {
        this.maxSize = maxSize;
        this.top = -1;
        data = new Object[maxSize];
    }

    /**
     * 入栈
     * @param value
     */
    public void push(Object value) throws Exception {
        if(top == maxSize-1){
            throw new Exception("栈满异常");
        }

        data[++top] = value;
    }

    /**
     * 出栈
     * @throws Exception
     */
    public void pop()throws Exception{
        if(top == -1){
            throw  new Exception("栈空异常");
        }

        Object value = data[top--];
    }

    /**
     * 遍历栈
     */
    public void traverse(){
        while (top != -1){
            System.out.println(""+data[top--]);
        }
    }
}

代码路径

总结

本篇文章主要介绍了栈的动态实现和静态实现，这对于我们后续一些算法的实现有很大的帮助。