2021-06-03 · 2분

データ構造 — キュー

algorithm

この記事は公開から2年以上経過しています。

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)：2 つのキューの内容を入れ替えます。
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();