Implement the following operations of a stack using queues.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • empty() – Return whether the stack is empty.

Notes:

  • You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

思路

题目要求我们利用队列来实现栈的操作。

栈是先入先出，队列是先入后出。队列转栈的关键就是获得队列中的第一个元素——而队列中没有这样的内建函数。在设计的时候，我们可以利用两个队列来实现栈的功能。在实现栈的pop指令时，将第一个队列中除了第一个元素的所有元素都倒到第二个队列里。这样我们就取到了第一个队列中的第一个元素。

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
import Queue
class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q1 = Queue.Queue()
        self.q2 = Queue.Queue()
    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.q1.put(x)
    def pop(self):
        """
        :rtype: nothing
        """
        while(not self.q1.empty()):
            tmp = self.q1.get()
            if (not self.q1.empty()):
                self.q2.put(tmp)
        while(not self.q2.empty()):
            self.q1.put(self.q2.get())
    def top(self):
        """
        :rtype: int
        """
        tmp = 0
        while(not self.q1.empty()):
            tmp = self.q1.get()
            self.q2.put(tmp)
        while(not self.q2.empty()):
            self.q1.put(self.q2.get())
        return tmp
    def empty(self):
        """
        :rtype: bool
        """
        return self.q1.empty()