两个栈实现一个队列

发表于

之前面试的时候被面试官问到一道算法题：如何用两个栈实现一个队列。我的回答是，把所有元素：入第一个栈 -> 从第一个栈出栈并入第二个栈 -> 从第二个栈出栈。当时无知，以为自己的回答是正确的，但是面试官接下来的问题便把我给打回原形了：如果想要队列是可以同时入队列和出队列的呢。

最近在学习《算法导论》，学习到了栈和队列这一章，又想起了上面的问题，便重新思考和 Coding 了一番，顺便记录一下。

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

从上面这段关于栈的介绍我们可以知道栈的基本特点：先入后出，后入先出（LIFO, Last In First Out）。

stack 图示

下面是用 Python 中的 list 实现的一个 Stack，主要依靠 self.top 这个变量来定位栈顶元素以及判断是否 stack overflow, stack underflow。

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 Stack(object):
    def __init__(self, length):
        self.S = [None for _ in range(length)]
        self.top = -1
    def stack_empty(self):
        if self.top == -1:
            return True
        else:
            return False
    def push(self, element):
        if self.top + 1 == len(self.S):
            raise IndexError('stack overflow')
        else:
            self.top = self.top + 1
            self.S[self.top] = element
    def pop(self):
        if self.stack_empty():
            raise IndexError('stack underflow')
        else:
            self.top = self.top - 1
            return self.S[self.top + 1]

队列

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的后端（Back）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

从上面这段关于队列的介绍我们可以知道队列的基本特点：先入先出（First-In-First-Out），后入后出。

queue 图示

下面是用 Python 中的 list 实现的一个 Queue，主要依靠 self.head, self.tail 这两个变量来定位的队列的队头（head），队尾（tail）以及判断是否 queue overflow, queue underflow。

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
class Queue(object):
    def __init__(self, length):
        self.Q = [None for _ in range(length)]
        self.head = 0
        self.tail = 0
        self.maxIndex = length - 1
    def enqueue(self, element):
        if self._isOverFlow():
            raise IndexError('queue overflow.')
        else:
            self.Q[self.tail] = element
            if self.tail == self.maxIndex:
                self.tail = 0
            else:
                self.tail += 1
    def dequeue(self):
        if self._isUnderFlow():
            raise IndexError('queue underflow.')
        else:
            result = self.Q[self.head]
            self.Q[self.head] = None
            if self.head == self.maxIndex:
                self.head = 0
            else:
                self.head += 1
            return result
    def _isOverFlow(self):
        return (self.head == self.tail) and self.Q[self.head]
    def _isUnderFlow(self):
        return (self.head == self.tail) and (not self.Q[self.head])
    def onlyOneElement(self):
        return (self.tail - self.head == 1) or (self.tail == 0 and self.head == self.maxIndex)

利用两个栈实现一个队列

介绍完基础知识终于可以开始进入主题了：如何利用两个栈实现一个队列？

只要利用好上面提到的栈和队列的基本特点就可以很轻松的想出解决方案：

  • 队列的入队：直接利用第一个栈的入栈操作来实现队列的入队。

  • 队列的出队：因为入队使用了非常简单的方式来实现，所以出队就需要稍微花点功夫了。

    1. 出队的时候，因为想要的是将第一个栈中的栈底元素出队，所以首先我们需要将第一个栈中除了栈底元素外的其他元素弹出栈并且进入第二个栈中。
    2. 然后将第一个栈的栈底元素返回即可。
    3. 当然，为了保证后续的入栈出栈操作都正确，所以在上一步拿到栈底元素返回之前，需要将第二个栈中的元素全部弹出栈并且进入第一个栈中。这样第一个栈前后的变化仅仅是失去了原来的栈底元素，队列也顺利的完成了出队操作。

下面是利用两个 Stack （具体实现在上面的第一片代码中） 实现 Queue 的代码。基本上就是按照上面提到的步骤实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from stack import Stack
class Queue(object):
    def __init__(self, length):
        self.stack1 = Stack(length)
        self.stack2 = Stack(length)
    def enqueue(self, element):
        try:
            self.stack1.push(element)
        except IndexError:
            raise IndexError('queue overflow.')
    def dequeue(self):
        while self.stack1.top > 0:
            self.stack2.push(self.stack1.pop())
        try:
            result = self.stack1.pop()
        except IndexError:
            raise IndexError('queue underflow.')
        while not self.stack2.stack_empty():
            self.stack1.push(self.stack2.pop())
        return result

利用两个队列实现一个栈

延伸一下，既然已经有了利用两个栈实现一个队列的思路，那么同样的按照这个思路走就能利用两个队列实现一个栈啦。

  • 入栈：利用两个队列中不为空的那一个队列的入队操作来实现栈的入栈。（如果两个都为空的话就随便哪一个）

  • 出栈：同样的，因为入栈使用了非常简单的方式来实现，所以出栈就需要稍微花点功夫了。（好像在哪里见过这句话？？？）

    1. 出栈的时候，因为想要的是不为空的那一个队列中的队尾元素出队，所以首先我们需要将该队列中除了队尾元素外的其他元素出队并且进入另一个为空的队列中。
    2. 然后将该队列的队尾元素返回即可。
    3. 嗯，利用两个队列实现一个栈没有第三步，不信你重复上面两步试试对不对。

下面是利用两个 Queue （具体实现在上面的第二片代码中） 实现 Stack 的代码：

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
from queue import Queue
class Stack(object):
    def __init__(self, length):
        self.queue1 = Queue(length)
        self.queue2 = Queue(length)
        self.usingQueue1Push = True
    def push(self, element):
        try:
            if self.usingQueue1Push:
                self.queue1.enqueue(element)
            else:
                self.queue2.enqueue(element)
        except IndexError:
            raise IndexError('stack overflow.')
    def pop(self):
        try:
            if self.usingQueue1Push:
                while not self.queue1.onlyOneElement():
                    self.queue2.enqueue(self.queue1.dequeue())
                result = self.queue1.dequeue()
            else:
                while not self.queue2.onlyOneElement():
                    self.queue1.enqueue(self.queue2.dequeue())
                result = self.queue2.dequeue()
        except IndexError:
            raise IndexError('stack underflow.')
        self.usingQueue1Push = not self.usingQueue1Push
        return result

源码地址：Two stacks implement the queue.

全文完

感谢阅读