该算法推广自两个栈实现队列（算法7）。

问题：使用两个队列实现栈。

原理：

队列具有自身对称性。怎么理解？例如，你把一字符串按顺序把每个字符放到队列中，然后取出队列中的所有字符组合成新的字符串，该新字符串和旧的字符串相等。这样我们可以把队列看作是一个容器。如果有两个这样的队列queue1和queue2做容器，那么栈的操作过程如下：
（1）压栈：把元素加入到队列queue1中
（2）出栈：1. queue1为空，把其作为容器保存queue2的元素，保存过程中把queue2的最后一个元素弹出栈；2.queue2为空的情况一样。3.如果两对立均为空，栈为空。

实现：

队列的简单实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Queue:

    def __init__(self):
        self._q = []

    def empty(self):
        return len(self._q) == 0

    def push(self, item):
        self._q.append(item)

    def get(self):
        item = self._q[0]
        del self._q[0]
        return item

使用两个队列实现栈

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
class Stack:

    def __init__(self):
        self._q1 = Queue()
        self._q2 = Queue()
        self._top = None

    def empty(self):
        return self._q1.empty() and self._q1.empty()

    def push(self, item):
        self._q1.push(item)
        self._top = item

    def pop(self):
        if self._q1.empty():
            while not self._q2.empty():
                item = self._q2.get()
                if self._q2.empty():
                    return item
                else:
                    self._q1.push(item)
                    self._top = item
        else:
            while not self._q1.empty():
                item = self._q1.get()
                if self._q1.empty():
                    return item
                else:
                    self._q2.push(item)
                    self._top = item

    def top(self):
        if self.empty():
            return None
        return self._top

为了能快速（常数时间内）返回栈顶元素，我们使用_top变量来保存每次弹出和压栈后的栈顶元素。