【数据结构和算法】栈—模拟实现Stack和栈相关算法题
文章目录
- 栈的定义
- Stack模拟实现
- 相关算法题
- 1.栈的压入弹出序列
- 2.逆波兰表达式(后缀表达式)⭐
- 1.什么是逆波兰表达式?
- 如何转换成逆波兰表达式
- 逆波兰表达式如何计算
- 3.有效的括号
- 总结
栈的定义
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出(先进后出)的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
在Java的集合类中栈是Stack
它的底层是一个数组,所以模拟实现就用数组来实现
当然栈分为顺序栈和链式栈,也可以使用链表的方式来实现
Stack模拟实现
Stack中有以上这些方法:
- push() :把数据压入堆栈顶部。
- pop() :移除堆栈顶部的对象，并作为此函数的值返回该对象。
- peek() :查看堆栈顶部的对象，但不从堆栈中移除它。
- empty() : 判断堆栈是否为空
- search() : 查找数据并返回对应的下标
import java.util.Arrays;
//数组实现栈
public class MyStack {
public int[] elem;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public MyStack() {
this.elem = new int[DEFAULT_SIZE];
}
/**
* 弹出
* @return
*/
public int pop(){
if(empty()){
throw new Myemptyexption("栈为空!");//自定义异常
}
return this.elem[--usedSize];
}
public boolean empty(){
if(this.usedSize == 0){
return true;
}
return false;
}
/**
* 压栈
* @return
*/
public int push(int val){
if(!isFull()){
this.elem = Arrays.copyOf(this.elem,2*elem.length);
}
this.elem[this.usedSize] = val;
this.usedSize++;
return val;
}
//判断数组是否满了
public boolean isFull(){
if(this.usedSize == this.elem.length){
return true;
}
return false;
}
/**
*返回栈顶元素
* @return
*/
public int peek(){
if(empty()){
throw new Myemptyexption("栈为空!");
}else{
return this.elem[usedSize-1];
}
}
/**
* 查找元素对应的下标
* @param val
* @return
*/
public int search(int val) {
for (int i = 0; i < usedSize; i++) {
if (this.elem[i] == val) {
return i;
}
}
return -1;
}
}
上面的代码是实现栈的主体部分,其中还用自定义异常
自定义异常代码如下:
public class Myemptyexption extends RuntimeException{
public Myemptyexption() {
super();
}
public Myemptyexption(String message) {
super(message);
}
}
运行并测试如图:
以上只是我自己模拟实现栈的想法,不一定和Stack底层源码的思路一样,大家如果要研究Stack的底层,还是建议去看官方源码
相关算法题
要真正掌握知识最重要还是刷题,接下来有几道栈相关的算法题,一起看看吧
1.栈的压入弹出序列
题目链接:传送门
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<=pushV[i]<=1000
- pushV 的所有数字均不相同
示例1:
输入：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
说明：
可以通过
push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true
示例2
输入： [1,2,3,4,5],[4,3,5,1,2]
返回值： false
说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false
解题思路:
创建一个栈,先将push数组中的元素依次进行入栈,入栈后栈顶元素要和pop数组的元素进行比较,如果相等就出栈,pop数组指向下一个元素,继续比较如果不相等再次入栈,直到结束.最后对栈进行判断如果空就为true 如果不为空就是false
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while(j < popA.length && !stack.empty() && stack.peek()==popA[j]){
j++;
stack.pop();
}
}
return stack.empty();
}
2.逆波兰表达式(后缀表达式)⭐
题目链接:传送门
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
1.什么是逆波兰表达式?
逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法
逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b) * (c+d)转换为ab+cd+ *
其中 (a+b) * (c+d) 这样的表达式是中缀表达式 ,而转换后的 ab+cd+* 是后缀表达式(逆波兰表达式)
如何转换成逆波兰表达式
先给大家介绍如何将中缀表达式转换为后缀表达式
最简单最粗暴的方式就是从左到右为每一步的运算加括号.如何改变运算符的位置
上面的式子大家可以逐个去除括号
先算的是 b*c 和 d/ f 所以 * 移到bc的后面 / 移到df的后面然后类似依次进行去除
逆波兰表达式如何计算
逆波兰表达式的计算就要用的栈了
方法如下: 将后缀表达式的数字进行入栈操作,然后遇到运算符就从栈里面弹出两个元素,再将计算好的数放回栈里面,以此类推
例如示例1的:2,1,+,3, *
2 1先入栈 然后是+ 1 2出栈进行相加为3 再入栈 下一个3也入栈 后面是* 因此两个3再出栈进行相乘 结果就为9
注意:在出栈时第一个数作为右操作数,第二个为左操作数 不能交换顺序,如果交换 运算符两侧的数就会变 ,此时如果是+ 的话结果不变 ,但如果不是结果就会出错
接下来就是用代码来实现计算过程了
代码实现:
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();
}
public boolean isOperation(String s){
if(s.equals("+") || s.equals("-") ||s.equals("*") ||s.equals("/")){
return true;
}
return false;
}
3.有效的括号
题目链接:传送门
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
解题思路:首先将元素进行入栈操作,从第二开始,入栈前要与栈顶元素进行匹配,如果能构成一个完成的括号,就出栈.因此如果字符串遍历完成,栈里面元素为空,就是匹配成功,
注意:因为这里是三个括号,不能通过左括号和右括号的数量进行判断
代码实现如下:
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 top = stack.peek();
if(ch==')'&&top=='(' || ch=='}'&&top=='{' || ch==']'&&top=='['){
//当前括号是匹配的 就出栈
stack.pop();
}else{
//不匹配
return false;
}
}
}
if(stack.empty()){
return true;
}else {
return false;
}
}
总结
- 栈的实现方式有很多种,我是用数组来实现的,也可以用链表来实现
- 栈虽然比较简单,但是它的算法题不一定简单,算法题还是建议多做几遍
- 中缀表达式如何转逆波兰表达式(后缀表达式),又如何去进行计算这部分要掌握(很重要)
