一、队列简介

队列是一种操作受限的线性表，其限制为仅允许在表的一端插入，而在表的另一端进行删除。把进行插入的一端称为队尾（rear），把进行删除的一端称作队头或队首（front）。向队列中插入元素称为进队或入队，从队列中删除元素称为出队或离队。

队列的一个显著特点是：FIFO（First In First Out）。

队列需要实现的方法和栈一样：empty()、push(e)、pop() 和 gethead()。

二、顺序队列

采用顺序存储结构的队列称为顺序队。我们用列表 data 来存放队列中的元素，另外设置两个指针，队头指针为 front，队尾指针为 rear。

为简单起见，这里使用固定容量的列表：

front 指向队头元素的前一个位置，而 rear 正好指向队尾元素。

顺序队分为非循环队列和循环队列两种结构，下面先讨论非循环队列，并通过说明该类型队列的缺点引出循环队列。

2.1 非循环队列

初始时置 front 和 read 均为 -1，非循环队列的四要素如下：

• 队空条件：front == rear;
• 队满条件：rear = MaxSize - 1；
• 元素 $e$ 进队操作：rear 增加 1，并将 $e$ 放在该位置（进队的元素总是在尾部插入的）；
• 出队操作：front 增加 1，取出该位置的元素（出队的元素总是在队头出来的）。

非循环队列的架构如下：

class SqQueue:
    def __init__(self):
        self.__MaxSize = 100
        self.data = [None] * self.__MaxSize
        self.front = self.rear = -1
1
2
3
4
5

完整实现：

class SqQueue:

    def __init__(self):
        self.__MaxSize = 100
        self.data = [None] * self.__MaxSize
        self.front = self.rear = -1

    def empty(self):
        return self.front == self.rear

    def push(self, e):
        assert self.rear != self.__MaxSize - 1
        self.rear += 1
        self.data[self.rear] = e

    def pop(self):
        assert not self.empty()
        self.front += 1
        return self.data[self.front]

    def gethead(self):
        assert not self.empty()
        return self.data[self.front + 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

上述操作的时间复杂度均为 $\mathcal{O}(1)$。

2.2 循环队列

2.2.1 假溢出

在非循环队列中，元素进队时队尾指针 rear += 1，元素出队时有 front += 1。当队满，即 rear = MaxSize - 1 成立时，此时即使仍出队若干元素，改变的只是 front 的位置，而 rear 不变，即队满条件仍然成立。这种队列中有空位置但仍然满足队满条件的上溢出称为假溢出。也就是说，非循环队列存在假溢出现象。

为了克服假溢出，充分利用数组的存储空间，我们可以把 data 数组的前端和后端连接起来，形成一个循环数组，即把存储队列元素的表从逻辑上看成一个环，称为循环队列。

2.2.2 循环队列的架构

循环队列首尾相连，当队尾指针 rear = MaxSize - 1 时，再前进一个位置就到达 0，这可以利用求余运算进行实现：

• 队首指针：front = (front + 1) % MaxSize；
• 队尾指针：rear = (rear + 1) % MaxSize。

循环队列的队头指针和队尾指针初始时均指向 0（即真实位置，不像非循环队列的队头指针和队尾指针初始时均指向虚拟位置 -1）。有元素进队时，rear += 1，有元素出队时，front += 1。

从上图还能发现一个细节：队空和队满时均有 rear == front，那我们该如何判断队空呢？事实上我们需要添加一个约束，具体如下。

循环队列和非循环队列都需要通过 front 和 rear 来标识队列状态。我们知道，一个长度为 $m$ 的队列有以下 $m+1$ 种状态：

• 队空；
• 队中有一个元素；
• 队中有两个元素；
• $\cdots$；
• 队中有 $m$ 个元素（即队满）。

若采取 |front - rear| 的方式来标识循环队列的状态，因为 front 和 rear 的取值范围为 $0\sim m-1$，从而 |front - rear| 只有 $m$ 种取值。注意到 $m<m+1$，所以如果采用 |front - rear| 来区分队列状态的话，必定有两种状态不能区分。所以如果我们限制长度为 $m$ 的队列最多含有 $m-1$ 个元素的话，就可以使用 |front - rear| 去区分所有的队列状态了。

为什么是有两种状态不能区分而不是有一种？我们可以考虑最简单的情形，假设队列长度为 $1$，因此只有两种状态：队空，队中只有一个元素（即队满）。此时 |front - rear| 只有一种取值：$0$，我们无法通过该值来判断队列的具体状态。

在规定了循环队列最多含有 $m-1$ 个元素后，我们就可以使用 rear == front 来判定队空了。当队满时（即队列中含有 $m-1$ 个元素），一定有 (rear + 1) % MaxSize == front。于是我们得到循环队列的四要素：

• 队空条件：rear == front；
• 队满条件：(rear + 1) % MaxSize == front；
• 元素 $e$ 进队操作：rear = (rear + 1) % MaxSize，再将 $e$ 放在该位置；
• 出队操作：front = (front + 1) % MaxSize，取出该位置的元素。

2.2.3 循环队列的实现

完整实现如下：

class CSqQueue:

    def __init__(self):
        self.__MaxSize = 100
        self.data = [None] * self.__MaxSize
        self.front = self.rear = 0

    def empty(self):
        return self.front == self.rear

    def push(self, e):
        assert (self.rear + 1) % self.__MaxSize != self.front
        self.rear = (self.rear + 1) % self.__MaxSize
        self.data[self.rear] = e

    def pop(self):
        assert not self.empty()
        self.front = (self.front + 1) % self.__MaxSize
        return self.data[self.front]

    def gethead(self):
        assert not self.empty()
        return self.data[(self.front + 1) % self.__MaxSize]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

上述操作的时间复杂度均为 $\mathcal{O}(1)$。

三、链队

队列的链式存储结构简称链队。它是通过由结点构成的单链表进行实现的。此时只允许在单链表的表头进行删除操作，在单链表的表尾进行插入操作。

需要注意的是，这里的单链表是不带头结点的，并且需要两个指针来标识该单链表。其中 front 指向队首结点，rear 指向队尾结点。

基本架构如下：

class LinkNode:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


class LinkQueue:
    def __init__(self):
        self.front = None
        self.rear = None
1
2
3
4
5
6
7
8
9
10

链队的四要素如下：

• 队空条件：front == rear == None，不妨仅以 front == None 作为队空条件；
• 队满条件：只有在内存溢出时才会队满，所以不考虑；
• 元素 $e$ 进队操作：在单链表的末尾插入一个存放 $e$ 的结点，并让 rear 指向它；
• 出队操作：取出队首结点的 data 值并将其从链队中删除。

3.1 链队的完整实现

class LinkQueue:

    def __init__(self):
        self.front = None
        self.rear = None

    def empty(self):
        return self.front == None

    def push(self, e):
        s = LinkNode(e)
        if self.empty():
            self.front = self.rear = s
        else:
            self.rear.next = s
            self.rear = s

    def pop(self):
        assert not self.empty()
        if self.front == self.rear:
            e = self.front.data
            self.front = self.rear = None
        else:
            e = self.front.data
            self.front = self.front.next
        return e

    def gethead(self):
        assert not self.empty()
        return self.front.data
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

四、双端队列

双端队列（double-ended queue，简称deque）是在队列的基础上扩展而来的：

双端队列与队列一样，元素的逻辑关系也是线性关系，但队列只能在一端进队，另一端出队。而双端队列可以在两端进行进队和出队的操作，具有队列和栈的特性，使用起来更加灵活。

从零开始实现一个双端队列也非常简单，这里略去。事实上Python中提供了这样的数据结构：

from collections import deque
1

4.1 创建双端队列

直接创建一个空的双端队列：

q = deque()
1

q 为空，它是一个可动态扩展的双端队列。

创建一个固定长度的双端队列：

q = deque(maxlen=10)
1

此时 q 为空，但最大长度为 10。当有新元素加入且双端队列已满时，会自动移除最老的元素。

从列表中创建一个双端队列：

a = [1, 2, 3, 4, 5]
q = deque(a)
print(q)
# deque([1, 2, 3, 4, 5])
1
2
3
4

4.2 判空

deque 没有提供判空方法，可以使用 len(q) == 0 来判断双端队列是否为空，其时间复杂度是 $\mathcal{O}(1)$。

4.3 主要方法

一些例子：

q = deque([1, 2, 3, 4, 5])
q.append(6)
q.appendleft(0)
print(q)
# deque([0, 1, 2, 3, 4, 5, 6])

q.pop()
q.popleft()
print(q)
# deque([1, 2, 3, 4, 5])

q.extend([1, 2, 3])
q.extendleft([7, 8, 9])
print(q)
# deque([9, 8, 7, 1, 2, 3, 4, 5, 1, 2, 3])

q.remove(1)
print(q)
# deque([9, 8, 7, 2, 3, 4, 5, 1, 2, 3])
print(q.count(2))
# 2

q.reverse()
print(q)
# deque([3, 2, 1, 5, 4, 3, 2, 7, 8, 9])

q.rotate(3)
print(q)
# deque([7, 8, 9, 3, 2, 1, 5, 4, 3, 2])

q.clear()
print(q)
# deque([])
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

五、优先级队列

所谓优先级队列，就是指定队列中元素的优先级，优先级越大的元素越优先出队。普通队列可以看成一种特殊的优先级队列，进队越早优先级越高。

优先级队列通常用堆来实现，本系列的后续文章将会介绍，这里不再提及。

六、栈 $\leftrightarrow$ 队列

6.1 用队列实现栈

方法一：双队列实现

class MyStack:

    def __init__(self):
        self.q1 = collections.deque()
        self.q2 = collections.deque()  # 类似于临时变量temp的作用

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return not self.q1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二：单队列实现

class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        n = len(self.q)
        self.q.append(x)
        for _ in range(n):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

上述两种方法的时间复杂度和空间复杂度均相同。

6.2 用栈实现队列

我们只需把列表当作栈，然后用两个栈来实现即可。

class MyQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []
        self.front = None

    def push(self, x: int) -> None:
        if not self.s1: self.front = x
        self.s1.append(x)

    def pop(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
            self.front = None
        return self.s2.pop()

    def peek(self) -> int:
        return self.s2[-1] if self.s2 else self.front

    def empty(self) -> bool:
        return True if not self.s1 and not self.s2 else False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

七、LeetCode实战

7.1 LeetCode#387——字符串中的第一个唯一字符

方法一：队列

我们可以创建一个字典和一个队列。字典用来统计每个字符的索引，对于那些重复字符，字典会将其索引置为 $-1$。

遍历字符串时，我们先检查当前字符是否已经出现在字典中。如果没有出现，就将该字符和其对应的索引同时添加到字典和队列中（以元组的形式加入队列）。如果已经出现过，我们就将字典中该字符的索引置为 $-1$，同时不断检查队头元素，只要它在字典中的索引为 $-1$ 就弹出。最后得到的队头元素就是我们需要的第一个不重复的字符。

当然，队空时，代表没有不重复的字符。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        hashmap = dict()
        q = collections.deque()
        for i in range(len(s)):
            if s[i] not in hashmap:
                hashmap[s[i]] = i
                q.append((s[i], i))
            else:
                hashmap[s[i]] = -1
                while q and hashmap[q[0][0]] == -1:
                    q.popleft()
        return -1 if not q else q[0][1]
1
2
3
4
5
6
7
8
9
10
11
12
13

方法二：哈希表

该方法简单直观。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        freq = collections.Counter(s)
        for i in range(len(s)):
            if freq[s[i]] == 1:
                return i
        return -1
1
2
3
4
5
6
7