数据结构(Java实现)：栈和队列相关练习题题解

1. 题目链接

1. 括号匹配
2. 逆波兰表达式求值
3. 出栈入栈次序匹配
4. 最小栈
5. 设计循环队列
6. 用队列实现栈
7. 用栈实现队列

2. 题目解析

2.1 括号匹配

题目分析
可能遇到的情况如下：

1. 如果括号匹配成功，栈最终为空且字符串遍历完成。
2. 左括号和右括号不匹配。eg：[(])
3. 字符串还没遍历完，遇到右半边符号，栈就为空。eg：()))
4. 字符串遍历完成，但是栈中仍然存在左括号。eg：(()

我们使用条件判断语句将上面四种情况考虑到就可以解决这道题目了。

代码示例

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;}else {//取栈顶元素的左括号看和当前右括号是否匹配char chL = stack.peek();if(chL == '(' && ch == ')' || chL == '[' && ch == ']' || chL == '{' && ch == '}') {//匹配成功，出栈stack.pop();}else {//左括号和右括号不匹配return false;}}}}//字符串遍历完成，但是栈中仍然存在左括号return stack.empty();}
}

2.2 逆波兰表达式求值

题目分析
tips： 逆波兰表达式是一种机器易读的表达式，不需要加括号或者定义运算符优先级就可以正确的描述运算顺序12。它是一种后缀表达式，与中缀表达式相对应，例如中缀表达式 (1 + 2) * (3 + 4) 对应的逆波兰表达式为 ((1 2 +) (3 4 +) *)。
首先传入的字符串组存储的是符号和数字的字符串，根据上面逆波兰表达式的介绍，我们可以得知开始都是数字，然后当出现一个符号，再对前面的数组进行运算。因此我们可以使用栈来解决这道题，当字符串为数字串时入栈，然后如果遇到符号，出栈两个数字，先出的在运算符右边，后出的在运算符左边，再将运算结果入栈。最后经过一系列运算，栈内剩余的数字就是运算结果。
代码示例

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for(int i=0;i<tokens.length;i++){String c=tokens[i];if(!(c.equals("+")||c.equals("-")||c.equals("*")||c.equals("/"))){//字符串为数字串时入栈stack.push(Integer.valueOf(c));}else{//如果遇到符号，出栈两个数字Integer val2=stack.pop();//先出的在运算符右边Integer val1=stack.pop();//后出的在运算符左边switch(c){case "+":stack.push(val1+val2);//将运算结果入栈break;case "-":stack.push(val1-val2);//将运算结果入栈break;case "*":stack.push(val1*val2);//将运算结果入栈break;case "/":stack.push(val1/val2);//将运算结果入栈break;}}}//栈内剩余的数字就是运算结果return stack.pop();}
}

2.3 出栈入栈次序匹配

题目分析
首先遍历pushV数组，将pushV数组正常入栈。然后每入栈一个数，判断popV数组，当popV数组的元素跟栈顶元素相同时，就将入栈元素出栈。然后继续判断，直到popV数组的元素不等于栈顶元素或者popV数组越界或者栈中没有元素结束循环，继续将pushV数组入栈。最后pushV数组完成入栈和出栈，栈中没有元素就返回true；否则返回false。
代码示例

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack=new Stack<>();int j=0;for(int i=0;i<pushV.length;i++){//将pushV数组正常入栈stack.push(pushV[i]);//popV数组的元素不等于栈顶元素或者popV数组越界或者栈中没有元素结束循环while(!stack.empty()&&stack.peek()==popV[j]&&j<popV.length){//当popV数组的元素跟栈顶元素相同时，就将入栈元素出栈stack.pop();//遍历popV数组j++;}}//栈中没有元素就返回true；否则返回falsereturn stack.empty();}
}

2.4 最小栈

题目分析
存放元素的过程:push

1. 如果第一次存放元素，普通栈和最小栈都得存放。
2. 如果不是第一次存放的时候，普通栈肯定得放。如果元素小于等于最小栈的栈顶元素，最小栈才存放元素。

取元素的过程:pop() 返回值是普通栈的元素

1. 每次pop元素的时候，都需要判断pop的元素是不是和最小栈的栈顶元素一样。如果一样，最小栈也得pop。

top相当于peek()返回值是普通栈的值。
getMin() 获取最小值，最小栈的栈顶元素就为栈的最小值。
代码示例

class MinStack {Stack<Integer> s1;//普通栈Stack<Integer> s2;//最小栈public MinStack() {s1=new Stack<>();s2=new Stack<>();}//存放元素public void push(int val) {s1.push(val);//普通栈必须存放if(s2.empty()){//如果第一次，最小栈也要存放元素s2.push(val);}else{//不是第一次，元素小于等于最小栈的栈顶元素，最小栈才存放元素if(s2.peek()>=val){s2.push(val);}}}//取元素public void pop() {if(s1.empty()){//判空return;}int a=s1.pop();//判断pop的元素是不是和最小栈的栈顶元素一样if(a==s2.peek()){s2.pop();//如果一样，最小栈也得pop}}//相当于peek()返回值是普通栈的值public int top() {return s1.peek();}//获取最小值，最小栈的栈顶元素就为栈的最小值public int getMin() {return s2.peek();}
}

2.5 环形数组队列

题目分析
当队尾走到顺序表的尽头，此时我们一直让fist++或者last++可能会造成数组越界，我们可以在每次入队列或者出队列时加一个判断，当first==len或者last==len时让他们的下标设置为0,。我们也可以通过表达式来设置下标，first=(first+1)%len或者last=(last+1)%len，通过这个表达式就不用担心数组越界的问题了。

考虑完数组越界问题后，我们如何区分队列的空与满？单纯依靠头尾相遇并不能解决这个问题，因为环形链表头尾相遇时可能为空，也可能为满。我们有下面三种解决方案。题目：力扣循环队列。

1. 使用usedSize，当usedSize==len时就为满。代码示例

class MyCircularQueue {public int[] elem;//存放队列元素public int first;//队列头public int last;//队列尾public int usedSize;//元素个数//构造方法public MyCircularQueue(int k) {elem=new int[k];this.usedSize=0;this.first=0;this.last=0;}//入队列 public boolean enQueue(int value) {if(isFull()){//判满，如果队列满了返回falsereturn false;}//元素入队列elem[last]=value;//队尾位置往后移一个last=(last+1)%elem.length;//元素个数加1usedSize++;//成功入队列，返回truereturn true;}//出队列public boolean deQueue() {if(isEmpty()){//判空，如果队列为空返回falsereturn false;}//出队列直接让对头往后移动一个first=(first+1)%elem.length;//元素个数减1usedSize--;//出队列成功，返回truereturn true;}//看队头元素public int Front() {if(isEmpty()){//判空，如果为空返回-1return -1;}//不为空，first下标即为队头元素return elem[first];}//看队尾元素public int Rear() {if(isEmpty()){//判空，如果为空返回-1return -1;}int index;if(last==0) {//如果last为0，队尾元素下标就为elem.length-1index = elem.length-1;}else {//否则，队尾元素下标为last-1index = last-1;}//返回对应下标的元素return elem[index];}//判空public boolean isEmpty() {//如果usedSize为0，队列尾空return usedSize==0;}//判满public boolean isFull() {//如果usedSize等于数组长度队列为满return usedSize==elem.length;}
}

2. 使用一个boolean类型的标记，当队列为满，flag为true，否则为false。代码示例

class MyCircularQueue {public int[] elem;//存放队列元素public int first;//队列头public int last;//队列尾public boolean flag;//标记//构造方法public MyCircularQueue(int k) {elem=new int[k];this.flag=false;//flag为false时，队列不满this.first=0;this.last=0;}//入队列public boolean enQueue(int value) {if(isFull()){//判满，如果队列满了返回falsereturn false;}//元素入队列elem[last]=value;//队尾位置往后移一个last=(last+1)%elem.length;if(last==first){//入队列时，last走完一圈回到first队列就满了flag=true;}//成功入队列，返回truereturn true;}//出队列public boolean deQueue() {if(isEmpty()){//判空，如果队列为空返回falsereturn false;}//出队列直接让对头往后移动一个first=(first+1)%elem.length;flag=false;//出队列时，队列就不满，标志设为false//出队列成功，返回truereturn true;}//看队头元素public int Front() {if(isEmpty()){//判空，如果为空返回-1return -1;}//不为空，first下标即为队头元素return elem[first];}//看队尾元素public int Rear() {if(isEmpty()){//判空，如果为空返回-1return -1;}int index;if(last==0) {//如果last为0，队尾元素下标就为elem.length-1index = elem.length-1;}else {//否则，队尾元素下标为last-1index = last-1;}//返回对应下标的元素return elem[index];}//判空public boolean isEmpty() {//如果last==first且flag为false，队列为空return last==first&&!flag;}//判满public boolean isFull() {//如果队列为满，flag为truereturn flag;}
}

3. 浪费一个空间，当first+1==last时，为满。代码示例

class MyCircularQueue {public int[] elem;//存放队列元素public int first;//队列头public int last;//队列尾//构造方法public MyCircularQueue(int k) {//因为浪费了一个空间，所以为了保证能够存够k个元素就需要开辟k+1个空间elem=new int[k+1];this.first=0;//队头this.last=0;//队尾}//入队列public boolean enQueue(int value) {if(isFull()){//判满，如果队列满了返回falsereturn false;}//元素入队列elem[last]=value;//队尾位置往后移一个last=(last+1)%elem.length;//成功入队列，返回truereturn true;}//出队列public boolean deQueue() {if(isEmpty()){//判空，如果队列为空返回falsereturn false;}//出队列直接让对头往后移动一个first=(first+1)%elem.length;//出队列成功，返回truereturn true;}//看队头元素public int Front() {if(isEmpty()){//判空，如果为空返回-1return -1;}//不为空，first下标即为队头元素return elem[first];}//看队尾元素public int Rear() {if(isEmpty()){//判空，如果为空返回-1return -1;}int index;if(last==0) {//如果last为0，队尾元素下标就为elem.length-1index = elem.length-1;}else {//否则，队尾元素下标为last-1index = last-1;}//返回对应下标的元素return elem[index];}//判空public boolean isEmpty() {//头等于尾时为空return last==first;}public boolean isFull() {//浪费一个元素，尾的下一个为头就视为满return (last+1)%elem.length==first;}
}

2.6 用队列实现栈

题目分析
队列是按照顺序出队列和入队列，栈是后进先出。如果要用队列实现栈，就需要两个队列。当我们要出栈或者查看栈顶元素时，就需要查看队尾元素。此时就将队尾的元素往前的元素进入到另一个队列，此时就能实现栈。
代码示例

class MyStack {Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1=new LinkedList<>();q2=new LinkedList<>();}//入栈public void push(int x) {if(empty()){//如果队列都为空，就先将元素入队列1q1.offer(x);}else {//否则，判断哪个队列为空，将元素如不为空的那个队列if(q1.isEmpty()){q2.offer(x);}else {q1.offer(x);}}}//出栈public int pop() {if(empty()){//如果栈为空，返回-1return -1;}if(q1.isEmpty()){//如果队列1为空，将队尾的元素往前的元素进入到队列2while (q2.size()>1){q1.offer(q2.poll());}return q2.poll();//返回队尾元素，实现出栈}else {//如果队列2为空，将队尾的元素往前的元素进入到队列1while (q1.size()>1){q2.offer(q1.poll());}return q1.poll();//返回队尾元素，实现出栈}}//查看栈顶元素public int top() {if(empty()){//如果栈为空，返回-1return -1;}int ret;//返回值if(q1.isEmpty()){//如果队列1为空，将队尾的元素往前的元素进入到队列2while (q2.size()>1){q1.offer(q2.poll());}ret=q2.element();//返回队尾元素q1.offer(q2.poll());//将队尾元素入到另一个队列}else {//如果队列2为空，将队尾的元素往前的元素进入到队列1while (q1.size()>1){q2.offer(q1.poll());}ret=q1.element();//返回队尾元素q2.offer(q1.poll());//将队尾元素入到另一个队列}return ret;}//判空public boolean empty() {//队列1和队列2都为空，栈为空return q1.isEmpty()&&q2.isEmpty();}
}

2.7 用栈实现队列

题目分析
栈是后进先出，队列是按照顺序出队列和入队列。所以要用栈实现队列，就需要一个模拟入队列，一个模拟出队列。我们先创建两个栈，s1和s2，s1入队列使用，s2出队列使用。详细实现参照下面代码注释。

代码示例

class MyQueue {public Stack<Integer> s1;public Stack<Integer> s2;public MyQueue() {s1=new Stack<>();s2=new Stack<>();}//入队列public void push(int x) {while (!s2.isEmpty()){//将栈2的元素放入栈1，实现入队列s1.push(s2.pop());}s1.push(x);//将新元素入队列}public int pop() {if (empty()){//判空，如果队列为空返回-1return -1;}while (!s1.isEmpty()){//将栈1的元素放入栈2，实现出队列s2.push(s1.pop());}return s2.pop();//出队列}public int peek() {if (empty()){//判空，如果队列为空返回-1return -1;}while (!s1.isEmpty()){//将栈1的元素放入栈2，实现出队列s2.push(s1.pop());}return s2.peek();//查看队头元素}public boolean empty() {//当栈1和站2都为空，队列为空return s1.isEmpty()&&s2.isEmpty();}
}