队列

队列

队列的概念

队列是一种先进先出(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++

  1. 入队操作 - push()
myQueue.push(10);  // 将10加入队尾
myQueue.push(20);  // 将20加入队尾
myQueue.push(30);  // 将30加入队尾
// 现在队列内容: 10(front) -> 20 -> 30(back)
  1. 出队操作 - pop()
myQueue.pop();  // 移除队首元素10
// 现在队列内容: 20(front) -> 30(back)
  1. 访问队首元素 - front()
int firstElement = myQueue.front();  // 获取队首元素20,但不移除
  1. 访问队尾元素 - back()
int lastElement = myQueue.back();  // 获取队尾元素30
  1. 检查队列是否为空 - empty()
if (myQueue.empty()) {
    std::cout << "队列为空" << std::endl;
} else {
    std::cout << "队列不为空" << std::endl;
}
  1. 获取队列大小 - size()
int queueSize = myQueue.size();  // 获取队列中元素个数

注意事项:

  • 调用front()或back()前应先检查队列是否为空,否则可能导致未定义行为
  • pop()操作只移除元素,不返回元素值
  • C++标准库队列不支持随机访问,只能访问首尾元素
  • 队列没有clear()方法,清空队列需要循环出队

Java

  1. 入队操作 - add()/offer()
myQueue.add(10);  // 将10加入队尾
myQueue.offer(20); // 将20加入队尾
// 现在队列内容: 10(front) -> 20(back)
  1. 出队操作 - remove()/poll()
int first = myQueue.remove(); // 移除并返回队首元素10
// 现在队列内容: 20(front)
  1. 访问队首元素 - element()/peek()
int head = myQueue.peek();  // 获取队首元素20,但不移除
  1. 检查队列是否为空 - isEmpty()
if (myQueue.isEmpty()) {
    System.out.println("队列为空");
} else {
    System.out.println("队列不为空");
}
  1. 获取队列大小 - size()
int size = myQueue.size();  // 获取队列中元素个数

注意事项:

  • 推荐使用offer()替代add(),poll()替代remove(),它们更友好
  • peek()在空队列时返回null,element()会抛出异常
  • Java队列没有直接访问队尾元素的方法
  • LinkedList实现的队列允许null元素

Python

  1. 入队操作 - append()
my_queue.append(10)  # 将10加入队尾
my_queue.append(20)  # 将20加入队尾
# 现在队列内容: 10(front) -> 20(back)
  1. 出队操作 - popleft()
first = my_queue.popleft()  # 移除并返回队首元素10
# 现在队列内容: 20(front)
  1. 访问队首元素
head = my_queue[0]  # 获取队首元素20,但不移除
  1. 访问队尾元素
tail = my_queue[-1]  # 获取队尾元素
  1. 检查队列是否为空
if not my_queue:
    print("队列为空")
else:
    print("队列不为空")
  1. 获取队列大小
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)时间复杂度的基本操作

缺点

  • 无法直接访问中间元素
  • 不支持复杂操作(如排序、查找),需借助其他数据结构

课后习题

习题 1:无法吃午餐的学生数量

习题 2:买票需要的时间

习题 3:用两个栈实现队列

习题 4:Dota2 参议院

习题 5:机器翻译

习题 6:小小的埴轮兵团

牛客代码笔记-牛栋 文章被收录于专栏

汗牛充栋,学海无涯。<br/> 内含算法知识点讲解,以及牛客题库精选例题。<br/> 学习算法,从牛栋开始。

全部评论

相关推荐

牛客837006795号:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
我的人生算是废了,23届裸辞空档一年,存款只能坚持几个月了,找不到像样的工作了,人生何去何从。
梦想是成为七海千秋:这大环境下为什么要裸辞呀,风险真的挺大的,而且社招的话23届没有太多的竞争力,不过既然已经裸辞了就不要焦虑慢慢找。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务