数据结构-栈

1.概念

栈是一种先进后出的数据结构，其中有两个关键的位置：栈顶和栈底。当需要出栈时，只需将栈顶元素取出并将原来的栈顶元素指针向前移动。压栈时，只需将栈顶位置指向新的元素。具体的示意图如下：

栈的实现可以基于两种常见的数据结构：数组和链表

2. 栈的实现

2.1 基于数组

示意图：

代码实现(java版)：

public class ArrayStack {
    private Object[] data;
    private int top;

    /**
     * @param size 初始化数组大小
     */
    public ArrayStack(int size) {
        if (size < 0) {
            throw new IllegalArgumentException("数组大小小于0");
        }
        data = new Object[size];
        top = -1;
    }

    /**
     * 出栈
     *
     * @return
     */
    public Object pop() {
        if (top < 0) {
            throw new RuntimeException("没有栈元素");
        }
        Object ret = data[top];
        top--;
        return ret;
    }

    /**
     * 入栈
     */
    public void push(Object o) {
        // 如果已经达到最大容量，扩容2倍
        if (data.length == top + 1) {
            Object[] newArr = new Object[data.length << 1];
            System.arraycopy(data, 0, newArr, 0, data.length);
            data = newArr;
        }
        data[++top] = o;
    }

    public boolean empty() {
        return top == -1;
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer("(");

        for(int i =0 ; i <= top ; i++){
            stringBuffer.append(data[i]);
            stringBuffer.append(",");
        }
        if (stringBuffer.length() == 1) {
            return stringBuffer.toString() + ")";
        } else {
            return stringBuffer.substring(0, stringBuffer.length() - 1) + ")";
        }
    }

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);
        stack.push(10);
        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push(45);
        stack.push(66);
        // (10,a,b,c,45,66)
        System.out.println(stack);
        Object o = stack.pop();
        // 66
        System.out.println(o);
        // (10,a,b,c,45)
        System.out.println(stack);
    }

}

1. 属性介绍：
   data： 存放栈元素数组，注意：栈元素是这个数组元素的子集，元素范围是[0,top]。如果在压栈过程中，数组已经满了，需要进行扩容操作。
   top: 控制栈元素范围，同时指定栈顶元素位置。
2. 方法介绍：
   push: 压栈，如果数组元素不够，需要扩容。
   pop: 出栈，弹出栈顶元素
   empty: 判断栈是不是为空

2.2 基于链表

示意图：

代码实现：

public class LinkedStack {
    private Node head; // 链表的head，也是栈的栈顶
    private int size;

    private class Node {
        private Object data;
        private Node next;

        Node(Object data) {
            this.data = data;
        }
    }


    public void push(Object o) {
        if (head == null) {
            head = new Node(o);
            head.next = null;
        } else {
            Node cur = new Node(o);
            cur.next = head;
            head = cur;
        }
        size++;
    }

    public Object pop() {
        if (head == null) {
            throw new RuntimeException("没有栈元素");
        }
        Object ret = head.data;
        head = head.next;
        size--;
        return ret;
    }

    public Object empty() {
        return size <= 0;
    }

    /**
     * 打印方式： 栈顶 -> 栈底
     * @return
     */
    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer("(");
        Node cur = head;
        while (cur != null) {
            stringBuffer.append(cur.data);
            stringBuffer.append(",");
            cur = cur.next;
        }
        if (stringBuffer.length() == 1) {
            return stringBuffer.toString() + ")";
        } else {
            return stringBuffer.substring(0, stringBuffer.length() - 1) + ")";
        }
    }

    public static void main(String[] args) {
        LinkedStack linkedStack = new LinkedStack();
        linkedStack.push(1);
        linkedStack.push(2);
        linkedStack.push("q");
        linkedStack.push("w");
        linkedStack.push("e");
        // (e,w,q,2,1)
        System.out.println(linkedStack);

        linkedStack.pop();
        linkedStack.pop();
        linkedStack.pop();
        // (2,1)
        System.out.println(linkedStack);
        linkedStack.pop();
        linkedStack.pop();
        // ()
        System.out.println(linkedStack);
        // Exception in thread "main" java.lang.RuntimeException: 没有栈元素
        linkedStack.pop();
    }

}

1. 设计介绍
   基于链表的栈，可以使用链表的头或者尾作为栈顶元素。如果选用尾作为栈顶元素，当出栈时需要将tail指向前一个元素，这个比较麻烦，而使用头节点就没有这个问题，只需要在push/pop时修改head节点的指向就行。

2. 属性介绍
   head: 链表的头节点，栈的栈顶。
   size: 链表的长度

3. 方法介绍
   push: 压栈，修改head的指向
   pop: 出栈，修改head的指向