スタック(stack)とキュー(queue)

スタックとキューはどちらもデータを一時的に保存したり、取り出したりするためのデータ構造です。どちらも、データを一列に並べて管理して、新しいデータを列のどちらかの端に保存し、また取り出す際もどちらかの端から取り出します。スタックはあとに保存したデータを先に取り出すデータ構造で、キューは先に保存したデータを先に取り出すデータ構造となっています。また、データを取り出すときに、各データにラベリングされた優先度に基づいて、データを取り出す優先度付きキューという構造もあります。

スタック

概要

スタックは、push()とpop()という２つの操作を提供するデータ構造です。それぞれデータの追加と取り出しを行います。また、現在先頭にあるデータはtop()で参照できます。

命令	スタック
初期状態	[] (empty)
push(3)	[3] (top = 3)
push(4)	[4, 3] (top = 4)
push(1)	[1, 4, 3] (top = 1)
pop	[4, 3] (top = 4)

使用上の注意と実装

push(),pop(),top()の計算時間は配列のサイズによらず定数時間です。

#include <stack>
#include <iostream>
using namespace std;
int main() {
    stack<int> S;
    S.push(3);
    S.push(4);
    S.push(1);
    while (! S.empty()) {
        int n = S.top();
        S.pop();
        cout << n << endl; //1, 4 ,3
        }
}

キュー

概要

キューはデータの格納と取り出しができるデータ構造です。現在先頭にあるデータはfront()で参照します。

命令	スタック
初期状態	[] (empty)
push(3)	[3] (front = 3)
push(4)	[3, 4] (front = 3)
push(1)	[3, 4, 1] (front = 3)
pop	[4, 1] (front = 4)

使用上の注意と実装

実装には配列やdequeが用いられます。計算コストはpush(),pop(),front()ともに定数時間です。C++には、queueというテンプレートクラスが用意されています。

#include <queue>
#include <iostream>
using namespace std;
int main() {
    queue<int> Q;
    Q.push(3);
    Q.push(4);
    Q.push(1);
    while (! Q.empty()) {
        int n = Q.front();
        Q.pop();
        cout << n << endl; //3, 4, 1
        }
}

優先度付きキュー

概要

優先度付きキューは、データの格納と取り出しができるデータ構造で、データにラベリングされた優先度順に取り出すことができるものです。実装には二分ヒープなどが利用されます。計算コストは、top()は定数時間ですが、push()またはpop()の操作については、格納されているデータの数をNとして、 $O(\log N)$ の時間がかかります。

実装

#include <queue>
#include <iostream>
using namespace std;
int main() {
    priority_queue<int> Q;
    Q.push(3);
    Q.push(4);
    Q.push(1);
    while (! Q.empty()) {
        int n = Q.top();
        Q.pop();
        cout << n << endl; //4, 3, 1(大きい順に格納されている？)
        }
}

memo

pythonにはheapqというパッケージがあるので、それを使います。自分で優先度付きキューを実装する場合は、配列またはvector上に二分ヒープ(binary heap)を作成するのが簡便です。

集合と連想配列

集合(set)

C++で集合を表現するための標準ライブラリとして、setとunordered_set(C++11以降)が用意されています。整数の集合を例にして説明します。どちらもほぼ同じ操作を提供しますが、ここでは、insert（挿入）,size（全体の要素数の取得）,count（指定した要素の有無の検索）を使用します。実装においては、setはデータに順序をつけて、unordered_setは順序を無視して管理をします。前者は通常二分探索木で実装され、挿入や検索には、 $O(\log N)$ の時間が必要です。後者は通常ハッシュ表を使って実装され、各操作は平均的には定数時間内で収まると期待されています。

要素の重複を許す場合

C++では、要素の重複を許す集合として、の表現方法として、multisetおよび、unordered_multisetというデータ構造が標準で用意されています。利用方法は通常のset及びunordered_setとほぼ同じです。

連想配列

連想配列とは、keyとそれに対応するvalueのペアを管理するために配列で、例えば、名簿の管理などに使えます。C++では、mapとunordered_mapが標準で用意されています。下の例では文字列がkey、整数がvalueとなっています。

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<string,int> table; // 文字列を数値に対応させる map
table["taro"] = 180;
table["hanako"] = 160;
cout << table["taro"] << endl; // 180
cout << table["ichirou"] << endl; // 0
}

文字列の出現回数

keyが存在しない場合の振る舞いは処理系の設定に依存します。上記の例では0が変えるようになっていて、これを利用して文字列の出現回数を簡単に計測できます。

各データ構造を使う問題

配列Aの連続する部分列について、その和がS以上となるものもうちで最小の長さを求めろ。

すべての区間を調べると、 $O(N ^ 2)$ の時間がかかりますが、popとpushを使って合計が $S$ に近い区間のみを調べると、 $O(N)$ で処理できます。つまり、はじめキューの合計が $S$ を超えるまでは、キューにpushしていき、 $S$ を超えたら、先頭の要素をpopしていくという方法を取ればいいわけです。いわゆるしゃくとり法と呼ばれる方法です。cinだと遅いのでscanfを使うといいでしょう。