【数据结构】栈

⭐ 作者：小胡_不糊涂
🌱 作者主页：小胡_不糊涂的个人主页
📀 收录专栏：浅谈数据结构
💖 持续更文，关注博主少走弯路，谢谢大家支持 💖

1. 什么是栈

栈： 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守**LIFO(Last In First Out)**的原则

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

现实生活中也有很多栈的例子：

2. 栈的使用

上述方法的实现：

import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size()); // 获取栈中有效元素个数---> 4
        System.out.println(s.peek()); // 获取栈顶元素---> 4
        s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
        System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
        if (s.empty()) {
            System.out.println("栈空");
        } else {
            System.out.println(s.size());
        }
    }
}    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. 栈的模拟实现

从下图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

模拟实现栈：

public class MyStack{
    private int[] elem;
    private int usedSize;//可以存放数据元素的下标
    private static final int DEFAULT_CAPACITY = 10;//默认容量

    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
    }

    //入栈
    public void push(int x) {
        if(full()) {
            elem = Arrays.copyOf(elem,2*elem.length);//扩容
        }
        elem[usedSize] = x;
        usedSize++;
    }

    //判断栈满
    public boolean full() {
        if(usedSize == elem.length) {
            return true;
        }
        return false;
    }

    //出栈
    public int pop() {
        if(empty()) {
            throw new EmptyException("栈空了！");
        }
        int old = elem[usedSize-1];
        usedSize--;//相当于是删除
        return old;
    }

    //返回栈顶元素
    public int peek() {
        if(empty()) {
            throw new EmptyException("栈空了！");
        }
        return elem[usedSize-1];
    }

    //计算入栈元素长度
    public int size() {
        return usedSize;
    }

    //判断栈空
    public boolean empty() {
        return usedSize == 0;
    }
}
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

4. 栈的应用场景

1. 改变元素序列

1. 若进栈序列为1,2,3,4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
   A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
   2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。
   A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

第一题答案为C。在序列进栈时，也可以有元素出栈，于是出栈的序列就有：1,2,3,4;1,4,3,2;2,3,4,1;3,4,2,1等等。C选项中，3先出栈，栈顶元素变为2，1不可能先出。

第二题答案为B，序列全部进栈，然后按照后进先出原则出栈。

2. 将递归化为循环–逆序打印链表

//递归方式
void printList (Node head){
       if(null != head) {
            printList(head.next);
            System.out.print(head.val + " ");
       }
 }
// 循环方式
void printList (Node head){
      if (null == head) {
           return;
      }
      Stack<Node> s = new Stack<>();
	// 将链表中的结点保存在栈中
       Node cur = head;
       while (null != cur) {
             s.push(cur);
             cur = cur.next;
       }
 	// 将栈中的元素出栈
       while (!s.empty()) {
            System.out.print(s.pop().val + " ");
       }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3. 括号匹配
   给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s，判断字符串是否有效。
   有效字符串需满足：
   (1)左括号必须用相同类型的右括号闭合。
   (2)左括号必须以正确的顺序闭合。
   (3)每个右括号都有一个对应的相同类型的左括号。
   类似于：(([]{}))、{[()]}、([])、()[]{}…

解题思路：

代码实现：

public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch1=s.charAt(i);
            if(ch1=='(' || ch1=='[' || ch1=='{'){
                stack.push(ch1);
            }else{
                if(stack.empty()){
                    return false;//没有与右括号对应的元素
                }
                char ch2=stack.peek();
                if(ch2=='('&&ch1==')' ||ch2=='['&&ch1==']' || ch2=='{'&&ch1=='}'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        //遍历完数组后，若栈不为空，即匹配失败
        if(!stack.empty()){
            return false;
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4. 逆波兰表达式求值
   给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
   请你计算该表达式。返回一个表示表达式值的整数。

逆波兰表示法，是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

解题思路：

代码实现：

public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(String s:tokens){
            if(!isOperation(s)){
                stack.push(Integer.parseInt(s));
            }else{
            	//注意计算顺序与出栈顺序
                int num2=stack.pop();
                int num1=stack.pop();
                switch (s){
                    case "+":stack.push(num1+num2);break;
                    case "-":stack.push(num1-num2);break;
                    case "*":stack.push(num1*num2);break;
                    case "/":stack.push(num1/num2);break;
                }
            }
        }
        return stack.pop();
    }
    //判断是否运算符
    public boolean isOperation(String s){
        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
            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
24
25
26