【数据结构和算法】栈—模拟实现Stack和栈相关算法题
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
文章目录
栈的定义
栈作为一种数据结构是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出(先进后出)的原则存储数据先进入的数据被压入栈底最后的数据在栈顶需要读数据的时候从栈顶开始弹出数据最后一个数据被第一个读出来。
在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]的弹出顺序要求435必须在12前压入且12不能弹出但是这样压入的顺序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;
}
}
总结
- 栈的实现方式有很多种,我是用数组来实现的,也可以用链表来实现
- 栈虽然比较简单,但是它的算法题不一定简单,算法题还是建议多做几遍
- 中缀表达式如何转逆波兰表达式(后缀表达式),又如何去进行计算这部分要掌握(很重要)
