栈和队列 OJ （一）
括号匹配问题
题目链接：
https://leetcode.cn/problems/valid-parentheses/
遇到左括号入栈，遇到右括号，我们就出栈看看括号是否匹配
这里要注意如果左括号多于右括号的情况下，字符串循环遍历结束时，栈不为空，所以循环结束后，最后我们要把栈是否为空保判断一下。
如果是右括号多余左括号的情况下，栈走到空的时候，字符串一定没有遍历完，所以在循环中判断括号是否匹配的时候，我们要注意栈是否为空这一个条件。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int len = s.length();
for(int i=0;i<len;i++) {
char str = s.charAt(i);
if(str == '(' || str == '[' || str == '{') {
//入栈
stack.push(str);
} else {
if(stack.empty()) {
return false;
} else if(!(isEquals(stack.pop(),str))) {
return false;
}
}
}
if(stack.empty()) {
return true;
}
return false;
}
private boolean isEquals(char ch1, char ch2) {
if((ch1 == '(' && ch2 == ')') ||
(ch1 == '[' && ch2 == ']') ||
(ch1 == '{' && ch2 == '}')) {
return true;
}
return false;
}
}
栈的压入、弹出序列
题目链接：
https://www.nowcoder.com/share/jump/9257752291720681998243
我们采用双指针的方法，i 遍历 入栈序列，j 遍历 出栈序列，当 i 和 j 所表示的元素相同时，进入出栈循环中，出栈要注意栈不能为空并且栈顶元素和 j 代表的元素要相同才能继续循环下去，否则 i 下标继续移动，直到 出栈序列完全遍历完。
在遍历入栈序列的时候，如果 i 和 j 所表示的元素不相同的话， i 所表示的元素直接入栈。
最后入栈序列遍历完成后，就可以判断 j 是否也遍历完出栈序列，没有则说明出栈序列不符合条件直接返回false，否则返回 true
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型一维数组
* @param popV int整型一维数组
* @return bool布尔型
*/
public boolean IsPopOrder (int[] pushV, int[] popV) {
// write code here
Stack<Integer> stack = new Stack<>();
int len1 = pushV.length;
int len2 = popV.length;
int j = 0;
int i = 0;
for(i=0;i<len1;i++) {
if(pushV[i] != popV[j]) {
stack.push(pushV[i]);
} else {
j++;
while(!stack.empty() && stack.peek() == popV[j]) {
j++;
stack.pop();
}
}
}
if(j < len2) {
return false;
}
return true;
}
}
逆波兰表达式
题目链接：
https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
首先介绍前缀，中缀，后缀表达式：
前缀表达式是指运算符在两个操作数前面，例如 1 + 1 转化为前缀表达式就变成 + 1 1，前缀表达式也叫波兰表达式
中缀表达式是指运算符在两个操作数中间，也就是我们经常使用的表达式的顺序，例如 1 + 1
后缀表达式是指运算符在两个操作数后面，例如 2 + 1 表示为 2 1 + ，后缀表达式也叫逆波兰表达式。
后缀表达式怎么转成中缀表达式？
从第一个元素开始找，直到遇到运算符，就从前面拿出两个操作数，分别为 第一个操作数和第二个操作数，将运算符放到它们中间，整合成新的式子作为操作数放回，以此类推，直到所有运算符找完为止，最后就会得到中缀表达式。
举个例子：
8 1 2 + 6 - *
首先遇到加号 ，拿出前两个操作数 ，将加号放在中间，即为 1 + 2 ，由于还没找完所有的运算符将式子放回去，即 8 （1 + 2 ）6 - *
接着遇到减号，还是一样，拿出前两个操作数，将减号放入二者之间，即 （1 + 2 ） - 6 ，由于还没找完所有的运算符将式子放回去，即 8 （ （1 + 2 ） - 6 ）*
最后遇到乘号，拿出前两个操作数，将乘号放入二者之间，即（ 8 * （ （1 + 2 ） - 6 ）），所有运算符找完，最后的式子就是中缀表达式。
回到代码题上，题目要求我们将逆波兰表达式的结果求出，那么我们就要将逆波兰表达式转化为中缀表达式，这时候可以使用栈这个数据结构，遍历整个数组，遇到运算符，出栈两次，第一次出栈是第二个操作数，第二次出栈是第一个操作数，将结果运算出来然后入栈。
如果没有遇到运算符的话，就要入栈，直到遇到运算符。
最后栈只会剩下一个元素，这个元素就是逆波兰表达式。
这里有一个方法要注意：字符串转整型可以使用包装类的Integer 里面的静态方法 parseInt(String s)
class Solution {
public int evalRPN(String[] tokens) {
int len = tokens.length;
Stack<Integer> stack = new Stack<>();
int val1 = 0;
int val2 = 0;
for(int i=0;i<len;i++) {
String ch = tokens[i];
switch(ch) {
case "+" :
val2 = stack.pop();
val1 = stack.pop();
stack.push(val1 + val2);
break;
case "-":
val2 = stack.pop();
val1 = stack.pop();
stack.push(val1 - val2);
break;
case "*":
val2 = stack.pop();
val1 = stack.pop();
stack.push(val1 * val2);
break;
case "/":
val2 = stack.pop();
val1 = stack.pop();
stack.push(val1 / val2);
break;
default:
stack.push(Integer.parseInt(ch));
break;
}
}
return stack.pop();
}
}
拓展
如何快速将中缀表达式转化为后缀表达式？
根据运算优先级先后给每两个操作数加括号
在每一个括号后面把里面的运算符给拉出来，之后删掉所有的括号即可
举个例子：
将中缀表达式 ( a + b ) * c - ( a + b ) / e 转化为后缀表达式
第一步：加括号
（ （ ( a + b ) * c ） - （ ( a + b ) / e ） ）
第二步： 拉出运算符
（ （ ( a b ) + c ） * （ ( a b ) + e ）/ ）-
第三步：去括号
a b + c * a b + e / - 这就是后缀表达式
最小栈
题目链接：
https://leetcode.cn/problems/min-stack/description/
题目要求我们即有普通栈的功能还能拥有找到最小数值的功能，并且在每次pop之后还是能在O（1）的条件下找到最新的最小值。这时候就需要用到辅助栈了，一个栈是正常使用，另一个栈专门存放最小值。
那第二个栈该怎么使用，因为题目要求我们在栈每次pop之后都能获取到剩下的元素的最小值，所以我们可以每次压栈的时候，就比较这个数据压栈后最新的最小值是多少，然后把这个最小值入栈即可，这样两个栈的元素总数是相同的，这样两个栈就可以同时进行push和pop操作了。
class MinStack {
public Stack<Integer> stack;
public Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(minStack.empty()) {
minStack.push(val);
} else {
int min = minStack.peek();
if(min > val) {
min = val;
}
minStack.push(min);
}
}
public void pop() {
minStack.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
设计循环队列
题目链接：
https://leetcode.cn/problems/design-circular-queue/description/
这里我使用顺序队列，因为顺序队列比链式队列好写
循环队列，我们可以使用牺牲一个空间的代价来实现循环：
当 rear == front 时队列为空，入队时使用 rear = ( rear + 1 ) % 数组长度 实现 rear 的移动，出队使用 front = ( front + 1 ) % 数组长度 实现 front 的移动，如果对这些式子不熟悉的，可以看一下我的博客文章JavaDS —— 栈 Stack 和 队列 Queue 里面有对循环队列的讲解
这里要格外的注意判断队列是否已满的方法，因为直接使用 rear + 1 == front 可能会发生一个情况，就是 rear 下一个数组就越界了，需要对准到正确的下标，即rear 此时为 数组长度-1 ，经过 +1 后就不会变成 0 而是变成数组的长度发生了越界，所以要使用 rear = ( rear + 1 ) % 数组长度 == front 判断队列是否已满
题目的要求是放入k 个数据，而我们的循环队列会牺牲一个空间，为了让队列能装下 k 个数据，所以我们在构造方法里要初始化 k+1 个空间的数组。
class MyCircularQueue {
int front;
int rear;
int[] elem;
public MyCircularQueue(int k) {
elem = new int[k+1];
}
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elem[rear] = value;
rear = (rear + 1) % elem.length;
return true;
}
public boolean deQueue() {
if(isEmpty()) {
return false;
}
front = (front + 1) % elem.length;
return true;
}
public int Front() {
if(isEmpty()) {
return -1;
}
return elem[front];
}
public int Rear() {
if(isEmpty()) {
return -1;
}
return elem[(rear-1+elem.length) % elem.length];
}
public boolean isEmpty() {
if(rear == front) {
return true;
}
return false;
}
public boolean isFull() {
if((rear + 1) % elem.length == front) {
return true;
}
return false;
}
}
用队列实现栈
题目链接：
https://leetcode.cn/problems/implement-stack-using-queues/
我们要使用两个队列来模拟栈，我们先回顾栈和队列：
选择我们来看一下队列怎么模拟出栈：
也就是说我们把一个有数据的队列先将元素出队，移动到另一个空队列上进行保存，然后还剩下最后一个元素直接出队就实现了模拟出队。
知道怎么出栈也就知道怎么模拟获取栈顶元素，这里不赘述。
现在我们来思考入栈怎么实现？
由于前面的出栈操作，我们就知道我们需要把所有的数据放在同一个队列上，保证一个队列是存放所有的数据，另一个队列为空队列，剩下的就交给你了。
什么时候是空栈？
显而易见，当两个队列均为空的时候就是空栈。
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
if(empty()) {
queue1.offer(x);
} else if(queue2.isEmpty()) {
queue1.offer(x);
} else {
queue2.offer(x);
}
}
private void offerAndPoll(Queue x, Queue y) { //x 有元素，y 为空队列
int size = x.size();
for(int i=0; i<size-1; i++) {
y.offer(x.poll());
}
}
public int pop() {
if(!queue1.isEmpty()) {
offerAndPoll(queue1,queue2);
return queue1.poll();
} else {
offerAndPoll(queue2,queue1);
return queue2.poll();
}
}
public int top() {
int ret = 0;
if(!queue1.isEmpty()) {
offerAndPoll(queue1,queue2);
ret = queue1.poll();
queue2.offer(ret);
} else {
offerAndPoll(queue2,queue1);
ret = queue2.poll();
queue1.offer(ret);
}
return ret;
}
public boolean empty() {
if(queue1.isEmpty() && queue2.isEmpty()) {
return true;
}
return false;
}
}
用栈实现队列
题目链接：
https://leetcode.cn/problems/implement-queue-using-stacks/description/
我们先看一下如何模拟出队：
假设此时进行入队 操作的话，会怎么样？
这时我们会发现stack2的顺序已经混乱，即使你加一个标记符，表示这时候如果进行出队的话，直接二号栈出栈即可，但是如果一直进行入队，你就很难判断二号栈接下来的模拟出队操作是出栈还是先将上面的元素移动到一号栈留下最后一个元素出栈，所以我们这里采用的是一号栈为主栈，二号栈为辅组栈，就是出队入队之后所有的元素最后都必须在一号栈上，二号栈只是用来辅助一号栈更好地完成出队或者获取队头信息的操作。
我们可以定义两个方法，一个方法是用于模拟出队或者获取队头元素的，也就是将一号栈留下栈底最后一个元素，其余元素全部移动到二号栈这个辅助栈上，另一个方法是用来善后的，即将二号栈所有的元素移动回一号栈上。
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
private void move(Stack x, Stack y) { // x 有元素， y 为空栈
int size = x.size() - 1;
for(int i=0; i<size; i++) {
y.push(x.pop());
}
}
private void moveAll(Stack x, Stack y) { // x 有元素， y 为空栈
int size = x.size();
for(int i=0; i<size; i++) {
y.push(x.pop());
}
}
public int pop() {
move(stack1,stack2);
int ret = stack1.pop();
moveAll(stack2,stack1);
return ret;
}
public int peek() {
move(stack1,stack2);
int ret = stack1.peek();
moveAll(stack2,stack1);
return ret;
}
public boolean empty() {
return stack1.empty();
}
}
原文地址：https://blog.csdn.net/liwuqianhzc/article/details/140351872
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！