導入
スタックは線形データ構造であり、同じ型のアイテムの集合です。スタック内では、要素の挿入と削除は片方のエンドポイントでのみ行われます。スタックの動作は「後入れ先出し」（LIFO）と呼ばれます。要素がスタックに「プッシュ」されると、その要素がスタックから最初に「ポップ」されます。最も古い挿入されたアイテムに到達するには、それ以前のすべてのアイテムをアンポップする必要があります。.
この記事では、スタック データ構造の概念と、C での配列を使用したその実装について学習します。.
スタック上で実行される操作
以下は Stacks が提供する基本的な操作です。.
- push: スタックの先頭に要素を追加します。.
- pop: スタックから最上位の要素を削除します。.
- isEmpty: スタックが空かどうかを確認します。.
- isFull: スタックがいっぱいかどうかを確認します。.
- top: スタックの最上位要素を表示します。.
スタックの基本的な仕組み
初期状態では、スタックの最上位の項目を追跡するためのポインタ（up）が設定されています。スタックは-1に初期化されます。.
次に、スタックの top と -1 を比較して、スタックが空かどうかを確認します。.
スタックに要素が追加されると、最上位の位置が更新されます。.
要素がポップまたは削除されるとすぐに、最上位の要素が削除され、最上位の位置が更新されます。.
Cでのスタック実装
STACKS は、構造体、ポインタ、配列、またはリンク リストを使用して表すことができます。.
この例では、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 つのオプションを提供します。
- 要素をプッシュする
- 要素をポップする
- 見せる
- 終わり
ユーザーが数字を入力するまで待機します。.
- ユーザーが1を選択した場合、プログラムはpush()を実行します。まず、topがSIZE - 1と等しいかどうかを確認します。等しい場合は「Overflow!!」と表示されます。そうでない場合は、スタックに追加する新しい要素を指定するようユーザーに促します。.
- ユーザーが2を選択した場合、プログラムはpop()関数を実行します。まず、topが-1かどうかを確認します。-1の場合は「Underflow!!」と表示されます。-1でない場合は、top要素を削除し、その結果をスタックに出力します。.
- ユーザーが3を選択した場合、プログラムはshow()関数を処理します。まず、topが-1かどうかを確認します。もしそうであれば、「Underflow!!」と表示されます。そうでない場合は、結果のスタックを出力します。.
- ユーザーが 4 を選択した場合、プログラムは終了します。.
このコードを実行して、数値「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次に、Stack() 内の要素を表示します。
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
これでスタックは空になりました。もう一度Pop()を試してみましょう。
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Underflow!! Your code... */スタックがどのように動作するかを理解するために、このプログラムで実験を続けてください。.
スタック操作の時間計算量
スタック内で一度にアクセスできる要素は 1 つだけです。.
スタック上でpush()およびpop()操作を実行すると、O(1)時間がかかります。.
結果
この記事では、スタック データ構造の概念と、C での配列を使用したその実装について学習しました。.
