栈和队列常考面试题
面试题1:有效的括号（括号匹配问题）
解题思路分析如图：
代码示例1：
package java2021_1004;
import java.util.Stack;
/**
* Description:栈和队列面试题1:有效的括号（括号匹配问题）
*/
public class StackAndQueueInterviewQuestion1 {
public boolean isValid(String s) {
//1、先创建一个栈，栈中保存字符类型即可
/*泛型参数中不能使用内置类型，所以要写char对应的包装类Character*/
Stack<Character> stack=new Stack<>();
//2、循环遍历字符串中的每个字符
for(int i=0;i<s.length();i++) {//使用下标循环
char c = s.charAt(i);//取出当前字符
//3、判定c是否是左括号，如果是左括号，就入栈
if (c == '(' || c == '[' || c == '{') { //java中字符类型（char）用单引号，字符串（String）用双引号
stack.push(c);//如果是左括号，就入栈
continue;//进入下一次循环，取下一个字符
}
//在去栈顶元素之前先判断一下栈是否为空
if(stack.empty()){
return false;//如果发现当前字符不是左括号，并且栈又为空，此时也说明字符串非法
}
//4、判定c是否是右括号，如果是右括号，就取出栈顶元素来对比一下
Character top=stack.pop();//获取栈顶元素并取出来;pop方法是直接获取栈顶元素的方法;
//a)合法情况1
if(top=='(' && c==')'){
continue;
}
//b)合法情况2
if(top=='[' && c==']'){
continue;
}
//c)合法情况3
if(top=='{' && c=='}'){
continue;
}
//除了上面的三种合法情况，剩下的都是非法情况
return false;
}
//遍历完字符串之后还得看一下栈是否为空，空栈才能是合法的字符串
if(stack.empty()){
return true;//如果是空，合法，返或true
}
return false;//如果不是空，不合法，返或false
}
}代码示例2：将代码示例1中的合法情况1、2、3改成使用Map
package java2021_1004;
import java.util.*;
/**
* Description:将合法情况1、2、3改成使用Map
*/
public class UseMap {
public boolean isValid(String s) {
//创建一个Map,Map是键值对的结构，它有两个参数，将这两个参数都定义为Character
//把左右括号当成一个一个的键值对，其中key就是左括号，value表示该左括号匹配的右括号
Map<Character,Character> map=new HashMap<>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++) {//使用下标循环
char c = s.charAt(i);//取出当前字符
if (c == '(' || c == '[' || c == '{') {
stack.push(c);//如果是左括号，就入栈
continue;//进入下一次循环，取下一个字符
}
if(stack.empty()){
return false;//如果发现当前字符不是左括号，并且栈又为空，此时也说明字符串非法
}
Character top=stack.pop();//获取栈顶元素并取出来;pop方法是直接获取栈顶元素的方法;
if(map.get(top)==c){//将左括号拿出来，判断一下左括号是否等于右括号，如果相同就表明是合法的,
continue;
}
//map等于一开始给了一个标准答案，然后结尾直接判断。
return false;
}
if(stack.empty()){
return true;//如果是空，合法，返或true
}
return false;//如果不是空，不合法，返或false
}
}
/*在《代码大全》这本书中，专门有一个章节讨论了圈复杂度
* 即一段代码中如果if、while、for语句比较多，认为圈复杂度比较高，圈复杂度越高这个代码就越难理解。
* 可以使用（1）拆分函数
* （2）转移表的方式（也就是我们使用的map这样的方式，即把一个复杂的条件分支语句，转换成一个查表操作）*/
//拓展：对于比较相等，其他的各种引用类型都是下面这样的 ，而内置类型的==就是比较值
/*
==：比较身份
.equals:比较内容，只能比较相等
.compareTo:比较内容，能比较大小关系
*/
面试题2：用队列实现栈
疑问：基于队列实现栈该如何实现呢？
基本过程分析：
可以使用两个队列来模拟实现一个栈的效果，因为，队列是先进先出，栈是先进后出，要想用队列实现栈需要实现先进后出的操作，在一个队列中是无法让先进来的后出去的，所以此时就需要一个辅助队列来帮助完成这样的操作，将A队列中除最后一个元素外都倒腾到B队列中，此时就可以让后进来的先出去了。
- 入栈：把新的元素往A队列中入队即可
- 出栈：把A队列中的元素往B队列中倒腾（即把A队列中的元素依次出队列，出队列之后入到B队列，直到当A中就剩一个元素的时候，就不用入到B队列中了，直接出队列即可，不需要计数了，此时就把最后进来的这个元素删掉了。）
◇完成以上操作之后，交换A队列和B队列的身份，让A队列始终保持是入队列的（即保证新入栈的元素始终是往A中入）。
- 取栈顶元素：和出栈类似，但是出栈的时候是把最后一个元素给删掉，而取栈顶元素的最后一个元素是不能删的
- 判定为空：当A和B都为空，此时就表明这个栈为空。
package java2021_1004;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
/**
* Description:栈和队列面试题2:用队列实现栈
*/
public class StackAndQueueInterviewQuestion2 {
//1、先创建两个队列A和B
private Queue<Integer> A=new LinkedList<>(); // Queue是一个接口，所以不能直接new Queue这样的实例,所以要使用实现Queue接口的类LinkedList
private Queue<Integer> B=new LinkedList<>();
public void push(int x){//将元素 x 压入栈顶
//把x往A中入队列即可
A.offer(x);
}
public Integer pop(){//移除并返回栈顶元素
if(empty()){//判断是否为空，如果为空就返回
return null;
}
//把A中的元素往B中倒腾
//依次出队列，放到B里面
while(A.size()>1){
Integer front=A.poll();//从A队列中取出队首元素放到ret中
B.offer(front);
}
//当循环结束之后，A中应该就是只有1个元素，这个元素就应该是被出栈的
int ret=A.poll();// 将这一个元素从A中取出，并放到返回值里
//交换A和B的身份
swapAB();//调用交换AB的方法
return ret;
}
private void swapAB(){//写一个交换AB的方法
Queue<Integer> tmp=A;
A=B;
B=tmp;
}
public Integer top(){// 返回栈顶元素
if(empty()){//判断是否为空，如果为空就返回
return null;
}
//把A中的元素往B中倒腾
//依次出队列，放到B里面
while(A.size()>1){
Integer front=A.poll();//从A队列中取出队首元素放到ret中
B.offer(front);
}
//当循环结束之后，A中应该就是只剩1个元素了，这个元素就应该是被出栈的
int ret=A.poll();// 将最后剩的这一个元素从A中取出，加入到B中
B.offer(ret);
//交换A和B的身份
swapAB();//调用交换AB的方法
return ret;
}
public boolean empty(){//如果栈是空的，返回 true ；否则，返回 false
return A.isEmpty();
}
}面试题3：用栈实现队列
疑问：基于栈实现队列该如何实现呢？
可以使用两个栈来模拟实现队列的效果，
1、实现入队列：先把B中的所有元素倒腾到A中，然后直接往A中入栈即可。
2、实现出队列：先把A中的所有元素都倒腾到B中，然后对B进行出栈操作即可
3、去队首元素，先把A中的所有元素都倒腾到B中，然后取B的栈顶元素就是队首元素。
4、判空：A和B都为空，整个队列就是空了。
代码示例：
package java2021_1004;
import java.util.Stack;
/**
* Created by Sun
* Description:
* User:Administrator
* Date:2021-10-05
* Time:20:59
*/
public class StackAndQueueInterviewQuestion3 {
private Stack<Integer> A=new Stack<>();
private Stack<Integer> B=new Stack<>();
//《入队列》
public void push(int x){
//1、先把B中的元素都倒腾到A里
while(!B.isEmpty()){//如果B是非空的话，
int tmp=B.pop();//就从B里面取出元素
A.push(tmp);//然后把取出的元素放到A里
}//如果B为空，就直接往A里面插入元素即可
//2、再把新元素入A即可
A.push(x);
}
//如果刚进行完push操作，那么所有的元素一定都在A中
//如果刚进行完peek/pop操作，那么所有的元素一定都在B中
//元素存在A中的时候，相当于把队尾放在栈顶这一端，就可以操作队尾
//元素存在B中的时候，相当于把队首放在栈顶这一端，就可以操作队尾
//《出队列》
public Integer pop(){
//1、如果为空就直接返回
if(empty()){
return null;
}
//2、把A中的元素都倒腾给B
while(!A.isEmpty()){//如果A是非空的话，
int tmp=A.pop();//就从A里面取出元素
B.push(tmp);//然后把取出的元素放到B里
}
//3、针对B进行出栈
return B.pop();//返回的值就是当前的栈顶元素
}
public Integer peek(){
//1、如果为空就直接返回
if(empty()){
return null;
}
//2、把A中的元素都倒腾给B
while(!A.isEmpty()){//如果A是非空的话，
int tmp=A.pop();//就从A里面取出元素
B.push(tmp);//然后把取出的元素放到B里
}
//3、直接取B的栈顶元素
return B.peek();
}
public Boolean empty(){
return A.isEmpty() && B.isEmpty();//A和B都为空，整个队列就是空了
}
}面试题4：实现一个最小栈
问题描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
- 像最小栈这样的问题，要求O(1)获取最小值，只能用空间换时间。
- 创建两个栈一个叫栈A,一个叫栈B
- 实现入栈操作：对于A,直接入栈，对于B,取当前元素和B的栈顶元素比较，把较小值入栈。
- 实现出栈操作：对于栈A和栈B同时出栈
- 实现取栈顶元素：直接取A的栈顶元素
- 实现取最小值：直接取B的栈顶元素
代码：
package java2021_1004;
import java.util.Stack;
/**
* Created by Sun
* Description:栈和队列面试题2:实现一个最小栈
* User:Administrator
* Date:2021-10-06
* Time:8:44
*/
public class StackAndQueueInterviewQuestion4 {
//创建两个栈一个叫栈A,一个叫栈B
private Stack<Integer> A=new Stack<>();
private Stack<Integer> B=new Stack<>();
//1、实现入栈操作：对于A,直接入栈，对于B,取当前元素和B的栈顶元素比较，把较小值入栈。
public void push(int x){
A.push(x);
if(B.isEmpty()){//如果B为空，直接push
B.push(x);
return;
}
//B的栈顶元素本来就是A的最小值，当新来一个元素x的时候，就看看x和A的最小值比谁小，谁小谁就是新的最小值min。
int min=B.peek();//如果B不为空，就取出当前的最小值
if(x<min){//将当前栈B中的最小值min与当前栈A中的元素x进行比较
min=x;//如果x小，就把min更新成x,如果min小，那min就还是原来的值
}
B.push(min);//如果min小，那min就还是原来的值,然后将最小值min插入再到B里面
}
//2、实现出栈操作：对于栈A和栈B同时出栈,A和B要同进退
public Integer pop(){
if(A.isEmpty()){//判断栈A是否为空
return null;//如果为空就直接返回null
}
//将栈B中的元素和栈A中的元素都出栈，最终返回栈A中的元素
B.pop();
return A.pop();
}
//3、实现取栈顶元素：直接取A的栈顶元素
public Integer top(){
if(A.isEmpty()){
return null;
}
return A.peek();//如果不为空，直接取A的栈顶元素
}
//4、 实现取最小值：直接取B的栈顶元素
public Integer getMin(){
if(B.isEmpty()){
return null;
}
return B.peek();
}
}面试题5：设计循环队列
package java2021_1003;
/**
* Description:通过数组实现队列
*/
public class MyQueueArray {
//如果使用数组实现队列它的出队列效率太低，不太适合，所以可以使用循环队列的方式实现出队列操作
private int[] array=new int[100];
//有效元素的范围是[head,tail),注意，tail可能在head之前的情况
private int head=0;
private int tail=0;
private int size=0;//size表示元素个数
//写里面的操作
//进队列操作（插入元素）
public void offer(int val){
//先判断队列是否为满
if(size==array.length){
//此时表明队列满了，无法继续插入,直接返回
return;
}
//保证这个操作下标不能越界
array[tail]=val;//如果没满的话就把tail位置的元素赋成val
tail++;
if(tail>=array.length) {//如果tail++之后，超出了数组的有效范围，就从头开始
tail=0;
}
size++;//同时增加元素
}
//出队列操作
public Integer poll(){
//先判断size是否为0,如果等于0，就直接返回null队列
if(size==0){
return null;
}
//如果不是空队列
Integer ret=array[head];
head++;
if(head>=array.length){
head=0;
}
size--;//同时删除元素
return ret;
}
//取队首元素
public Integer peek(){
if(size==0){//判断队列是否为空
return null;
}
return array[head];//如果队首为null，直接返回head
}
}