概览
用栈实现队列
题目是:232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明:
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可
用队列实现栈
题目是:225. 用队列实现栈
请你仅使用两个队列实现一个后入先出(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(双端队列)来模拟一个队列 , 只要是标准的队列操作即可
力扣-232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
实现 MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
说明:
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]
解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示:
1 <= x <= 9
- 最多调用
100
次push
、pop
、peek
和empty
- 假设所有操作都是有效的 (例如,一个空的队列不会调用
pop
或者peek
操作)
进阶:
- 你能否实现每个操作均摊时间复杂度为
O(1)
的队列?换句话说,执行n
个操作的总时间复杂度为O(n)
,即使其中一个操作可能花费较长时间。
解法1:我自己写的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MyQueue {
int N = 100;
int[] stack1 = new int[N], stack2 = new int[N];
int size1, size2;
public MyQueue() {
size1 = size2 = 0;
}
public void push(int x) {
stack1[size1++] = x;
}
public int pop() {
if (size2 != 0)
return stack2[--size2];
if (size1 == 0)
return 0;// 注意 1 <= x <= 9 所以x=0就是代表没有元素了
for (int i = size1 - 1; i >= 0; i--) {
stack2[size2++] = stack1[i];
size1--;
}
return stack2[--size2];
}
public int peek() {
if (size2 != 0)
return stack2[size2 - 1];
if (size1 == 0)
return 0; // 注意 1 <= x <= 9 所以x=0就是代表没有元素了
for (int i = size1 - 1; i >= 0; i--) {
stack2[size2++] = stack1[i];
size1--;
}
return stack2[size2 - 1];
}
public boolean empty() {
return size1 == 0 && size2 == 0;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
分析:
-
push每次加一个数时间为 O(1)。
-
当 stack2 为空且需要 pop 或 peek 时,stack1 中的所有元素会被转移到 stack2,时间为 O(n)。但转移后,stack1 变空,stack2 包含所有元素(以相反顺序)。
关键点:每个元素最多被转移一次——从 stack1 到 stack2。一旦转移到 stack2,它要么被弹出,要么留在那里直到队列变空。
-
考虑一个包含 n 个操作的序列(例如 n/2 次 push 和 n/2 次 pop):
- n/2 次 push:总时间 O(n/2) = O(n)
- 转移操作:假设所有元素都在某个时刻转移,总共转移 n/2 个元素,花费 O(n/2) = O(n)
- n/2 次 pop:如果转移发生在某一次 pop,则那次操作花费 O(n),但之后每次 pop 都是 O(1),因为 stack2 已填充
总时间:
- push:O(n)
- 转移(总和):O(n)
- pop 和 peek 从 stack2 取元素:O(n)
总时间为 O(n),n 个操作均摊下来每个操作 O(1)。
所以以上实现:这个队列实现每个操作的均摊时间复杂度为 O(1)。尽管单个 pop 或 peek 操作在最坏情况下可能是 O(n)(当需要转移所有元素时),但通过均摊分析,n 个操作的总时间复杂度为 O(n)。这种方法是经典的“双栈队列”实现,广泛认可其均摊 O(1) 的性能。
解法2:左神的代码
首先左神的思路也是2个栈倒,分为in和out两个栈,但是要注意:
- 只有out是空才能从in栈中倒到out中,不然会出错。(其实和我上面自己写的思路是一致的,当size2不为0的时候优先返回stack2中的值,当size2=0,那么再看size1,如果size1不为0,则从stack1倒入stack2,然后再pop或者peek,如果size1也等于0,说明此时这个逻辑队列就是空)
- 如果要倒数据(即从in栈倒到out栈),数据必须要全部倒完。(就是我上面自己写的思路,在pop以及peek中写的循环,i从size1-1到0,全部需要倒过去)
上面提到的关键的2点,在下面的inToOut
方法中都有体现了。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MyQueue {
private Stack<Integer> in;
private Stack<Integer> out;
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
// 用来倒数据的
// 从in栈,把数据倒入out栈
// 1) out空了,才能倒数据
// 2) 如果倒数据,in必须倒完
private void inToOut() {
if (out.empty()) {
while (!in.empty()) {
out.push(in.pop());
}
}
}
public void push(int x) {
in.push(x);
inToOut();
}
public int pop() {
inToOut();
return out.pop();
}
public int peek() {
inToOut();
return out.peek();
}
public boolean empty() {
return in.empty() && out.empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
分析时间复杂度:
每一个数,只有可能进in一次出in一次,进out一次出out一次,所以就是入栈和出栈4次,就是均摊O(1)
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出(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(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]
解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示:
1 <= x <= 9
- 最多调用
100
次push
、pop
、top
和empty
- 每次调用
pop
和top
都保证栈不为空
进阶:你能否仅用一个队列来实现栈。
解法1:临时队列+正式队列
先补充一个Java中LinkedList数据结构的API:
- poll():
- 移除并返回队列的头部元素。
- 如果队列为空,则返回 null。
- 不会抛出异常。
- remove():
- 移除并返回队列的头部元素。
- 如果队列为空,则抛出 NoSuchElementException 异常。
- 需要捕获异常或者在方法声明中throws该异常
先贴解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>(); // queue1是临时的
queue2 = new LinkedList<>(); // queue2是正式的
}
public void push(int x) {
queue1.add(x);
while (!queue2.isEmpty()) {
queue1.add(queue2.poll());
}
while (!queue1.isEmpty()) {
queue2.add(queue1.poll());
}
queue1.clear();
}
public int pop() {
return queue2.poll();
}
public int top() {
return queue2.peek();
}
public boolean empty() {
return queue2.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
思路是,queue1永远都是临时队列,queue2永远都是正式队列。
每次进来一个数x,先进入queue1,如果queue2是空的,说明此时逻辑栈迎接了第一个元素x,然后直接把x从queue1弹出,弹到queue2即可。如果queue2不是空,那么此时将queue2中的元素以此弹出,进入到queue1的尾巴中。这样就保证了后进先出。然后再将queue1中的元素捯饬到queue2中。每次取数(不管是pop还是peek都是从queue2中)。
解法2:一个队列实现栈
步骤:
- 将元素入列到队尾;
- 再将除队尾之外的所有元素移除并重写入列。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
queue.add(x);
// 除队尾之外的所有元素移除并重写入列
for (int i = queue.size() - 1; i > 0; i--) {
queue.add(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
解法3:双端队列实现栈
队尾入,队尾出
在 Java 中,双端队列(Double-Ended Queue,简称 Deque)是一个接口,定义在 java.util 包中。它扩展了 Queue 接口,提供了在队列两端(头部和尾部)添加、移除和检查元素的能力。
Java 中的双端队列由 Deque 接口定义,主要实现包括:
- ArrayDeque:循环数组实现,高效且常用。
- LinkedList:双向链表实现,功能丰富。
- ConcurrentLinkedDeque:并发安全的双向链表实现。
其中,ArrayDeque 是最推荐的通用实现,因其 O(1) 的均摊时间复杂度和优异的性能表现。
如果这道力扣225用ArrayDeque实现的话:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MyStack {
ArrayDeque<Integer> queue;
public MyStack() {
queue =new ArrayDeque<>();
}
public void push(int x) {
queue.addLast(x);
}
public int pop() {
return queue.pollLast();
}
public int top() {
return queue.peekLast();
}
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/