2021-06-03 · 2분

数据结构 — 队列

algorithm

这篇文章发布已超过两年，内容可能已过时。

BOJ #10845 队列：https://www.acmicpc.net/problem/10845

什么是队列（queue）？

队列（queue）是计算机的基本数据结构之一，指以先放入的数据先出来的 FIFO（First In First Out）结构进行存储的形式。它与后放入的数据先出来的栈是正相反的概念。

队列的功能

有很多，这些是常用的。

empty()：确认队列是否为空。
front()：返回最前面的数据。
pop()：删除队列的 front 数据。
push(item)：把 item 添加到队列。
size()：返回当前队列的大小。
swap(q1, q2)：交换两个队列的内容。
back()：返回最后面的数据。

队列的应用示例

队列主要用于需要按数据输入的时间顺序处理的场景。

同优先级的作业预约
银行业务
进程管理
广度优先搜索（BFS, Breadth-First Search）
缓存（Cache）

队列的实现

BOJ #10845 队列问题

#include <stdio.h>
#include <string.h>

int queue[10001];
int queue_size=0;

void push(int push_data){
    queue[queue_size] = push_data;
    queue_size += 1;
}

int empty(){
    if(queue_size == 0){
        return 1;
    }
    return 0;
}

int pop(){
    if(empty()){
        return -1;
    }
    queue_size -= 1;
    return queue[0];
}

int front(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-queue_size];
}

int back(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-1];
}

void setting(){
    for (int i=0;i<queue_size;i++)
    {
        queue[i]=queue[i+1];
    }
}

int main(){

    int N = 0, push_data = 0;
    char command[5] = {0,};

    scanf("%d",&N);

    for(int i=0;i<N;i++){

        scanf("%s",command);

        if(!strcmp(command,"push")){
            scanf("%d",&push_data);
            push(push_data);
        }
        else if(!strcmp(command,"pop")){
            printf("%d\n",pop());
            setting();
        }
        else if(!strcmp(command,"empty")){
            printf("%d\n",empty());
        }
        else if(!strcmp(command,"size")){
            printf("%d\n",queue_size);
        }
        else if(!strcmp(command,"front")){
            printf("%d\n",front());
        }
        else if(!strcmp(command,"back")){
            printf("%d\n",back());
        }

    }

    return 0;
}

这个和栈一样，c++ 里存在名为 queue 的头文件。

来看看它的用法。

STL 队列的用法

// 声明 queue 头文件
#include <queue>

// 创建 int 型、char 型队列
queue<int> q1;
queue<char> q2;

// 向 int 型队列 q1 添加数字
q1.push(1);
q1.push(2);
q1.push(3);

// 从 int 型队列 q1 删除元素
q1.pop();