データ構造におけるスタックADT（抽象データ型）の基本と操作を解説

抽象データ型（ADT：Abstract Data Type）は、値の集合とそれに対する操作の集合によって振る舞いが定義される、特殊なデータ型です。「抽象」という言葉が使われる理由は、利用者はこれらのデータ型を使って様々な操作を実行できるものの、その操作が内部でどのように実装され、動作しているのかが完全に隠されているためです。つまりADTはプリミティブなデータ型から構成されていますが、操作のロジックは外部から見えないようにカプセル化されています。

スタックはADTの代表的な例の一つです。スタックは「LIFO（Last In First Out：後入れ先出し）」と呼ばれる方式でデータを管理し、最後に追加した要素が最初に取り出されるという特徴を持ちます。スタックADTには主に以下のような操作（関数）が定義されています。

• isFull()：スタックが満杯かどうかを判定するために使用します
• isEmpty()：スタックが空かどうかを判定するために使用します
• push(x)：要素xをスタックの先頭に挿入（プッシュ）するために使用します
• pop()：スタックの先頭から要素を1つ削除するために使用します
• peek()：スタックの最上位にある要素を取得するために使用します（削除は行いません）
• size()：スタック内に存在する要素の数を取得するために使用します

C++によるスタックADTの実装例

#include<iostream>
#include<stack>
using namespace std;
main(){
    stack<int> stk;
    if(stk.empty()){
        cout << "Stack is empty" << endl;
    } else {
        cout << "Stack is not empty" << endl;
    }
    //スタックへ要素を挿入
    stk.push(10);
    stk.push(20);
    stk.push(30);
    stk.push(40);
    stk.push(50);
    cout << "Size of the stack: " << stk.size() << endl;
    //要素を取り出しながら表示
    while(!stk.empty()){
        int item = stk.top(); //peek操作に相当
        stk.pop();
        cout << item << " ";
    }
}

実行結果

Stack is empty
Size of the stack: 5
50 40 30 20 10

コードの解説

このプログラムでは、まずempty()関数を使ってスタックが空であることを確認した後、push()によって10から50までの5つの整数を順番に挿入しています。この時点でsize()が返すスタックのサイズは5になります。

その後、whileループの中でtop()（peek操作に相当）により先頭要素を取得し、pop()で削除しながら全要素を表示しています。スタックはLIFO構造のため、出力結果は挿入した順序と逆の「50 40 30 20 10」となります。このように、ADTの利用者は内部実装を意識することなく、定義された操作だけでスタックを扱うことができます。