データ構造学習ノート＜2＞スタック

一、スタックの抽象データ型の説明#

型名：スタック（Stack）
データオブジェクトの集合：0 個以上の要素を持つ有限線形リスト
操作の集合：長さが MaxSize のスタック S∈Stack、スタックの要素 item∈ElementType

1. 空のスタックを生成し、最大長さは MaxSize です。
Stack CreateStack(int MaxSize);
2. スタック S が満杯かどうかを判断します。
int IsFull(Stack S, int MaxSize);
3. 要素 item をスタックにプッシュします。
void Push(Stack S, ElementType item);
4. スタック S が空かどうかを判断します。
int IsEmpty(Stack S);
5. スタックのトップ要素を削除して返します。
ElementType Pop(Stack S);

二、スタックの順序保存実装#

1. 定義#

スタックの順序保存構造は通常、1 次元配列とスタックのトップ要素の位置を記録する変数から構成されます。

#define MaxSize <データ要素の最大数>
typedef struct SNode *Stack;//SNodeの構造体ポインタをStackとして定義する
struct SNode {
    ElementType Data[MaxSize];//1次元配列
    int Top;//スタックのトップ要素を記録
};

Stack PtrS は、SNode への構造体ポインタ PtrS を定義しています。

2. 操作#

(1) プッシュ操作（Push）#

Top の値を 1 増やし、要素 item をスタックのトップに保存します。

void Push(Stack PtrS, ElementType item) {
    if (PtrS->Top == MaxSize-1) {//スタックがいっぱいです
        printf("スタックがいっぱいです");
        return;
    } else {    //スタックがいっぱいでない場合、プッシュ操作を実行します
        PtrS->Data[++(PtrS->Top)] = item;//Topの値を先に増やし、その後に保存します
        return;
    }
}

(2) ポップ操作（Pop）#

要素をポップし、Top の値を 1 減らします。

ElementType Pop(Stack PtrS) {
    if(PtrS->Top == -1) {//スタックが空です
        printf("スタックが空です");
        return ERROR;//ERRORはElementTypeの特殊な値で、エラーを示します。
    } else 
        return (PtrS->Data[(PtrS->Top)--]) //トップの要素を返し、その後にTopを減らします
}

三、スタックのリンク保存実装#

1. 定義#

スタックのリンク保存構造は実際には単方向リストであり、リンクスタックと呼ばれます。挿入と削除操作はリンクスタックのトップでのみ行うことができます。スタックのトップポインタ Top はリストの先頭にある必要があります！

typedef struct SNode *Stack;
struct SNode {
    ElementType Data;//現在のデータ
    struct SNode* Next;//次のSnodeを指すポインタ
};

2. 操作#

(1) スタックの初期化（CreateStack）#

スタックのヘッドノードを構築し、ポインタを返します。

Stack CreateStack() {
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

(2) スタックが空かどうかを判断する（IsEmpty）#

スタック S が空であるかどうかを判断し、空の場合は 1 を返し、そうでない場合は 0 を返します。

int IsEmpty(Stack S) {
    return (S->Next == NULL);//後ろにノードがない場合は空です
}

(3) 要素 item をスタックにプッシュする（Push）#

まず、新しいノードの構造体ポインタ TmpCell を作成し、領域を割り当てます。次に、データを item に設定し、Next ポインタを元の S の Next ポインタに設定します。次に、S の Next ポインタを TmpCell に設定します。

void Push(ElementType item, Stack S) {
    Stack TmpCell;
    TmpCell = (Stack) malloc(sizeof(struct SNode));
    TmpCell->Data = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

(4) スタック S のトップ要素を削除して返す（Pop）#

現在のノード (S) を一時的に保存し、FirstCell を S の Next ポインタに設定し、S の Next ポインタを次のアドレスに設定します。つまり、S の Next ポインタを直接 2 番目のノードに指します。次に、FirstCell 内のデータを取り出して動的に割り当てられたメモリを解放し、そのデータを返します。

ElementType Pop(Stack S) {
    Stack FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)) {//空の場合
        printf("スタックが空です");
        return NULL;
    } else {
        FirstCell = S->Next;//次のノードを指すポインタを一時的に保存します
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Data;
        free(FirstCell);
        return TopElem;
    }
}

四、スタックの応用（式の評価）#

中置表記を後置表記に変換する方法は？
中置表記の各オブジェクトを先頭から末尾まで読み取り、異なるオブジェクトを異なる場合に処理します。

1. オペランド：直接出力します。#

2. 左括弧：スタックにプッシュします。#

3. 右括弧：スタックのトップの演算子をポップして出力し、左括弧に出会うまで続けます（ポップは行いますが、出力はしません）。#

4. 演算子：スタックのトップの演算子の優先順位が高い場合、スタックにプッシュします。優先順位が等しいか低い場合、スタックのトップの演算子をポップして出力し、新しいトップの演算子と比較し、その後、スタックのトップの演算子の優先順位が新しい演算子よりも低くなるまで続けます。その後、その演算子をスタックにプッシュします。#

5. 各オブジェクトの処理が完了した場合、スタックに残っている演算子をすべて出力します。#

スタックの他の応用：関数呼び出しと再帰の実装、深さ優先探索、バックトラックアルゴリズムなど...