Leetcode 232.用栈实现队列

232.用栈实现队列

题目

使用栈实现队列的下列操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

方法

方法1:两个栈Push 每个操作O(N),Pop 每个操作O(1)

队列是先进先出,栈是后进后出。这意味着新元素加入到栈底。将s1的元素转移到辅助栈s2中。然后将新加入的元素push到栈s2,再将所有元素弹出并push到s1

push
新加入的元素必须压入到栈底。将s1的所有元素转换为辅助栈s2中。新加入的元素push到s2中,并且所有元素被s2 pop掉再push到s1.

  • 时间复杂度:每个新加入的元素,都被push和pop两次。最后一个加入的元素,pop和push依次。因此,当队列长度是n,操作次数是4n+2,push和pop复杂度是O(1)
  • 空间复杂度:O(n),需要额外的空间存储队列元素

pop
所有元素都是从栈s1 pop掉的。因为s1的栈顶总是第一个加入的元素front。队列的队头记作front

  • 时间复杂度和空间复杂度都是O(1)

empty
栈s1包含了所有的元素,所以只需要检查s1的size就可以得知队列是否为空

  • 时间复杂度和空间复杂度都是O(1)

peek
元素front总是保存在恒定的内存中,当push和pop才会改变

  • 时间复杂度和空间复杂度都是O(1)
  • front早就被计算,当peek时才返回
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(object):

def __init__(self):
"""
Initialize your data structure here.
"""
self.s1=[]
self.s2=[]

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
while self.s1:
self.s2.append(self.s1.pop())
self.s1.append(x)
while self.s2:
self.s1.append(self.s2.pop())

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
return self.s1.pop()


def peek(self):
"""
Get the front element.
:rtype: int
"""
return self.s1[-1]

def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not self.s1



# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

方法2:两个栈Push 每个操作O(1);Pop 每个操作O(1)

  • Push:新加入的元素总是被添加在s1的顶部,第一个元素始终作为队列的队头
  • Pop:队头元素在栈s1的栈底,要pop,只能将所有元素弹出并push到辅助栈s2(有助于存储s1的元素,以相反的顺序)。这样s1的栈底元素就位于s2的栈顶,此时可以简单的从s2弹出。当s2为空,再将s1的元素转移到s2
  • empty:栈s1和s2包含所有栈元素,检查s1和s2的size来判断队列是否为空
  • peek:当s2不空,队头元素位于s2的栈顶
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
class MyQueue(object):

def __init__(self):
"""
Initialize your data structure here.
"""
self.s1=[]
self.s2=[]

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.s1.append(x)

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
self.peek()
return self.s2.pop()


def peek(self):
"""
Get the front element.
:rtype: int
"""
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]

def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not self.s1 and not self.s2


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
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
52
53
class MyQueue(object):

def __init__(self):
"""
Initialize your data structure here.
"""
self.input=[]
self.output=[]

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.input.append(x)


def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
self.peek()
return self.output.pop()


def peek(self):
"""
Get the front element.
:rtype: int
"""
if self.output==[]:
while self.input!=[]:
self.output.append(self.input.pop())
return self.output[-1]


def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return self.input==[] and self.output==[]



# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()