【数据结构】——栈和链表的面试题详解
一、栈的面试题详解
1、20. 有效的括号 - 力扣（LeetCode）
我们先来列出来括号不匹配的几种情况：
- 左右括号不匹配
- 右括号多
- 左括号多
括号匹配的情况：
- 字符串遍历完成
- 栈为空
代码如下：
public boolean isValid(String s) {
//时间复杂度O(N),空间复杂度O(N)
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;
}
}2、150. 逆波兰表达式求值 - 力扣（LeetCode）
首先我们先来了解一下逆波兰表达式（也叫作后缀表达式）：
将这个式子转成逆波兰表达式：a + b * c + (d * e + f ) * g
- 我们先从左到右按照先乘除后加减的顺序进行加括号:( ( a + (b * c ) )+( ( (d * e) + f ) * g) )
- 把括号内的运算符放到对应括号的外面:( ( a ( b c ) * ) + ( ( (d e) * f ) + g)* ) +
- 再把括号去掉: a b c * + d e * f + g * +
完整代码:
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();
}
private boolean isOperation(String opera){
if(opera.equals("+") || opera.equals("-") || opera.equals("*") || opera.equals("/")){
return true;
}else{
return false;
}
}3、栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
这道题我们用栈来解决：
- 我们可以先定义一个栈用来存储元素,然后定义两个下标 i j 来遍历push数组和pop数组，
- 当push[i] != pop[j]时，将push[i]入栈，i++，j不变，然后在进行比较，
- 如果push[i] == pop[j]，那就弹出栈顶元素，直到栈为空，说明pop[ ]是该压栈序列的弹出序列：
完整代码：
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0){
return false;
}
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().equals(popA[j]) ){
stack.pop();
j++;
}
}
return stack.empty();
}
}二、队列面试题
1、225. 用队列实现栈 - 力扣（LeetCode）
分析：
- 首先我们要知道一个队列是无法实现栈的，所以我们要创建两个队列qu1和qu2
- 入栈时，入到不为空的队列中，出栈时，出不为空的队列(size - 1)个，
完整代码:
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public int usedSize;
public MyStack() {
queue1 = new LinkedList<>() ;
queue2 = new LinkedList<>();
}
//入栈
public void push(int x) {
if (!queue1.isEmpty()){
queue1.offer(x);
}else if (!queue2.isEmpty()){
queue2.offer(x);
}else {
//qu1和qu2都为空
queue1.offer(x);
}
usedSize++;
}
//出栈
public int pop() {
if (empty()){
return -1;
}
if (!queue1.isEmpty()){
int curSize = queue1.size();
for (int i = 0; i < curSize-1; i++) {
queue2.offer(queue1.poll());
}
usedSize--;
return queue1.poll();
}else {
int curSize = queue2.size();
for (int i = 0; i < curSize-1; i++) {
queue1.offer(queue2.poll());
}
usedSize--;
return queue2.poll();
}
}
//peek查看栈顶元素
public int top() {
if (empty()){
return -1;
}
if (!queue1.isEmpty()){
int curSize = queue1.size();
int ret = -1;
for (int i = 0; i < curSize; i++) {
ret = queue1.poll();
queue2.offer(ret);
}
return ret;
}else {
int curSize = queue2.size();
int ret = -1;
for (int i = 0; i < curSize; i++) {
ret = queue2.poll();
queue1.offer(ret);
}
return ret;
}
}
//
public boolean empty() {
return usedSize == 0;
}
}
2、232. 用栈实现队列 - 力扣（LeetCode）
同理也需要用两个栈来模拟实现队列：
class MyQueue {
Stack<Integer> s1;
Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if (empty()){
return -1;
}
if (s2.empty()){
//需要把s2里面的元素全部倒过来
while (!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if (empty()){
return -1;
}
if (s2.empty()){
//需要把s2里面的元素全部倒过来
while (!s1.empty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.empty() && s2.empty();
}
}3、155. 最小栈 - 力扣（LeetCode）
- 这个题的关键就是需要多创建一个栈用来存储相对小的值
- 当我们需要出栈的时候，除了出普通栈的元素之外，每次出的时候，都要和最小栈的栈顶元素进行比较如果相等，那么最小站=栈当中也要出栈，这样才能保证每次获取最小值的时候，正好在最小栈的栈顶！
- 最后得到最小值的时候就只需要弹出最小栈的栈顶元素：
class MinStack {
private Stack<Integer> s;//普通栈
private Stack<Integer> minStack;//维护当前栈的最小值
public MinStack() {
s = new Stack<>();
minStack = new Stack<>();
}
/**
* 入栈
* @param val
*/
public void push(int val) {
s.push(val);// 普通栈 必须放
if (minStack.empty()){
//也存一份到最小栈中
minStack.push(val);
}else {
int peekVal = minStack.peek();
if (val <= peekVal){
minStack.push(val);
}
}
}
/**
* 出栈
*/
public void pop() {
// if (s.pop().equals(minStack.peek())){
// minStack.pop();
// }
if (!s.empty()){
int popVal = s.pop();
int peekValMinS = minStack.peek();
if (peekValMinS == popVal){
minStack.pop();
}
}
}
public int top() {
if (!s.empty()){
return s.peek();
}
return -1;
}
public int getMin() {
if (!minStack.empty()){
return minStack.peek();
}
return -1;
}
}