Cプログラミングでスタックを実装する方法

2年 ago

綾乃, 一希

3 minutes

以下は日本語で、一つのオプションで表現したものです。

イントロダクション

スタックは、同じ型のアイテムのコレクションである、線形のデータ構造です。

スタックでは、要素の挿入と削除は片方の端だけで起こります。スタックの動作は「後入れ先出し」（LIFO）として説明されます。要素がスタックに「プッシュ」されると、それがスタックから「ポップ」される最初のアイテムとなります。最も古く入力されたアイテムにアクセスするには、以前のすべてのアイテムをポップする必要があります。

この記事では、スタックデータ構造の概念とそのCでの配列を使った実装について学びます。

スタック上で行われるオペレーション

以下はスタックによって提供される基本的な操作です。

push: Adds an element to the top of the stack.
pop: Removes the topmost element from the stack.
isEmpty: Checks whether the stack is empty.
isFull: Checks whether the stack is full.
top: Displays the topmost element of the stack.

スタックの基本的なメカニズム

最初に、ポインタ（トップ）はスタック内で最も上にあるアイテムを追跡するために設定されます。スタックは-1で初期化されます。

それから、トップと-1を比較してスタックが空かどうかを確認するチェックが行われます。

スタックに要素が追加されると、トップの位置が更新されます。

要素がポップされたり削除されると、一番上の要素が削除され、一番上の位置が更新されます。

Cでのスタックの実装

スタックは、構造体、ポインタ、配列、またはリンクリストを使用して表現することができます。

この例では、C言語を使って配列を使用してスタックを実装しています。

#include <stdio.h>

#include <stdlib.h>

#define SIZE 4

int top = -1, inp_array[SIZE];
void push();
void pop();
void show();

int main()
{
    int choice;

    while (1)
    {
        printf("\nPerform operations on the stack:");
        printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
        printf("\n\nEnter the choice: ");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            push();
            break;
        case 2:
            pop();
            break;
        case 3:
            show();
            break;
        case 4:
            exit(0);

        default:
            printf("\nInvalid choice!!");
        }
    }
}

void push()
{
    int x;

    if (top == SIZE - 1)
    {
        printf("\nOverflow!!");
    }
    else
    {
        printf("\nEnter the element to be added onto the stack: ");
        scanf("%d", &x);
        top = top + 1;
        inp_array[top] = x;
    }
}

void pop()
{
    if (top == -1)
    {
        printf("\nUnderflow!!");
    }
    else
    {
        printf("\nPopped element: %d", inp_array[top]);
        top = top - 1;
    }
}

void show()
{
    if (top == -1)
    {
        printf("\nUnderflow!!");
    }
    else
    {
        printf("\nElements present in the stack: \n");
        for (int i = top; i >= 0; --i)
            printf("%d\n", inp_array[i]);
    }
}

このプログラムは、ユーザーに4つのオプションを表示します。

終了

ユーザーが数値を入力するのを待っています。

If the user selects 1, the program handles a push(). First, it checks to see if top is equivalent to SIZE – 1. If true, “Overflow!!” is displayed. Otherwise, the user is asked to provide the new element to add to the stack.
If the user selects 2, the program handles a pop(). First, it checks to see if top is equivalent to -1. If true, “Underflow!!” is displayed. Otherwise, the topmost element is removed and the program outputs the resulting stack.
If the user selects 3, the program handles a show(). First, it checks to see if top is equivalent to -1. If true, “Underflow!!” is displayed. Otherwise, the program outputs the resulting stack.
If the user selects 4, the program exits.

スタックに数字「10」をpush()するために、このコードを実行してください。

Output

Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 1 Enter the element to be inserted onto the stack: 10

その後、スタック内の要素をshow()してください。

Output

Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 3 Elements present in the stack: 10

それからpop()を実行する。

Output

Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 2 Popped element: 10

さあ、スタックは空になりました。もう一度pop()を試みてください。

Output

Perform operations on the stack: 1.Push the element 2.Pop the element 3.Show 4.End Enter the choice: 3 Underflow!!

このプログラムを試行し続けて、スタックの動作を理解するために研究を続けてください。

スタックの操作の時間複雑度

スタックでは一度に1つの要素しかアクセスすることができません。

スタックのpush()とpop()操作を実行する際、O(1)の時間がかかります。

結論

この記事では、スタックデータ構造の概念とそのCにおける配列を用いた実装について学びました。

スタックは、一般的な問題を解決するために使用されます。

中置記法から接頭辞変換への変換

Cとは、C言語でキューを作成する方法と、C言語で配列を初期化する方法についての学習を続けてください。