【数据结构】栈

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

栈-Stack

1. 什么是栈
2. 栈的使用
3. 栈的模拟实现
4. 栈的应用场景

1. 什么是栈

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

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

在这里插入图片描述

现实生活中也有很多栈的例子：
在这里插入图片描述

2. 栈的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

上述方法的实现：

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()); // 获取栈中有效元素个数---> 4System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3if (s.empty()) {System.out.println("栈空");} else {System.out.println(s.size());}}
}

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;}
}

4. 栈的应用场景

改变元素序列

若进栈序列为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，序列全部进栈，然后按照后进先出原则出栈。

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

//递归方式
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 + " ");}
}

括号匹配
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 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;}

逆波兰表达式求值
给你一个字符串数组 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;}