面试题：通过队列实现栈
题目：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
栈的基本性质：后进先出
队列的基本性质：先进先出
解题思路：
创建两个队列qu1和qu2：
1.push(入栈)方法的实现：
若两个队列均为空，将待入栈的值(x) 通过队列提供的offer方法尾插到qu1中。
如果qu1不为空，将待入栈的值（x）通过offer方法尾插到qu1中
若qu2不为空，同理。
2.pop（出栈方法的实现）
出栈之前，通过empty方法判断qu1和qu2是否同时为空，为空，返回-1.
若qu1不为空，将qu1中前size-1个元素（通过队列的poll（出队列）方法获取qu1中的队头元素）尾插到qu2中，那么最后，qu1中队头元素即为要出栈的哪个元素，返回这个值即可。
若qu2不为空，同上。
3，top（得到栈顶元素）：
将不为空的那个队列通过for循环全部尾插到另一个队列中，最后一个尾插的元素即为栈顶元素。
具体步骤的实现：
1.基本结构的实现：
声明并初始化两个底层为链表的队列：qu1 和 qu2.（在构造方法中初始化）
代码如下：
class useQueueStack {
//声明两个队列
public Queue<Integer> qu1;
public Queue<Integer> qu2;
public useQueueStack() {
//初始化两个队列
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}2.push（入栈）功能的实现：
判断pu1和pu2的状态：qu1不为空，将x尾插到qu1中，qu2不为空，将x尾插到qu2中（通过队列的offer方法实现），若两个队列都为空，则将x尾插到qu1中。
具体代码如下：
//入栈功能的实现
public void push(int x) {
//若队列qu1不为空，将x尾插到qu1中
if (!qu1.isEmpty()) {
qu1.offer(x);
} else if (!qu2.isEmpty()) { //队列qu2不为空，将x尾插到qu2中
qu2.offer(x);
} else { //若两者都为空，将元素尾插到qu1中
qu1.offer(x);
}
}3.出栈(pop)功能的实现：
判断当前两个队列是否为空，若都为空，返回-1.
若qu1不为空，创建一个变量size来接受qu1长度，通过for循环，将qu1中前size-1个元素尾插到qu2中，则剩下的qu1中的元素，就是要出栈的那一个元素。
qu2同上。
以下时qu1不为空的例子：
具体代码如下：
public int pop() { //出栈方法的实现
if (empty()) { //判断两个队列是否都为空
return -1;
}
//如果qu1不为空，将qu1中的前size-1个元素尾插到qu2中，qu1中最后的那个元素即为栈顶元素
if (!qu1.isEmpty()) {
int size = qu1.size(); //获取qu1的长度
for (int i = 0; i < size - 1; i++) {
qu2.offer(qu1.poll());
}
return qu1.poll(); //返回qu1遗留的最后一个元素
} else {
//qu2不为空
int size = qu2.size();
for (int i = 0; i < size - 1; i++) {
qu1.offer(qu2.poll());
}
return qu2.poll();
}
}4.获取栈顶元素功能（top）的实现:
在获取栈顶元素之前，判断队列是否为空，如果两个元素都为空，返回-1，
若qu1不为空，可以通过for循环，利用pop（队列的出队方法）将qu1的队头元素依次全部尾插到qu2中，最后插入的元素即为要获取的栈顶元素。，返回最后一个尾插元素。
若qu2不为空，同上。
以下时qu1不为空的例子：
具体代码如下：
//获取栈顶元素
public int top() {
if (empty()) { //判断两个队列是否为空
return -1;
}
if(!qu1.isEmpty()){
int size = qu1.size();
int val = qu1.poll();//每次插入前将qu1栈顶元素赋给val
for (int i = 0; i < size; i++) {
qu2.offer(qu1.poll());
} //循环结束后最后一个插入的val即为栈顶元素
return val;
}else{
int size = qu2.size();
int val = qu2.poll()();
for (int i = 0; i < size; i++) {
qu1.offer(qu2.poll());
}
return val;
}
}5.判断两个队列是否为空的方法empty:
布尔类型的方法
判断qu1和qu2是否同时为空。
具体代码如下：
//当qu1和qu2均为空时
public boolean empty(){
return qu1.isEmpty() && qu2.isEmpty();
}
}
到这里，问题已经被解决了，喜欢的老铁来个三联吧！
原文地址：https://blog.csdn.net/kkksij/article/details/142644348
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！