剑指Offer:用两个栈实现队列

题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

分析

我们通过一个具体的例子来分析队列中插入和删除元素的过程。首先插入元素a(插入到stack1中),接着再往stack1中插入两个元素b和c。此时stack中元素有{a,b,c},c为栈顶元素。此时stack2为空

这时我们试着从队列中删除一个元素,按照队列先入先出的规则,最先被删除的应该是a。但是元素a储存在stack1中且不是栈顶元素,因此不能直接删除。

这时如果我们把,stack1中的元素逐个弹出并压入stack2中,则stack2中元素的顺序正好和stack1中的元素顺序相反,这时就可以弹出stack2中的栈顶元素a了,此时stack1为空。

如果我们还想继续删除队列中的元素,stack2中剩下的元素的出栈顺序正好符合队列的出队顺序。

由上我们可以看出,当stack2不为空时,stack2中的栈顶元素就是最先进入队列的元素,可以弹出。当stack2为空时,酒吧stack1中的元素逐个弹出并压入stack2.由于先进队列的元素被压到stack1的底端,经过弹出和压入操作之后就处于stack2的顶部,可以弹出。

具体过程如下图所示
)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}
public int pop() {
int node;
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
node = stack2.pop();
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
return node;
}
}
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%