ヒープ Heap

Priority Queue を効率よく実装するためのデータ構造が ヒープ(heap) です。ヒープもまたデータ構造であり、その論理的構造は完全２分木となっています。完全２分木を１次元配列によって表現するために、木のノードの番号と配列のインデックスを下図のように対応付けます。便宜上インデックスは1から始めます。


木のルートを配列のインデックス1と対応させ（0でないことに注意して下さい）、その左の子を2、右の子を3と対応させます。同様に、各ノードの番号をkとすると、その親、左の子、右の子のインデックスは以下のようになります。

インデックス	k
親のインデックス	parent = k / 2
左の子のインデックス	left = 2 × k
右の子のインデックス	right = 2 × k+ 1

例えば、ノード 5 の
親のノードは parent = k / 2 = 5 / 2 = 2
左の子のノードは left = 2 × k = 2 × 5 = 10
右の子のノードは right = 2 × k + 1 = 2 × 5 + 1 = 11
となります。


ヒープの各ノード（配列の各要素）に、データが格納されます。ヒープにはデータの並びにおける制約があり下図に示すようにMaximum HeapとMinimum Heapの2つのタイプがあります。



上図は整数のデータを格納するヒープを表しています。

マキシマムヒープ Maximum Heap

マキシマムヒープでは上図（左）に示すように、各ノードのキーがその親ノードのキーよりも小さいか等しくなければなりません。ヒープのルートのキーが必ず最大となります。

ミニマムヒープ Minimum Heap

ミニマムヒープは上図（右）に示すように、各ノードのキーがその親ノードのキーよりも大きいか等しくなければなりません。ヒープのルートのキーが必ず最小となります。

マキシマムヒープもミニマムヒープも、データが完全に整列されている必要はありません。左の子と右の子のキーの大小関係に制約はなく、親ノードと子ノードのキーの大小関係にのみ制約があります。

ヒープには、ヒープのユーザ（プログラムやアルゴリズム）がそれに対してなんらかの操作（データの追加・取り出し・入れ替えなど）をした直後に、ヒープの条件（マキシマムヒープまたはミニマムヒープ）を維持するための処理が不可欠となります。この条件を維持するための処理は以下のものを含みます。

• upHeap()
• downHeap()

これらの処理を詳しく見てみましょう。ここでは、常にマキシマムヒープの条件を維持することを考えます。

upHeap

下図に示すように、upHeapは起点となるノードcursorの要素を、ヒープの条件を満たすまで木のルートへ向かって上へ移動します。まず1.においてcursorの要素である60が親の要素である8よりも大きくマキシマムヒープの条件を満たしていないので、2.でこれらの要素を交換しcursorを上に移動します。さらに3.においてcursorの要素である60が親の要素である25よりも大きくマキシマムヒープの条件を満たしていないので、4.でこれらの要素を交換し、cursorを上に移動します。5.でマキシマムヒープの条件が満たされたのでupHeapの処理を終了します。

downHeap

下図に示すように、downHeapは起点となるノードcursorの要素を、ヒープの条件を満たすまで木の葉（子を持たないノード）へ向かって下へ移動します。まず1.においてcursorの要素である6が子の要素である25よりも小さくマキシマムヒープの条件を満たしていないので、2.でこれらの要素を交換しcursorを下に移動します。ここで、cursorの子はノード2（左の子）とノード3（右の子）がありますが、こられのうちキーの値が大きいものを選んで比較します。この場合は25と21を比べ、25の方が大きいので、ノード2を選びます。3.においてcursorの要素である6が子の要素である12よりも小さいので、4.でこれらの要素を交換し、cursorを下に移動します。5.でマキシマムヒープの条件が満たされるのでdownHeapの処理を終了します。




ヒープを使って以下のデータ構造とアルゴリズムを実装することができます。

• 優先順位付きキュー　Priority Queue
• ヒープソート Heap Sort

優先順位付きキュー Priority Queue

データ構造には主にデータを「追加する」と「取り出す」という操作あります。そしてデータ構造にはデータを取り出すときのルールがあります。スタックはデータの中で最後に追加されたもの（一番短い時間滞在したもの）、キューはデータの中で最初に追加されたもの（一番長い時間滞在したもの）、を優先的に取り出します。つまりデータを取り出す優先度が制約によって決められています。一方、データがもつあるキーを基準にして優先度が高いものからデータを取り出す優先順位付きキューも、システムの制御やアルゴリズムの実装において重要な役割を果たします。

例として、プリンタのジョブ管理を考えてみます。１つのプリンタを共有している複数のＰＣがあると仮定します。もし、プリンタがFIFOのルールに従ったキューでジョブを管理すれば、１０００ページのジョブがキューに到着し、その後１ページのジョブがキューに到着した場合、このプリンタは先に到着した１０００ページのジョブを印刷し、それが終了した後、１ページのジョブを印刷するでしょう。このようなケースでは、先に１ページのジョブを印刷して、その後１０００ページのジョブを印刷した方が良いと考えられます。なぜなら、ジョブが実行されるまでの全体としての"待ち時間"が短くなるからです。この場合は、ページ数が少ないジョブの優先度を高くするべきです。

ここでは、整数のデータを格納する優先順位付きキューについて考えます。整数が追加されていき、キューの中で値が大きいものから優先的に取り出されます。

Priority Queue の操作

• insert( x ): キューにデータ x を挿入する
• get(): キューから最も優先度の高いデータを取り出す

データ構造はリアルタイムで（動的に）値の追加や取り出しが行われるので、いかにこれらの操作を効率良く行うかが重要になります。例えば、スタックやキューのデータ構造における操作は、追加も取り出しもO(1)の計算量で行うことができます。しかし、優先順位付きキューはそうはいきません。ここで考えられるのがデータの探索と整列（次章で学習します）ですが、データを取り出す度に優先度の高いものを探索していたのではO(n)の計算量が必要ですし、データを追加する（または取り出す）度にデータを優先度順に並び変えていては探索するよりも効率が悪くなります。優先順位付きキューの操作を効率良く行うために、ヒープの概念を用います。

ヒープ（Heap）

整数型のデータが格納される優先順位付きキューをヒープを用いて実装します。値が大きいものほど優先度が高いものとします。実装に必要なものは配列によるスタックとキューと同じく、データを格納するための整数型1次元配列bufferです。このbufferをヒープとみなして優先順位付きキューに対する操作を行います。優先順位付きキューにはinsert(x)とgetの操作がありました。

insert(x)

ヒープのデータ構造において、新しいデータをinsertすることができる場所はヒープのサイズを1つ増やしたヒープの末尾です。下図に示すように、ヒープの末尾にデータを追加すると（1.）、それがヒープの制約を破る可能性があります（2.）。従って、そのデータが追加されたヒープの末尾を起点にupHeapを施します（2.→3.）。

get

ヒープのルートには必ずデータの中で一番優先度が高い要素が含まれます。従って下図に示すように、getでルートの要素を取り出します（1.）。ルートが実質空になるので、ヒープの末尾の要素をルートに移動しヒープのサイズを1つ減らします（2.）。ルートの要素がヒープの制約を破る可能性があるので（2.）、ルートを起点としてdownHeapを施します（2.→3.）。




以下のプログラムはヒープによって優先順位付きキューを実現し、キューへのデータの追加・取り出しをシミュレーションします。プログラムは”insert x”（xは整数）と入力されるとキューにxを追加し、”get”と入力されるとキューの中で一番値が大きいものを取り出し出力します。

001 #include<iostream>
002 #include<string>
003 #include<algorithm>
004 using namespace std;
005 #define MAX 10000
006 
007 class PriorityQueue{
008     public:
009     int size;
010     int buffer[MAX + 1];
011     
012     PriorityQueue(){size = 0;}
013     
014     void insert(int x){
015         size++;
016         buffer[size] = x;
017         upHeap(size);
018     }
019     
020     int get(){
021         int v = buffer[1];
022         buffer[1] = buffer[size];
023         size--;
024         downHeap(1);
025         return v;
026     }
027     
028     private:
029     
030     void upHeap( int cursor ){
031         int parent;
032         while(1){
033             parent = cursor / 2;
034             if ( parent < 1 ) break;
035             if ( buffer[parent] < buffer[cursor] ){
036                 swap(buffer[parent], buffer[cursor]);
037             } else break;
038             cursor = parent;
039         }
040     }
041     
042     void downHeap( int cursor ){
043         int child;
044         while(1){
045             if ( cursor > size/2 ) break;
046             child = cursor * 2; // left child
047             if ( child < size && buffer[child] < buffer[child+1] ) child++;
048             if ( buffer[cursor] < buffer[child] ){
049                 swap( buffer[cursor], buffer[child] );
050             } else break;
051             cursor = child;
052         }
053     }
054 };
055 
056 int main(void){
057     PriorityQueue PQ = PriorityQueue();
058     int x;
059     string command;
060     
061     while(1){
062         cin >> command;
063         if ( command == "insert" ){
064             cin >> x;
065             PQ.insert(x);
066         } else if ( command == "get" ){
067             cout << PQ.get() << endl;
068         } else break;
069     }
070     
071     return 0;
072 }

main関数

優先順位付きキューのオブジェクトPQを操作します。

insert (x)

ヒープのサイズsizeを1つ増やし、ヒープの末尾をしめすbuffer[size]にxを追加します。ヒープの条件を保つためにヒープの末尾を示すsizeを起点にupHeapを施します。

get

ヒープのルートの要素であるbuffer[1]を一時変数vに記録し、ヒープの末尾の要素buffer[size]をルートへ移動します。末尾の要素を空にするので、ヒープのサイズsizeを1つ減らします。ヒープの条件を保つためルートである1を起点にdownHeapを施します。

upHeap

下図を参照して下さい。引数cursorを起点にupHeapを行います。親の要素buffer[parent]が起点の要素buffer[cursor]よりも小さい場合、それらを交換します。この処理をcursorを1つ上に移動してヒープの条件を満たすまで繰り返します。

downHeap

下図を参照して下さい。引数cursorを起点にdownHeapを行います。子の要素buffer[child]が起点の要素buffer[cursor]よりも大きい場合、それらを交換します。047行目で左と右の子のうち要素の値が大きいものを選んでいます。この処理を、cursorを選ばれた子の方向に1つ下に移動してヒープの条件を満たすまで繰り返します。



ヒープは完全２分木であり、要素の数をnとすれば木の高さはlognとなります。upHeapとdownHeapの計算量はいづれもO(logn)です。従って、優先順位付きキューに対するinsertとgetの計算量は、いづれもO(logn)となります。

Disjoint Sets, Union Find

Disjoint Sets, Union Find とは？
Disjoint Sets は、多くのデータを互いに素な集合（１つの要素が複数の集合に属することがない集合）に分類して管理するためのデータ構造です。このデータ構造は、動的に以下の操作を高速に処理します。

	makeSet( x ): 要素が x ただ１つである新しい集合を作る
	findSet( x ): 要素 x が属する集合の"代表"の要素を求める つまり、要素 x がどの集合に属するかを調べることができる
	union( x, y ): 指定された２つの要素 x, y を unite（合併）する

Disjoint Sets に対して、「指定された２つの要素 x, y が、同じ集合に属するか？」どうかを調べる操作、つまり findSet(x) == findSet(y) は Union Find と呼ばれます。

Disjoint Sets の表現
Disjoint Sets を実装する方法はいくつかありますが、ここでは Disjoint Sets forests と呼ばれる"森"の構造を用います。森を構成する tree (木)が各集合を表し、tree の各ノードが集合内の各要素を表します。

findSet( x )
集合を区別するために、各 tree の根を代表 (representative) とし、集合を識別するために用います。従って、findSet( x ) は、要素 x が属する tree （集合）の根を値として返します。これを実現するために、各ノードはそれ自身から代表まで到達できるように、親へのポインタを持ちます（ただし、代表 はそれ自身へのポインタを持ちます）。

例えば、下図の Disjoint Sets で findSet( 5 ) の結果は 1 、findSet( 0 ) の結果も 1 なので、5 と 0 が同じ集合に属することが分かります。

findSet( x ) の計算量は、各ノードから代表までの間にたどるポインタの数 = 木の高さです。ここで、findSet( x ) は、単に代表を求めるだけではなく、次に実行される findSet( x ) の効率を高めるために、ある工夫をしています。それは、ある要素の代表を求めるとき、その要素から代表に至る経路の全てのノードについて、ポインタが直接代表を指すように変更します。例えば、下図はある集合 S に対して findSet( 0 ) を実行した結果を示しています。

S		S'
	→  findSet( 0 )  →

S において、各ノードは親へのポインタをもち、要素 0 の代表は、0 → 1 → 2 → 3 → 4 とたどることによって 4 と求められます。その経路上のノードのポインタを直接 4 を指すように処理し S' を得ます。

この工夫によって、極めて高さの低い木が生成されることがわかります。つまり、次回実行されるであろう S' に属する要素 x における findSet( x ) の操作は極めて少ない計算量で行うことができます。これを path compression (経路圧縮)といいます。

再帰を用いて path compression を行う findSet の実装は、以下のようになります。

    int findSet( int x ){
        if ( x != p[x] ) p[x] = findSet( p[x] );
        return p[x];
    }

union( x, y )
指定された２つの要素 x, y を合併する操作は、x の代表と y の代表を求め、どちらか一方を新しい代表として選びます。つまり、代表にならなかったほうのポインタを新しい代表を指すように更新します。例えば、下図はある Disjoint Sets S に対して union( 2, 4 ) を実行した結果を示しています。

S		S'
	→  union( 2, 4 )  →

ここで重要なことが、"どちらの代表を新しい代表として選ぶか"です。ポイントは、合併する集合を表す木の高さです。低い方の木を高い方の木に合併すれば、新しい木の高さが高くなることはありません。従って、高い木の代表を新しい代表にします。各ノード x を根としたときの木の高さに関する情報を rank[x] という変数に記録します。１つの要素が１つの集合を成している初期状態では、rank[x] は全て 0 としておきます。そして同じ rank の木を合併するときに rank を１つ増やします。以下に例を示します。

S		S'
	→  merge( 0, 5 )  →

S		S'
	→  merge( 0, 5 )  →

merge や経路圧縮を伴う findSet によって、rank の値は変化していきます。従って、rank は木の正確な高さを与えるものではなく、木の高さの上限を与えます。

以下に、DisjointSets のデータ構造を実装したプログラムを示します。

class DisjointSet{
    public:
    DisjointSet(){}
    DisjointSet( int size ){
        rank.resize( size, 0 );
        p.resize( size, 0 );
    }
    
    void makeSet( int x ){
        p[x] = x;
        rank[x] = 0;
    }
    
    void union( int x, int y ){
        link( findSet(x), findSet(y) );
    }
    
    int findSet( int x ){
        if ( x != p[x] ) p[x] = findSet( p[x] );
        return p[x];
    }
    
    bool isSameSet( int x, int y ){
        return ( findSet(x) == findSet(y) );
    }
    
    private:
    vector<int> rank, p;
    
    void link ( int x, int y ){
        if ( rank[x] > rank[y] ){
            p[y] = x;
        } else {
            p[x] = y;
            if ( rank[x] == rank[y] ) rank[y]++;
        }
    }
};

計算量の解析
ここで紹介した DisjointSets における Union Find は、経路圧縮と rank を用いることによって極めて高速になります。（解析は省略します）

キュー （待ち行列） Queue

キューは「待ち行列」とも呼ばれ、データを到着順に処理したいときに使用するデータ構 造で、データの中で最初に入ったものが最初に取り出される、先入れ先出し（FIFO: First In First Out）のルールに従ってデータを管理します。スーパーのレジやＡＴＭの待ち行列にお ける人々の動きやそこにある暗黙のルール（割り込みや追い越しの禁止）は、キューのデー タ構造そのものです。

キューの操作

• enqueue(x): キューの末尾に要素 x を追加します。
• dequeue(): キューの先頭から要素を取り出します。
• isEmpty(): キューが空かどうかを調べます。
• isFull(): キューが満杯かどうかを調べます。

実用的なキューには、これらの他にもキューの先頭の要素を参照したり、キューに指定され たデータが含まれているかを調べたりするオプション的な操作も含まれますが、ここでは上 記４つの操作を含むキューを実装します。

キューの制約

• データの中で最初に入ったものが最初に取り出されます。

整数型のデータが格納されるキューを配列を用いて実装します。以下に、実装に必要なもの を示します(下図参照)。



データを格納するための整数型1 次元配列: buffer
配列buffer の各要素にエンキューされたデータを格納していきます。問題に応じた十分な 記憶領域を確保することが必要です。Fig.4.3-1 では、既にいくつかの要素が格納されてい ます。

先頭カーソルである整数型変数：head
キューの先頭の場所を指し示す変数です。dequeue されるとhead で指された要素が取り出 されます。キューの先頭の要素のインデックスが0 とは限らないことに注意して下さい。

末尾カーソルである整数型変数：tail
キューの末尾＋ 1 の場所（最後の要素の隣）を指し示す変数です。tail は新しい要素が追加 される場所を示します。

実際にキューのデータ構造を操作する様子を見てみましょう。Fig. 4.3-2は、実際にキューに適当な値を適当に出し入れしている様子を示しています。

初期化: head = tailのときキューが空になります。初期値はhead = tail = 0とします。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 3 ）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 7 ）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 1 ）。 dequeue: headが指す要素を取り出し、headを1増やします （例: 3を取り出す）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 8 ）。 dequeue: headが指す要素を取り出し、headを1増やします （例: 7を取り出す）

このように配列によってキューを実装すると、上図に示すように、データの追加と取り出し操作を繰り返すことによって、headとtailに挟まれたキューのデータ本体が配列の末尾に向かって（図の右側に）移動していき、すぐに要領をオーバーしてしまいそうに見えます。

下図に示すように、dequeueされたときにheadを常に0に保つようにデータ全体を配列の先頭に（左に）向かってシフトしていては、dequeueの度にO(n)の計算が必要になってしまいます。一方で、tailが配列の領域を超えた時点でoverflowとしてしまったのでは、まだ使える配列の領域を無駄にしてしまいます。


これらの問題を避けるために、配列によるキューの実装ではFig.4.3-4に示すように、配列をリングバッファとみなしてキュー内のデータを管理します。


リングバッファとは通常の1次元配列で実現しますが、キューの範囲を指し示すカーソルheadまたはtailが配列の領域を超えてしまったときにこれらのカーソルを循環させます。つまり、カーソルを1つ増やして、それが配列の範囲を超えてしまった場合には、カーソルを0にリセットします。

上図は既にいくつかのデータが格納されたキューにデータを出し入れしている様子を示しています。最初に1を追加したときに、tailの値が1つ増えますが、配列の領域を超えてしまうので、tailを0に設定します。リングバッファを時計回りに見ると、キューにデータがある場合は必ずhead→tailの順番に並びます。

次のは配列によってキューを実現し、キューへのデータの追加・取り出しをシミュレーションします。

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

#define MAX 100

class Queue{
    private:
    int buffer[MAX];
    int head, tail;

    public:
    Queue(){
        initialize();
    }

    void initialize(){
        head = tail = 0;
    }

    bool isEmpty(){
        return ( head == tail );
    }

    bool isFull(){
        return ( head == tail + 1 );
    }

    void enqueue( int x ){
        if ( isFull() ){
            cout << "overflow" << endl;
            return;
        } else {
            buffer[tail] = x;
            if ( tail + 1 == MAX ) tail = 0; // 循環
            else tail++;
        }
    }

    int dequeue(){
        if ( isEmpty() ){
            cout << "underflow" << endl;
        } else {
            int x = buffer[head];
            if ( head + 1 == MAX ) head = 0; // 循環
            else head++;
            return x;
        }
    }
};

int main(void){
    Queue queue;
    int x;
    string command;

    while (1){
            cin >> command;
            if ( command == "enqueue" ) {
                cin >> x;
                queue.enqueue(x);
            } else if ( command == "dequeue" ){
                cout << queue.dequeue() << endl;
            } else break;
    }

    return 0;
}

main関数
キューのオブジェクトqueueを操作します。無限ループによってキーボードからコマンドcommandの入力を待ち続けます。commandがenqueueであればxを読み込みそれをqueueに追加します。commandがdequeueであればqueueからデータを取り出し、それを出力します。それ以外のcommandが入力されたときループから抜けプログラムが終了します。

initialize
queue を空にします。queue が空のときhead とtail が同じ位置を示します。ここでは初期 値を0 と設定します。

isEmpty
queue が空の場合真を返します。head とtail が同じ値のときキューが空となります。

isFull
queue が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されていま す。head が(tail+1)%MAX に等しいとき、queue が満杯になります。リングバッファを時 計回りに見ると、tail → head の間は常に1 つ以上の空きがあります。

enqueue(x)
queue が満杯の場合は”overflow” と出力します。そうでなければ、tail が指す場所にx を追 加します。queue の要素が1 つ増えたのでtail を1 増やします。ただし、増やした値が配 列の容量であるMAX 以上になってしまう場合はtail を0 として循環させます。

dequeue
queue が空の場合は”underflow” と出力します。そうでなければ、head が指すqueue の先 頭の要素を変数x に一時記録し、head を1 増やしてからx を返します。ただし、head を 増やした値がMAX 以上になってしまう場合はhead を0 として循環させます。

スタック Stack

スタックは一時的にデータを退避したいときに有効なデータ構造で、データの中で最後に 入ったものが最初に取り出される後入れ先出し（LIFO: Last In First Out）のルールに従いデー タを管理します。例えば、以下の何気ない日常の行動が、スタックのデータ構造をうまく表 現してくれます。

テストの勉強中で以下のような一連の行動をとった場面があるかもしれません。

• １. 英語の教科書を読む
• ２. 分からない単語があったので、辞書を引く
• ３. 辞書を引いている途中で、友達からメールがｷﾀのでメールを書く
• ４. メールの返信が終わったので、辞書を引きなおす
• ５. 単語を理解したので、教科書の続きを読む
• ６. 教科書を読み終える

この行動の流れをスタックで表わすと以下のようになります：



積み木のように「行動」が順番に重なっていきます。積み木の最上部が進行中の行動で、そ の下にあるもの全てが中断されている行動になります。この例での重要なポイントは、例え ばステップ4 でメールを返信した後に教科書を読むのではなく、メールの対応によって中 断されていた「辞書を引く」ことに戻るということです。

このように、コンピュータにおいても処理していたことを一時的に退避させ、適時それを取 り出して正しい順番で続行しなければならない場面は多くあります。この例では、もし順番 が乱れて単語の意味を理解しないまま教科書を読もうとしてもつまづいてしまいます。この ような行動をコンピュータにおけるデータや処理と置き換えたものが、スタックのデータ構 造です。

スタックの操作

• push(x): スタックの先頭（頂点）に要素 x を追加します。
• pop(): スタックの先頭（頂点）から要素を取り出します。
• isEmpty(): スタックが空かどうかを調べます。
• isFull(): スタックが満杯かどうかを調べます。

スタックの制約

• データの中で最後に入ったものが最初に取り出されます。

スタックやその他のデータ構造の実装には配列やリストを使ったものなどいくつかの方法があります。ここでは、データ構造の操作と制約の理解に重点をおきますので、簡単な例を通して１つの実装方法を示します。整数型のデータが格納されるスタックを配列を用いて実装します。以下に、実装に必要なものを示します(下図参照)。

データを格納するための整数型1次元配列： buffer
配列bufferの各要素にプッシュされたデータを格納していきます。問題に応じた十分な記憶領域を確保することが必要です。また、便宜上 0 番目には常に何も入れないようにします。Fig. 4.2-2は、容量が7のスタックに既に5つの要素が格納されている様子を表しています。


スタックポインタである整数型変数： top
スタックの頂点の要素（一番最後に追加された要素）を指し示す整数型の変数です。この変数をスタックポインタといいます。またtop の値はスタックの要素数をも示します。

実際にスタックのデータ構造を操作する様子を見てみましょう。Fig. 4.2-3は、実際にスタックに適当な値を適当に出し入れしている様子を示しています。データ構造の操作は動的に発生するものなので、スタックの要素は変動していきます。

初期化: top = 0としてスタックを空にします。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 3 ）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 12 ）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 1 ）。 pop: topが指している要素を取り出し、topを1減らします （例: 1を取り出す）。 pop: topが指している要素を取り出し、topを1減らします （例: 12を取り出す）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 5 ）

以下のプログラムは配列によってスタックを実現し、スタックへのデータの追加・取り出しをシミュレーションします。プログラムは、”push x” （xは整数）とキーボードから入力されると、スタックにxを追加し、”pop” と入力されると、スタックの頂点の要素を取り出しそれを出力します。これら以外の形式が入力されたときプログラムが終了します。
スタックのデータ構造はクラスとして実装されています。クラスとしてデータ構造を実装しておけば、それらを部品として使えるので、プログラムで複数の異なるスタックを使いたい場合などに便利になります。

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

#define MAX 5

class Stack{
    private:
    int buffer[MAX];
    int top;

    public:
    Stack(){
        initialize();
    }

    void initialize(){
        top = 0;
    }

    bool isEmpty(){
        return ( top == 0 );
    }

    bool isFull(){
        return  ( top >= MAX );
    }

    void push( int x ){
        if ( isFull() ){
            cout << "overflow" << endl;
        } else {
            top++;
            buffer[top] = x;
        }
    }

    int pop(){
        if ( isEmpty() ) {
            cout << "underflow" << endl;
        } else {
            int x = buffer[top];
            top--;
            return x;
        }
    }
};

int main(void){
    Stack stack;
    int x;
    string command;

    while (1){
        cin >> command;
        if ( command == "push" ) {
            cin >> x;
            stack.push(x);
        } else if ( command == "pop" ){
            cout << stack.pop() << endl;
        } else break;
    }

    return 0;
}

main 関数
スタックのオブジェクト（※ 1）stack を操作します。無限ループによってキーボードから コマンドcommand の入力を待ち続けます。command がpush であればx を読み込みそれ をstack に追加します。command がpop であればstack からデータを取り出し、それを出 力します。それ以外のcommand が入力されたときループから抜けプログラムが終了します。

initialize
stack を空にします。stack が空のときはtop が0 を指します。

isEmpty
stack が空の場合真を返します。top が0 のときstack が空の状態になります。

isFull
stack が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されています。 top がMAX 以上のときにstack が満杯の状態になります。

push(x)
stack が満杯の場合は”overflow” と出力します。そうでなければ、top を1 つ増やし、その 場所にx を追加します。

pop
stack が空の場合は”underflow” と出力します。そうでなければ、stack の頂点の要素を変数 x に一時記録し、top を1 減らしてからx を返します。



普通は、以下のように便利なライブラリを使います。

#include<stack>

using namespace std;

main(){
    stack<int> st;
    st.push(1);
    st.push(7);
    st.push(3);
    cout << st.top() << endl; st.pop();
    cout << st.top() << endl; st.pop();
    st.push(5);
    cout << st.top() << endl; st.pop();
    cout << st.top() << endl; st.pop();
}

練習問題１

see-try-see

データ構造

データ構造とは、プログラムの中でデータを一定の形式に系統立てて格納するときの形式です。プログラムの中で、どのようなデータ構造を用いたかが、そこで実装されたアルゴリズムの効率に大きく影響します。 データ構造は、

• 「データの集合」
• 「データの集合に対する操作」
• 「データをルールに従って正しく保つための制約」

から成りたっています。

これから記録していきたいデータ構造↓

• スタック Stack
• キュー Queue
• 優先順位キュー Priority Queue
• Disjoint Sets
• 二分探索木
• etc.