Beauty Of Algorithms 8 Summary. Stack

什么是栈

• 后进者先出，先进者后出，这就是典型的 ”栈“ 结构
• 从栈的操作特性来看，是一种“操作受限”的线性表，只允许在端插入和删除数据

为什么需要栈

• 栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现。
• 但任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。
• 所以，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特定时，我们应该首选栈这种数据结构。

如何实现栈

数组实现

使用数组实现固定容量的栈

public class ArrayStack {
    private String[] data;
    private int count;
    private int maxSize;

    public ArrayStack(int maxSize) {
        data = new String[maxSize];
        this.maxSize = maxSize;
        count = 0;
    }

    public void push(String item) throws Exception {
        if (count == maxSize - 1) {
            throw new Exception("stack is full ,cant push anymore !");
        }
        data[count] = item;
        count++;
    }

    public String pop() throws Exception {
        if (count == 0) {
            throw new Exception("Stack is empty, no element to pop !");
        }
        String top = data[count-1];
        count--;
        return top;
    }

    public void printStack() {
        for (int i = this.count-1; i >=0; i--) {
            System.out.println(this.data[i]);
        }
    }

    public static void main(String[] args) throws Exception {
        ArrayStack arrayStack = new ArrayStack(5);
        arrayStack.push("1");
        arrayStack.push("2");
        arrayStack.push("3");
        arrayStack.printStack();
        System.out.println("***************************");
        System.out.println(arrayStack.pop());
        System.out.println("***************************");
        arrayStack.printStack();

    }

}

数组实现自动扩容

改进代码：

//入栈方法
    public void push(String item) throws Exception {
        if (count == maxSize) {
            maxSize = count * 2;
            String[] tmp = data;
            data = new String[maxSize];
            for (int i = 0; i <count ; i++) {
                data[i] = tmp[i];
            }
        }
        data[count] = item;
        count++;
    }

链表实现

单链表栈：

public class SingleLinkedStack<T> {
    private class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> top;

    public SingleLinkedStack() {
        top = null;
    }

    public void push(T t){
        Node node = new Node(t,top);
        top = node;
    }

    public T pop() throws Exception {
        if (top == null){
            throw new Exception("Stack is empty, no element to pop !");
        }
        Node<T> node = top;
        top = top.next;
        return node.data;
    }

    public void printStack(Node<T> top){
        while (top != null){
            System.out.println(top.data);
            top = top.next;
        }
    }

    public static void main(String[] args) throws Exception {
        SingleLinkedStack<String> singleLinkedStack = new SingleLinkedStack<>();
        singleLinkedStack.push("1");
        singleLinkedStack.push("2");
        singleLinkedStack.push("3");
        singleLinkedStack.printStack(singleLinkedStack.top);
        System.out.println("***************************");
        System.out.println(singleLinkedStack.pop());
        System.out.println("***************************");
        singleLinkedStack.printStack(singleLinkedStack.top);
    }

}

栈的应用

栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成 “栈” 这种结构，用来存储函数调用时的临时变量。

每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

栈在表达式求值中的应用

利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。从左向右遍历表达式，当遇到数字，就直接压入操作数栈。当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈。若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。

站在括号匹配中的应用

用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时候，则将其压入栈

当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。

如果扫描过程中，遇到不能配对的右括号，或者占中没有数据，则说明为非法格式。

当所有的括号都扫描完成后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。

实现浏览器的前进和后退功能

我们使用两个栈 X 和 Y，我们把首次浏览的页面依次压入栈 X，Y。

当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入 Y 栈。

当点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。

当栈 X 中没有数据时，说明没有页面可以继续后退浏览了。

当 Y 栈没有数据，那就说明没有页面可以点击前进浏览了。