Authored by Tony Feng
Created on April 12th, 2022
Last Modified on May 16th, 2022
Task 1 - Q09. 用两个栈实现队列
Question
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class CQueue:
def __init__(self):
self.que = []
self.tmp = [] # Buffer
def appendTail(self, value: int) -> None:
self.que.append(value)
def deleteHead(self) -> int:
# Reverse the order
while self.que:
self.tmp.append(self.que.pop())
head = self.tmp.pop() if self.tmp else -1
while self.tmp:
self.que.append(self.tmp.pop())
return head
|
Explanation
- Two Stacks: One is for storage and the other is for buffering.
- Time Complexity
appendTail: O(1)deleteHead: O(N)
- Space Complexity
appendTail: O(N)deleteHead: O(N)
Task 2 - Q30. 包含min函数的栈
Question
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
Solution 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
|
class MinStack:
def __init__(self):
self.stack = []
self.minVal = []
def push(self, x: int) -> None:
self.stack.append(x)
if self.minVal:
self.minVal.append(min(x, self.minVal[-1]))
else:
self.minVal.append(x)
def pop(self) -> None:
if self.stack:
self.stack.pop()
if self.minVal:
self.minVal.pop()
def top(self) -> int:
if self.stack:
return self.stack[-1]
if self.minVal:
return self.minVal[-1]
def min(self) -> int:
return self.minVal[-1]
|
Solution 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
|
class MinStack:
def __init__(self):
self.stack = []
def push(self, x: int) -> None:
if not self.stack:
self.stack.append((x, x))
else:
m = self.min()
r = min(m, x)
self.stack.append((x, r))
def pop(self) -> None:
if self.stack:
self.stack.pop()
def top(self) -> int:
if self.stack:
return self.stack[-1][0]
def min(self) -> int:
if self.stack:
return self.stack[-1][1]
|
Explanation
- Two Stacks: One is for storage and the other is for tracing the minimum value.
- Time Complexity: O(1)
- Space Complexity: O(N)