【蓝桥杯冲击国赛计划第3天】队列

通过对链表的学习，我们基本已经把握到了数据结构的思想，能够清楚什么是数据结构，数据结构如何使用？链表算是数据结构中比较难的部分了，战胜了他，接下来我们学习的道路会非常好走。

单向链表

双向链表和循环链表

本文不使用队列的 api 进行解题，仅使用列表进行操作，因为这可以更进一步了解队列，日后刷题的时候，根据需要会用到队列的 api 的

1. 队列

1.1 概念

我们做核酸的时候需要排队，先排的先做，后排的后做，即先到先得。

它的存储分为顺序存储和链式存储，顺序存储通过数组，在 python 中可以通过列表来实现，而我们本文的重点在顺序存储。

和做核酸排队一样，我们的队列从队尾进，队头出。

1.2 队列的定义

根据 python 列表进行定义（注意：这里并没有用到内置的队列，采用列表能帮助我们更了解队列）

queue = []
1

1.3 实例「CLZ 的银行普通队列」

我们还是通过这个实例来了解一下，队列的定义和使用。

题目描述

CLZ 银行只有两个接待窗口，VIP 窗口和普通窗口，VIP 用户进入 VIP 窗口排队，剩下的进入普通窗口排队。现有 M 次操作，操作有四种类型，如下：

• IN name V：表示一名叫 name 的用户到 VIP 窗口排队
• OUT V：表示 VIP 窗口队头的用户离开排队
• IN name N：表示一名叫 name 的用户到普通窗口排队
• OUT N：表示普通窗口队头的用户离开排队

求 M 次操作结束后 VIP 窗口队列和普通窗口队列中的姓名。

输入描述

第一行是一个整数 M（1≤M≤1000），表示一共有 M 次操作。

第二行到第 M+1 行输入操作，格式如下：

• IN name V
• OUT V
• IN name N
• OUT N

输出描述

输出 M 次操作后 VIP 窗口队列和普通窗口队列中的姓名（从头到尾），先输出 VIP 窗口队列后输出普通窗口队列。

输入输出样例

示例 1

输入

5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V
1
2
3
4
5
6

输出

Adel
CLZ
laozhao
1
2
3

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

1.4 简单分析

题目说了一大串，其实简单说就是有两个队列 VIP 队列 和 普通队列，连个队列经过一系列入队和出队的操作，最终，输出 VIP 队列 和 普通队列 还在排队的人。这里都是排队了，核心思想和队列也一样，所以使用队列来解题。

1.5 队列队头队尾的定义

队列可以由空列表来定义，然后队头和队尾一开始初始化为 0，队头为队列最前面的那个人，队尾为最后一个人的后一个（相当于虚拟的尾节点，所以队尾一定不在队列中），这样定义有个好处：队头 == 队尾时相当于队列为空，因为队头指向的值不在队列之中了。

# vip用户
Vqueue = []
Vhead = 0
Vtail = 0
# normal用户
Nqueue = []
Nhead = 0
Ntail = 0
1
2
3
4
5
6
7
8

1.6 入队

入队需要知道两个信息，谁入队和入哪个队。因此，我定义函数形参为 name 和 type，入队入的是队尾，这和列表操作的 append() 函数是一致的，因为 append 插入的值会在最后。

插入之后，队尾需要 +1，队头保持不变。这里有点要注意的地方，由于队尾相当于虚拟结点，相当于并没有实际空间，所以队尾插入新的结点后，会越过虚拟结点，简单理解就是：队尾一直在最后一个结点的后一个结点（虚拟结点）。

def inQueue(name,type): # 入队
    global Vqueue,Vhead,Vtail,Nqueue,Nhead,Ntail
    if type == 'V':
        Vqueue.append(name)
        Vtail +=1

    if type == 'N':
        Nqueue.append(name)
        Ntail +=1
1
2
3
4
5
6
7
8
9

1.7 取队头

直接取在 head 的值

def queueHead(type): # 取队头
    global Vqueue,Vhead,Vtail,Nqueue,Nhead,Ntail
    if type == 'V':
        return Vqueue[Vhead]

    if type == 'N':
        return Nqueue[Nhead]
1
2
3
4
5
6
7

1.8 出队

出队出的是队头，出队前一定要判定队列是否为空。刚才我们说过如果队头 == 队尾，相当于队列为空，因为队尾指向的是虚拟结点，那么队头和队尾相等的时候，相当于队列里没有元素。或者也可以这么说，队尾-队头的差值为队列中元素的个数。

我们头指针移动相当于出队的过程：

def outQueue(type): # 出队
    global Vqueue,Vhead,Vtail,Nqueue,Nhead,Ntail
    if type == 'V':
        if Vhead == Vtail:
            return None
        else:
            Vhead +=1

    if type == 'N':
        if Nhead == Ntail:
            return None
        else:
            Nhead +=1
1
2
3
4
5
6
7
8
9
10
11
12
13

1.9 主函数

我们经过题目中一系列输入操作，执行相应入队出队操作后。最后用循环打印 队头 到 队尾-1的元素即可。

if __name__ == '__main__':
    M = int(input())
    for i in range(M):
        op = input().split()
        if op[0] == 'IN':
            inQueue(op[1],op[2])

        if op[0] == 'OUT':
            outQueue(op[1])
    for i in range(Vhead,Vtail):
        print(Vqueue[i])
    for i in range(Nhead,Ntail):
        print(Nqueue[i])
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 队列优化

2.1 概述

我们发现，之前通过队头和队尾的移动，最终得到了一整个队列，但是这个队列是属于我定义的队列的子集，所以空间的开销较大。而且，出队操作并没有真正出去，所以我们准备对队列进行优化，打造一个真正的队列。

2.2 一样的实例「CLZ 的银行普通队列」

题目描述

CLZ 银行只有两个接待窗口，VIP 窗口和普通窗口，VIP 用户进入 VIP 窗口排队，剩下的进入普通窗口排队。现有 M 次操作，操作有四种类型，如下：

• IN name V：表示一名叫 name 的用户到 VIP 窗口排队
• OUT V：表示 VIP 窗口队头的用户离开排队
• IN name N：表示一名叫 name 的用户到普通窗口排队
• OUT N：表示普通窗口队头的用户离开排队

求 M 次操作结束后 VIP 窗口队列和普通窗口队列中的姓名。

输入描述

第一行是一个整数 M（1≤M≤1000），表示一共有 M 次操作。

第二行到第 M+1 行输入操作，格式如下：

• IN name V
• OUT V
• IN name N
• OUT N

输出描述

输出 M 次操作后 VIP 窗口队列和普通窗口队列中的姓名（从头到尾），先输出 VIP 窗口队列后输出普通窗口队列。

输入输出样例

示例 1

输入

5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V
1
2
3
4
5
6

输出

Adel
CLZ
laozhao
1
2
3

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

2.3 定义队列

# vip用户
Vqueue = []

# normal用户
Nqueue = []
1
2
3
4
5

2.4 入队

仅仅只要判断类型和 append 即可

def inQueue(name,type): # 入队
    if type == 'V':
        Vqueue.append(name)

    if type == 'N':
        Nqueue.append(name)
1
2
3
4
5
6

2.5 取队头

队头就是队列中最前面的值，即下标为 0

def queueHead(type): # 取队头
    if type == 'V':
        return Vqueue[0]

    if type == 'N':
        return Nqueue[0]
1
2
3
4
5
6

2.6 出队

先判断出哪个队列，然后判断队列是否为空，不为空就出队头的元素（利用 pop() 函数移除指定位置的元素，由于队头位置为下标 0，所以 pop(0) 就可以移除队头元素了）

def outQueue(type): # 出队
    if type == 'V':
        if Vqueue:
            Vqueue.pop(0)
    if type == 'N':
        if Nqueue:
            Nqueue.pop(0)
1
2
3
4
5
6
7

2.7 主函数

现在的定义的队列为真正的队列，那么从头打印就可以了。

if __name__ == '__main__':
    M = int(input())
    for i in range(M):
        op = input().split()
        if op[0] == 'IN':
            inQueue(op[1],op[2])

        if op[0] == 'OUT':
            outQueue(op[1])
    for i in range(len(Vqueue)):
        print(Vqueue[i])
    for i in range(len(Nqueue)):
        print(Nqueue[i])
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 完整代码

可在 我的仓库免费查看，如果无法使用可以及时私信我或在评论区指出，谢谢。

本文主要参考蓝桥杯省赛14天夺奖冲刺营，有兴趣的可以自己在蓝桥杯官网搜索

如有错误，敬请指正，欢迎交流🤝，谢谢♪(･ω･)ﾉ