队列的基础概念与经典题目（Leetcode题解-Python语言）

87 阅读 0 评论 58 点赞

我是靠谱客的博主跳跃御姐，这篇文章主要介绍队列的基础概念与经典题目（Leetcode题解-Python语言），现在分享给大家，希望可以做个参考。

队列是先入先出（后入后出）的数据结构，常用操作就 push 和 popleft，Python中用列表中的 pop(0) 或者 collection.deque的 popleft() 都可以。

普通队列

225. 用队列实现栈

复制代码

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

    def __init__(self):
        self.queue1 = []
        self.queue2 = []
        self.size = 0

    def push(self, x: int) -> None:
        self.size += 1
        self.queue1.append(x)

    def pop(self) -> int:
        # if self.empty():  题目中保证了不会 pop 空
        #     return None
        for _ in range(self.size-1):
            self.queue2.append(self.queue1.pop(0))
        self.size -= 1
        self.queue1, self.queue2 = self.queue2, self.queue1
        return self.queue2.pop(0)

    def top(self) -> int:
        # if self.empty():
        #     return None
        return self.queue1[-1]

    def empty(self) -> bool:
        return self.size == 0

题目要求用两个队列实现栈，很简单，push 的操作是一样的，只不过在 pop 的时候不能 pop 队列最后一个元素，而要一直 pop 队首元素到另一个队列，只剩下的那一个元素即为栈顶元素，弹出它即可。显然用一个队列也能实现：

复制代码

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

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

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        # if self.empty():
        #     return None
        for _ in range(len(self.queue)-1):
            self.queue.append(self.queue.pop(0))
        return self.queue.pop(0)

    def top(self) -> int:
        # if self.empty():
        #     return None
        return self.queue[-1]

    def empty(self) -> bool:
        return len(self.queue) == 0

346. 数据流中的移动平均值

复制代码

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

    def __init__(self, size: int):
        self.queue = []
        self.size = size
        self.sum = 0

    def next(self, val: int) -> float:
        if len(self.queue) < self.size:
            self.queue.append(val)
        else:
            self.sum -= self.queue[0]
            self.queue.pop(0)
            self.queue.append(val)
        self.sum += val
        return self.sum / len(self.queue)

这题是利用队列实现滑动窗口，窗口满了之后每次新加进来一个数 val，计数器 sum 就减去队首元素 queue[0]，然后加上 val 即可。

622. 设计循环队列

复制代码

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

    def __init__(self, k: int):
        self.front = 0
        self.rear = 0
        self.size = k+1
        self.queue = [0 for _ in range(k+1)]

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = value
            return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        else:
            self.front = (self.front + 1) % self.size
            return True

    def Front(self) -> int:
        return self.queue[(self.front + 1) % self.size] if not self.isEmpty() else -1

    def Rear(self) -> int:
        return self.queue[self.rear] if not self.isEmpty() else -1

    def isEmpty(self) -> bool:
        return self.front == self.rear

    def isFull(self) -> bool:
        return (self.rear + 1) % self.size  == self.front