04-栈(Stack)结构应用分析

栈(Stack)结构应用分析

什么是栈(Stack)?

栈（Stack）是一种先进后出(FILO-First In Last Out)，操作上受限的线性表。其限制指的是，仅允许在表的一端进行插入和删除运算。这一端称为栈顶（top），相对地，把另一端称为栈底(bottom)。如图所示：

对于栈而言，我们生活中也有很多这样的应用，例如一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。

栈(Stack)有哪些应用场景？

实际的软件项目中很多地方都会用到这种栈结构，例如：
1）Java中虚拟机内部方法调用栈。
2）运算表达式的语法分析，词法分析。
3）浏览器内置的回退栈(back stack)。
4）手机中APP的回退栈(back stack)。
我们现在以手机中的APP为例进行分析，如图所示：

在android手机上我们每打开一个app都会创建一个回退栈，栈中存储每次打开的界面对象，新打开的UI界面会处于栈顶。

基于Java定义栈结构规范？

package com.cy.pj.ds.stack;
/**栈接口规范的定义*/
public interface Stack {
    /**
     * 压栈
     * @param item
     */
    void push(Object item);
    /**
     * 出栈
     * @return
     */
    Object pop();
    /**
     * 获取栈顶元素，但不出栈。
     * @return
     */
    Object peek();
    /**
     * 获取栈中有效元素个数
     * @return
     */
    int size();
    /**
     * 判定栈是否为空
     * @return
     */
    boolean isEmpty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

基于Java数组实现栈(Stack)？

/**
 * 基于数组实现栈结构中的数据操作
 * @author qilei
 */
public class BoundedArrayStack implements Stack {

    private Object[] array;
    private int size;
    public BoundedArrayStack(int capacity) {
        this.array=new Object[capacity];
    }
    @Override
    public void push(Object item) {
        if(size==array.length)
            throw new IllegalStateException("Stack is full");
        this.array[size++]=item;
    }

    @Override
    public Object pop() {
        if(size==0)
            throw new NoSuchElementException("Stack is empty");
        Object result=array[size-1];
        array[--size]=null;
        return result;
    }

    @Override
    public Object peek() {
        if(size==0)
            throw new NoSuchElementException("Stack is empty");
        return array[size-1];//栈顶元素
    }

    @Override
    public int size() {
        return size;
    }
    @Override
    public boolean isEmpty() {
        return size==0;
    }
    public static void main(String[] args) {
        BoundedArrayStack stack=new BoundedArrayStack(3);
        stack.push(100);
        stack.push(200);
        stack.push(300);
        System.out.println(stack.peek());
        //stack.push(400);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

基于Java链表实现栈(Stack)?

public class LinkedStack implements Stack {

    private Node top=null;
    class Node{
        private Object data;
        private Node next;
        public Node(Object data,Node next) {
            this.data=data;
            this.next=next;
        }
    }
    @Override
    public void push(Object item) {
        //新节点为栈顶元素
        top=new Node(item, top);
    }

    @Override
    public Object pop() {
        Object item=peek();
        top=top.next;
        return item;
    }

    @Override
    public Object peek() {
        if(top==null)throw new NoSuchElementException("Stack is empty");
        return top.data;
    }

    @Override
    public int size() {
        int count=0;
        Node node=top;
        while(node!=null) {
            node=node.next;
            count++;
        }
        return count;
    }
    @Override
    public boolean isEmpty() {
        return top==null;
    }
    public static void main(String[] args) {
        LinkedStack stack=new LinkedStack();
        stack.push(100);//栈底
        stack.push(200);
        stack.push(300);//栈顶
        System.out.println(stack.size());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        //System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

如何基于栈实现表达式求值？

栈是一种重要的数据结构，而表达式求值是程序设计语言编译中的一个基本问题，编译系统通过栈对表达式进行语法分析、词法分析，最终获得正确的结果。例如，在使用栈进行表达式计算时，一般要设计两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。如图所示：

如何基于栈实现函数调用实践？

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

StackTraceElement[] stackTrace =
        Thread.currentThread().getStackTrace();

exception.printStackTrace();
1
2
3
4

如何基于栈实现括号匹配分析？

在进行括号匹配的语法校验时，可以用栈保存匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中。当扫描到右括号时，从栈顶取出一个左括号，如果两个括号能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。例如：

static boolean isMatching(String expression){
    Stack stack = new BoundedArrayStack(10) ;
    for(int index=0 ; index<expression.length();index++){
        char c=expression.charAt(index);
        switch(expression.charAt(index)){
            case '(':stack.push(c) ; break ;
            case '{':stack.push(c) ; break ;
            case ')':
                if(!stack.isEmpty()
                        &&stack.peek()==(Character)'(') {
                    stack.pop() ;
                }
                break ;
            case '}':
                if(!stack.isEmpty()
                        &&stack.peek()==(Character)'{'){
                    stack.pop();
                }
        }
    }
    if(stack.isEmpty())return true ;
    return false ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

手机APP中回退栈是如何应用的？

在android手机上我们每打开一个app都会创建一个回退栈，栈中存储每次打开的界面对象，新打开的UI界面会处于栈顶，当我们点击手机上的回退操作时，会移除栈顶元素，将后续元素作为栈顶，然后进行激活。

总结（Summary)