问题：用两个栈实现队列，要求队列包括方法：从尾部入队（插入元素）；从头部出队（删除元素）。

原理：

首先要理解一点，栈操作具有对称性。正确地说，栈操作具有½对称性。如何理解这一点？例如，把以字符串压人栈，然后弹出，会得带得到原先字符串序列的反序列。如果该反序列在进行上述的压栈出栈操作，就会得带字符串的最初序列。这个操作过程就像：把以平面图案，先旋转180°后再旋转180°，结果和原先的重合（对称）。

上述的操作过程实现如下。

先实现基本的栈结构，为了代码简介，这里不添加边界检测部分的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:

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

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

    def pop(self):
        if self.empty():
            return None
        return self._q.pop()

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

    def top(self):
        return self._q[-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
def push_string_to_stack(string):
    stack = Stack()
    for s in string:
        stack.push(s)
    return stack

def pop_string_from_stack(stack):
    string = []
    while not stack.empty():
        string.append(stack.pop())
    return ''.join(string)

def main():
    string = "I am LittleFeng"

    # 第一次旋转180°
    stack_1 = push_string_to_stack(string)
    string_1 = pop_string_from_stack(stack_1)
    print(string_1)

    # 第二次旋转180°
    stack_2 = push_string_to_stack(string_1)
    string_2 = pop_string_from_stack(stack_2)
    print(string_2)

输出结果

1
2
gneFelttiL ma I 
I am LittleFeng

假设现在有两栈：stack1和stack2。据栈操作的对称性，不难理解，一队列queue中的元素依次压人栈stack1后，从stack1的栈顶到栈底看，元素序列是原来队列的反序。如果把stack1中的元素依次弹出压人stack2后，从栈顶到栈底看，该序列和原先的队列queue的元素顺序是一样的。这就说明了，如果我们入队的时候往stack1中压人元素，出队时从stack2中弹出元素，那么弹出元素的序列就和压人stack1的序列一样了。这就解决了两个栈实现一个队列queue的问题。

但还有一些细节需要处理。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Queue:

    def __init__(self):
        self._s1 = Stack()
        self._s2 = Stack()

    def put(self, item):
        self._s1.push(item)
        
    def get(self):
        if self._s2.empty():
            while not self._s1.empty():
                item = self._s1.pop()
                self._s2.push(item)
        if self._s2.empty():
            return None
        return self._s2.pop()

    def length(self):
        return len(self._s1._q) + len(self._s2._q)

编写测试代码，这里不演示极端的测试用例。仅用于功能测试。

1
2
3
4
5
6
7
def test():
    q = Queue()
    for i in range(10):
        q.put(i)

    while q.length() != 0:
        print(q.get())

利用对称思路，我们甚至可以用四个、八个…栈实现一个队列。类似思路的问题，可参看两个栈实现队列（算法7）的启发式问题两个队列实现栈（算法7+）。

完。