双队列实现栈
单个队列是无法实现栈的，双队列是可以的，如下分析（例如出栈）
注意：
- 哪个队列不为空就放入哪个将元素放入哪个队列
- 若两个都为空，任选一个队列放入即可
如下代码：
class MyStack {
public Queue<Integer> q1;
public Queue<Integer> q2;
public int usedSize;
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
//压栈
public void push(int x) {
//哪个队列不为空，往那里里面放，都为空就放q1
if(!q1.isEmpty()){
q1.offer(x);
}
else if(!q2.isEmpty()){
q2.offer(x);
}
else{
q1.offer(x);
}
usedSize++;
}
//出栈
public int pop() {
//哪个队列不为空，就从哪里取元素放到另一个队列里
if(empty()){
return -1;
}
if(!q1.isEmpty()){
//转移usedSize - 1个元素到另一个队列
//for(int i = 0; i < usedSize - 1; i++)//不能这样写，usedSize会随着出栈不断减少
int size = usedSize;
for(int i = 0; i < size - 1; i++){
q2.offer(q1.poll());
}
usedSize--;
return q1.poll();
}
else{
int size = usedSize;
for(int i = 0; i < size - 1; i++){
q1.offer(q2.poll());
}
usedSize--;
return q2.poll();
}
}
public int top() {
//哪个队列不为空，就从哪里取元素放到另一个队列里
if(empty()){
return -1;
}
int tmp = 0;
if(!q1.isEmpty()){
int size = usedSize;
for(int i = 0; i < size - 1; i++){
q2.offer(q1.poll());
}
tmp = q1.peek();
q2.offer(q1.poll());
}
else{
int size = usedSize;
for(int i = 0; i < size - 1; i++){
q1.offer(q2.poll());
}
tmp = q2.peek();
q1.offer(q2.poll());
}
return tmp;
}
//判空
public boolean empty() {
return usedSize == 0;
}
}双栈实现队列
单个栈是无法实现队列的，双栈是可以的，如下分析（例如出队）
注意：
- 出队之前一定要先检查s2中是否有元素，若有直接弹出即可，若没有再将s1全部压入s2中
- 检查队列首元素也是如此(peek)
代码如下：
class MyQueue {
public Stack<Integer> s1;//入栈
public Stack<Integer> s2;//出栈
public MyQueue() {
this.s1 = new Stack<>();
this.s2 = new Stack<>();
}
//进队
public void push(int x) {
s1.push(x);
}
//出队
public int pop() {
if(empty()) {
return -1;
}
//s2如同蓄水池，一旦要出队列，就全压s1
//前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
if(s2.empty()){
while(!s1.empty()) {
s2.push(s1.pop());
}
return s2.pop();
}
//如果s2里有元素，就直接弹出
return s2.pop();
}
public int peek() {
if(empty()) {
return -1;
}
//s2如同蓄水池，一旦要出队列，就全压s1
//前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
if(s2.empty()){
while(!s1.empty()) {
s2.push(s1.pop());
}
return s2.peek();
}
//如果s2里有元素，就直接弹出
return s2.peek();
}
public boolean empty() {
return s1.empty() && s2.empty();
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/129891.html
