队列和栈的Python实现

发表于 | 分类于

本文介绍队列、堆栈的基本概念以及使用Python实现这两种数据结构，以及实现如何使用队列实现栈的基本功能和如何使用栈实现队列的基本功能。

两个栈实现队列

入队：元素进栈A

出队：先判断栈B是否为空，为空则将栈A中的元素 pop 出来并 push 进栈B，再栈B出栈，如不为空，则栈B直接出栈

时间复杂度：入队O(1);出队O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class QueueWithTwoStacks:
    """
    两个栈实现队列
    """
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        elif not self.stack1:
            return None
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
1
2
3
4
testq = QueueWithTwoStacks()
testq.push(1)
testq.push(2)
testq.pop()
1

两个队列实现栈

进栈：元素入队列A

出栈：判断如果队列A只有一个元素，则直接出队。否则，把队A中的元素出队并入队B，直到队A中只有一个元素，再直接出队。为了下一次继续操作，互换队A和队B。

时间复杂度：入队O(1)；出队O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class StackWithTwoQueues:
    """
    两个队列实现栈
    """
    def __init__(self):
        self.queue1 = []
        self.queue2 = []
    def push(self, node):
        self.queue1.append(node)
    def pop(self):
        if len(self.queue1) == 0:
            return None
        while len(self.queue1) != 1:
            self.queue2.append(self.queue1.pop(0))
        self.queue1, self.queue2 = self.queue2, self.queue1 # 交换顺序
        return self.queue2.pop()
1
2
3
4
tests = StackWithTwoQueues()
tests.push(1)
tests.push(2)
tests.pop()
2