栈Stack的认识

发表于 更新于 分类于 阅读次数：

栈Stack

  • 栈是一种线性结构
  • 相比数组，栈对应的操作是数组的子集
  • 只能从一端添加元素，也只能从同一端取出元素
  • 这一端称为栈顶
  • 栈是一种 后进先出 LIFO（Last In First Out）的数据结构

栈的应用

  • Undo操作（撤销）- 编辑器

在编辑器中输入“我 爱 学习”，即在栈内添加“我”，“爱”，“学习”三个元素，但输入错误为“我 不爱 学习”了，那么要正确输入，就要执行撤销功能，删除“学习”和“不爱”，即取出“学习”和“不爱”两个元素，然后添加元素“爱 学习”。

  • 系统调用栈 - 操作系统

栈 程序调用的系统栈

函数A执行到第2行时停止，执行子函数B，此时，在栈中添加一个A2来标记程序执行到此有一个停止；

函数B执行到第2行时停止，执行子函数C，此时，在栈中添加一个B2来标记程序执行到此有一个停止；

函数C执行完后，会查看系统的栈应该执行哪里，此时，在栈中存在A2、B2两个元素；

从栈中取出栈顶元素B2，即程序应该执行函数B的第3行，执行完函数B之后再查看系统栈；

从栈中取出栈顶元素A2，即程序应该执行函数A的第3行，执行完函数A之后再查看系统栈，发现栈是空的，那么此时的程序就执行完了。

  • 括号匹配 - 编译器

栈的实现

1
2
3
4
5
6
Stack<E>
int getSize();
boolean isEmpty();
void push(E e); //入栈
E pop();  //出栈
E peek(); //栈顶元素

源码在此

leetcode练习

第20题：Valid Parentheses

链接：https://leetcode-cn.com/problems/valid-parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //匹配左括号时，入栈
            if (c == '(' || c == '[' || c == '{') { 
                stack.push(c);
            } else {  //否则是右括号
                if (stack.isEmpty())  //栈是空时直接返回false
                    return false;
                char topChar = stack.pop();  //取出栈顶元素
                if (c == ')' && topChar != '(')  
                    return false;
                if (c == ']' && topChar != '[')
                    return false;
                if (c == '}' && topChar != '{')
                    return false;
            }
        }
        return stack.isEmpty(); //如果栈是空，则表示已匹配完，返回true，否则栈内有未匹配的括号，返回false
    }
}