队列
队列
队列的概念
队列是一种先进先出(First In First Out,FIFO)的线性数据结构,它只允许在队列的头部进行删除操作,而在队列的尾部进行插入操作。想象你在超市收银台前排队结账,这就是一个典型的队列。先来的人先结账(先进先出),新来的人必须排在队伍最后面,只有队伍最前面的人可以离开(结完账)。
队列的特点
-
元素按照进入的顺序排列
-
新元素总是添加到队尾
-
只有队首元素可以被移除
-
不支持随机访问
队列的声明与初始化
不同编程语言中,队列的声明和初始化语法略有不同,下面分别介绍几种常见语言的用法。(注:在实际使用中队列一般不要求初始化,即使要求也可以使用挨个入队的方式,所以初始化部分内容了解,知道可以这么使用,不要求完全掌握)
C++
在C++ 中,声明数组的基本语法如下:
//需要包含头文件<queue>
#include<queue>
std::queue<队列内元素的数据类型> 队列名称;
例如,如果声明一个包含整数的队列 q,可以这样写:
#include<queue>
std::queue<int>q;
//声明并初始化
std::vector<int> vec = {1, 2, 3};
std::queue<int, std::deque<int>> queueFromDeque(std::deque<int>(vec.begin(), vec.end()));
C++ 队列声明和初始化注意事项:
- std::queue默认使用deque作为底层容器,但也可以指定list
std::queue<int, std::list<int>> customQueue;
- 初始化陷阱
// 错误!这不是初始化队列元素的方式
std::queue<int> q = {1, 2, 3}; // 编译错误
Java
在Java中,声明队列的基本语法如下:
// 需要导入java.util包
import java.util.Queue;
import java.util.LinkedList;
Queue<队列内元素的数据类型> 队列名称 = new LinkedList<>();
例如,如果声明一个包含整数的队列q,可以这样写:
import java.util.Queue;
import java.util.LinkedList;
Queue<Integer> q = new LinkedList<>();
// 声明并初始化
Queue<Integer> initializedQueue = new LinkedList<>(Arrays.asList(1, 2, 3));
Java队列声明和初始化注意事项:
- Queue是接口,通常使用LinkedList或ArrayDeque实现
Queue<Integer> arrayDequeQueue = new ArrayDeque<>();
- 初始化陷阱
// 错误!不能直接这样初始化
Queue<Integer> q = {1, 2, 3}; // 编译错误
// 正确方式是通过集合初始化
Queue<Integer> q = new LinkedList<>(Arrays.asList(1, 2, 3));
Python
在Python中,声明队列的基本语法如下:
# 需要导入collections模块
from collections import deque
队列名称 = deque()
例如,如果声明一个包含整数的队列q,可以这样写:
from collections import deque
q = deque()
# 声明并初始化
initialized_queue = deque([1, 2, 3])
Python队列声明和初始化注意事项:
- 初始化陷阱
# 错误!这不是初始化队列的正确方式
q = deque(1, 2, 3) # 会报错
# 正确方式是通过可迭代对象初始化
q = deque([1, 2, 3])
- 类型自由:队列可以包含任意类型元素
q = deque()
q.append(1)
q.append("字符串")
队列的基本操作
C++
- 入队操作 - push()
myQueue.push(10); // 将10加入队尾
myQueue.push(20); // 将20加入队尾
myQueue.push(30); // 将30加入队尾
// 现在队列内容: 10(front) -> 20 -> 30(back)
- 出队操作 - pop()
myQueue.pop(); // 移除队首元素10
// 现在队列内容: 20(front) -> 30(back)
- 访问队首元素 - front()
int firstElement = myQueue.front(); // 获取队首元素20,但不移除
- 访问队尾元素 - back()
int lastElement = myQueue.back(); // 获取队尾元素30
- 检查队列是否为空 - empty()
if (myQueue.empty()) {
std::cout << "队列为空" << std::endl;
} else {
std::cout << "队列不为空" << std::endl;
}
- 获取队列大小 - size()
int queueSize = myQueue.size(); // 获取队列中元素个数
注意事项:
- 调用front()或back()前应先检查队列是否为空,否则可能导致未定义行为
- pop()操作只移除元素,不返回元素值
- C++标准库队列不支持随机访问,只能访问首尾元素
- 队列没有clear()方法,清空队列需要循环出队
Java
- 入队操作 - add()/offer()
myQueue.add(10); // 将10加入队尾
myQueue.offer(20); // 将20加入队尾
// 现在队列内容: 10(front) -> 20(back)
- 出队操作 - remove()/poll()
int first = myQueue.remove(); // 移除并返回队首元素10
// 现在队列内容: 20(front)
- 访问队首元素 - element()/peek()
int head = myQueue.peek(); // 获取队首元素20,但不移除
- 检查队列是否为空 - isEmpty()
if (myQueue.isEmpty()) {
System.out.println("队列为空");
} else {
System.out.println("队列不为空");
}
- 获取队列大小 - size()
int size = myQueue.size(); // 获取队列中元素个数
注意事项:
- 推荐使用offer()替代add(),poll()替代remove(),它们更友好
- peek()在空队列时返回null,element()会抛出异常
- Java队列没有直接访问队尾元素的方法
- LinkedList实现的队列允许null元素
Python
- 入队操作 - append()
my_queue.append(10) # 将10加入队尾
my_queue.append(20) # 将20加入队尾
# 现在队列内容: 10(front) -> 20(back)
- 出队操作 - popleft()
first = my_queue.popleft() # 移除并返回队首元素10
# 现在队列内容: 20(front)
- 访问队首元素
head = my_queue[0] # 获取队首元素20,但不移除
- 访问队尾元素
tail = my_queue[-1] # 获取队尾元素
- 检查队列是否为空
if not my_queue:
print("队列为空")
else:
print("队列不为空")
- 获取队列大小
size = len(my_queue) # 获取队列中元素个数
注意事项:
- deque是双端队列,可以从两端操作
- 检查队列是否可以直接用if not my_queue
- 可以初始化时设置最大长度: deque(maxlen=5)
- 比list的pop(0)效率高很多
队列的应用
例题 1:【模版】队列
题意
实现一个队列支持队列的入队,出队,查询队首元素,查询队列元素个数
思路
声明一个队列,循环读入操作对其进行处理,并根据要求输出结果
#include<bits/stdc++.h> // 包含所有标准库头文件
using namespace std; // 使用标准命名空间
int main(){
queue<int> q; // 声明一个整数类型的队列q
int n; // 定义变量n,表示操作次数
cin >> n; // 输入操作次数n
// 循环处理n次操作
while(n--){
int x; // 定义变量x,表示操作类型
cin >> x; // 输入操作类型x
// 根据操作类型x执行不同操作
switch(x){
case 1: // 操作1:入队操作
int c; // 定义变量c,表示要入队的元素
cin >> c; // 输入要入队的元素c
q.push(c); // 将元素c加入队尾
break;
case 2: // 操作2:出队操作
if(q.empty()){ // 检查队列是否为空
cout << "ERR_CANNOT_POP" << endl; // 队列为空,无法出队
break;
}
q.pop(); // 队列不为空,移除队首元素
break;
case 3: // 操作3:查询队首元素
if(q.empty()){ // 检查队列是否为空
cout << "ERR_CANNOT_QUERY" << endl; // 队列为空,无法查询
break;
}
cout << q.front() << endl; // 队列不为空,输出队首元素
break;
case 4: // 操作4:查询队列大小
cout << q.size() << endl; // 输出队列中元素的数量
break;
}
}
return 0; // 程序正常结束
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 初始化一个整数队列,使用LinkedList实现
Queue<Integer> q = new LinkedList<>();
// 创建Scanner对象用于读取输入
Scanner sc = new Scanner(System.in);
// 读取操作次数n
int n = sc.nextInt();
// 循环处理n个操作
while (n-- > 0) {
// 读取操作类型x
int x = sc.nextInt();
// 根据操作类型执行相应操作
switch (x) {
case 1: // 入队操作
// 读取要入队的元素c
int c = sc.nextInt();
// 将元素c加入队尾
q.add(c);
break;
case 2: // 出队操作
if (q.isEmpty()) {
// 队列为空时输出错误信息
System.out.println("ERR_CANNOT_POP");
} else {
// 移除队首元素
q.poll();
}
break;
case 3: // 查询队首元素
if (q.isEmpty()) {
// 队列为空时输出错误信息
System.out.println("ERR_CANNOT_QUERY");
} else {
// 获取但不移除队首元素并输出
System.out.println(q.peek());
}
break;
case 4: // 查询队列大小
// 输出队列当前元素数量
System.out.println(q.size());
break;
}
}
// 关闭Scanner对象释放资源
sc.close();
}
}
from collections import deque
import sys
def main():
# 初始化双端队列作为队列使用
q = deque()
# 读取所有输入行
lines = sys.stdin.read().split()
ptr = 0 # 指针跟踪当前读取位置
# 读取操作次数n
n = int(lines[ptr])
ptr += 1
# 循环处理n个操作
for _ in range(n):
# 读取操作类型x
x = int(lines[ptr])
ptr += 1
if x == 1: # 入队操作
# 读取要入队的元素c
c = int(lines[ptr])
ptr += 1
# 将元素c加入队尾
q.append(c)
elif x == 2: # 出队操作
if not q:
# 队列为空时输出错误信息
print("ERR_CANNOT_POP")
else:
# 移除队首元素
q.popleft()
elif x == 3: # 查询队首元素
if not q:
# 队列为空时输出错误信息
print("ERR_CANNOT_QUERY")
else:
# 获取但不移除队首元素并输出
print(q[0])
elif x == 4: # 查询队列大小
# 输出队列当前元素数量
print(len(q))
if __name__ == "__main__":
main()
队列优缺点
优点
- 元素出队顺序严格遵循入队顺序
- 提供O(1)时间复杂度的基本操作
缺点
- 无法直接访问中间元素
- 不支持复杂操作(如排序、查找),需借助其他数据结构
课后习题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋,学海无涯。<br/> 内含算法知识点讲解,以及牛客题库精选例题。<br/> 学习算法,从牛栋开始。