作者：爱塔居
专栏：数据结构
作者简介：大三学生，希望跟大家一起进步
目录
一、栈
1.1 概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
1.2 栈的使用
| 方法 | 功能 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e入栈，并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
1.3 示例
-
import java.util.Stack;
-
public
class
Test {
-
public
static
void
main
(String[] args) {
-
Stack<Integer> stack=
new
Stack<>();
-
stack.push(
1);
//压栈
-
stack.push(
2);
//压栈
-
System.out.println(stack.size());
//获取栈中有效元素元素
-
stack.pop();
//出栈
-
int b=stack.peek();
//获取栈顶元素
-
System.out.println(b);
-
}
-
}
二、栈的应用场景
2.1 改变元素的序列
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
2.2 逆波兰表达式求值
将中缀表达式"1+((2+3)*4)-5"转换为后缀表达式为:"1 2 3+4*+5-"
步骤：
全部括号分开：((1+((2+3)*4))-5)
把符号都移到对应的括号外面：
((1((23)+4)*)+5)-
删除所有括号：123+4*+5-
思路：遍历后缀表达式，只要是数字就入栈，是字符就弹出栈顶的两个元素，参与运算，最后把运算之后的结果，再次入栈。
-
class
Solution {
-
public
int
evalRPN
(String[] tokens) {
-
Stack<Integer> stack=
new
Stack<>();
-
for(String x:tokens){
-
if(!isOperation(x)){
-
stack.push(Integer.parseInt(x));
//不是运算符号，放入栈中
-
}
else{
-
int num2=stack.pop();
//如果是运算符号，把栈中两个元素出栈
-
int num1=stack.pop();
-
switch(x){
-
//判断运算符号，将出栈的两个数运算后，进栈
-
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();
-
}
-
//判断是否是运算符号
-
private
boolean
isOperation
(String x){
-
if(x.equals(
"+")||x.equals(
"-")||x.equals(
"*")||x.equals(
"/")){
-
return
true;
-
}
-
return
false;
-
}
-
}
2.3 括号匹配
思路：
左括号多：字符串遍历完成但是栈不空；
右括号多：字符串没完，栈空了;
不匹配;
-
class
Solution {
-
public
boolean
isValid
(String s) {
-
Stack<Character> stack=
new
Stack<>();
-
for(
int i=
0;i<s.length();i++){
-
char ch=s.charAt(i);
-
if(ch==
'('||ch==
'{'||ch==
'['){
-
stack.push(ch);
//如果是左括号，就进栈
-
}
else{
-
if(stack.empty()){
-
return
false;
//如果是右括号，栈为空，没有左括号匹配
-
}
-
char ch2=stack.peek();
//读取栈的栈顶元素，不出栈
-
if((ch2==
'('&&ch==
')')||(ch2==
'{'&&ch==
'}')||(ch2==
'['&&ch==
']')){
-
stack.pop();
//如果左右括号匹配，出栈
-
}
else{
-
return
false;
//不匹配
-
}
-
-
}
-
}
-
if(!stack.empty()){
//还有符号没匹配
-
return
false;
-
}
-
return
true;
-
}
-
}
2.4 栈的压入、弹出序列
- step 1：准备一个辅助栈，两个下标分别访问两个序列。
- step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
- step 3：栈顶等于出栈数组当前元素就出栈。
- step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。
-
import java.util.Stack;
-
public
class
Solution {
-
public
boolean
IsPopOrder
(int [] pushA, int [] popA) {
-
int n=pushA.length;
-
Stack<Integer> stack=
new
Stack<>();
-
int j=
0;
-
for(
int i=
0;i<n;i++){
-
while(j<n&&(stack.isEmpty()||stack.peek()!=popA[i])){
-
//入栈：栈为空或者栈顶不等于出栈数组
-
stack.push(pushA[j]);
-
j++;
-
}
-
if(stack.peek()==popA[i])
-
stack.pop();
-
else
-
return
false;
-
}
-
return
true;
-
}
-
}
-
转载：https://blog.csdn.net/m0_65683419/article/details/128817425
查看评论