キュー(Queue)・待ち行列のデータ構造

2019年11月27日データ構造キュー,データ構造

キューは待ち行列とも呼ばれます。最初に格納したデータが最初に出てくるような、線形なデータ構造をしていて、このような順序をFirst In First Out (FIFO)と言います。

キュー(Queue)

例えると、レストランにできる行列と一緒です。先に来たお客が、後から来たお客よりも早く店内に案内されます。

キューはデータを1つ格納する操作(enqueue)と1つ取り出す操作(dequeue)を使います。

プログラム例

Pythonの例

Pythonではlistを使ってキューを表現することができます。

queue = [] 

# 後方から要素の追加(enqueue)
queue.append(3)
queue.append(11)
queue.append(8)
queue.append(9)

# 先頭から要素の取出し(dequeue)
print(queue.pop(0)) # 出力は3
print(queue.pop(0)) # 出力は11
print(queue.pop(0)) # 出力は8
print(queue.pop(0)) # 出力は9

listよりも高速にデータの出し入れをしたい場合は、collectionsモジュールにあるdequeというクラスを使うことができます。

from collections import deque 
queue = deque()

# 後方から要素の追加(enqueue)
queue.append(3)
queue.append(11)
queue.append(8)
queue.append(9)

# 先頭から要素の取出し(dequeue)
print(queue.popleft()) # 出力は3
print(queue.popleft()) # 出力は11
print(queue.popleft()) # 出力は8
print(queue.popleft()) # 出力は9

C++の例

C++ではライブラリでqueueが提供されています。

#include <iostream>
#include <queue>
using namespace std;

int main() {

    queue<int> q;
    q.push(3);
    q.push(11);
    q.push(8);
    q.push(9);

    cout << q.front() << "\n"; // 3が出力
    q.pop();                   // 3が消される
    cout << q.front() << "\n"; // 11が出力
    q.pop();                   // 11が消される
    cout << q.front() << "\n"; // 8が出力
    q.pop();                   // 8が消される
    cout << q.front() << "\n"; // 9が出力
    q.pop();                   // 9が消される

    return 0;
}

データ構造キュー,データ構造