スタックとは#
スタック（stack）は、後入れ先出し（Last In First Out, LIFO）のリニアリストであり、リストの末尾には特別な意味があり、それをスタックトップ（top）と呼びます。
スタックの操作#
スタックで最もよく使用される操作は 2 つあります。1 つは要素をリストの末尾に挿入する操作で、これをプッシュ（push）またはスタックに追加すると呼びます。もう 1 つは要素をリストの末尾から削除する操作で、これをポップ（pop）またはスタックから取り出すと呼びます。
スタックの表現#
スタックは配列で表すこともできます。これを順序スタックと呼びます。また、リンクリストで表すこともできます。これをリンクスタックと呼びます（この記事では主にリンクスタックについて説明します）。
単方向リンクリストでは、要素をリストの先頭、末尾、または他の任意の有効な位置に挿入することができます。ただし、単方向リンクリストの末尾にのみ要素を挿入および削除できる場合、それをリンクスタックと見なすことができます。
したがって、単方向リンクリストの基礎となるものに加えて、topポインタを維持するだけで済みます。
注意
図中の各ノードのポインタフィールドnextは、次のノードを指すポインタではなく、次のノードのポインタフィールドを指しています。
スタックのノード定義と top ポインタ#
リンクスタックのノードを表す構造体の定義
typedef struct stack_node {
struct stack_node *next;
void *data;
} stack_node;
リンクスタックを表す構造体の定義
typedef struct stack {
struct stack_node *top;
int length; // スタックの高さを表す
} stack;
注意：topポインタは、スタックを表すノードの構造体を指しています。
関数リスト#
以下はスタックの操作に使用される関数名とその機能とアルゴリズムの複雑さです。
| 関数 | 機能 | アルゴリズムの複雑さ |
|---|---|---|
| stack_create | 新しいリンクスタックを作成する | O(1) |
| stack_release | スタックとスタック内のノードを解放する | O(N) |
| stack_push | プッシュ（スタックに追加）する | O(1) |
| stack_pop | ポップ（スタックから取り出す）する | O(1) |
| stack_empty | スタック内のすべてのノードを解放するが、スタック自体は解放しない | O(N) |
スタックの作成#
/* スタックの作成 */
stack *stack_create()
{
stack *stack = (struct stack *)malloc(sizeof(struct stack));
/* 同等の書き方：
stack *s = (stack *)malloc(sizeof(stack)); */
if (stack == NULL)
return NULL;
/* 初期化 */
stack->length = 0;
stack->top = NULL;
return stack;
}
プッシュ（スタックに追加）#
/* プッシュ（スタックに追加） */
stack *stack_push(stack *stack, void *data)
{
/* ノードの作成 */
stack_node *node = (struct stack_node *)malloc(sizeof(struct stack_node));
if (node == NULL)
return NULL;
node->data = data;
/* 挿入 */
node->next = stack->top;
stack->top = node;
stack->length++;
return stack;
}
要素がスタックにプッシュされると、まずノードが作成され、次に挿入操作が実行され、新しいノードの後続ノードnextがスタックトップノードを指すようになります。その後、スタックトップポインタが新しいノードnodeを指すように移動します。最後に、スタックの高さが 1 増えます。
ポップ（スタックから取り出す）#
/* ポップ（スタックから取り出す） */
void *stack_pop(stack *stack)
{
/* スタックトップ要素を一時的に保存 */
stack_node *curr = stack->top;
if (curr == NULL)
return NULL;
void *data = curr->data;
stack->top = stack->top->next;
free(curr);
stack->length--;
return data;
}
ポップするときは、まずスタックトップノードのポインタを一時的に保存し、スタックトップノードのデータフィールドの値を返す前に解放操作を行います。次に、スタックトップポインタをスタックトップノードの次のノードに移動します。最後に、一時的に保存したノードを解放し、スタックの高さを 1 減らし、データを返してポップ操作が完了します。
スタックのクリア#
/* スタック内のすべての要素をクリアするが、スタック自体は解放しない */
void stack_empty(stack *stack)
{
int length = stack->length;
stack_node *curr, *next;
curr = stack->top;
/* スタックの高さに基づいてノードの削除回数を決定する */
while (length--)
{
next = curr->next;
free(curr);
curr = next;
}
stack->length = 0;
stack->top = NULL;
}
スタックの解放#
/* スタック内のすべての要素をクリアし、スタックを解放する */
void stack_release(stack *stack)
{
stack_empty(stack);
free(stack);
}
テスト#
同様に、main 関数でテストします。
int main()
{
char a = 'a';
char b = 'b';
char c = 'c';
/* スタックを作成する */
stack *stack = stack_create();
printf("%p\n", stack_pop(stack));
/* プッシュする */
stack_push(stack, &a);
stack_push(stack, &b);
stack_push(stack, &c);
/* ポップする */
while (stack->length > 0)
{
printf("%c\n", *(char *)stack_pop(stack));
}
/* プッシュする */
stack_push(stack, &a);
stack_empty(stack);
printf("%p\n", stack_pop(stack));
/* スタックを解放する */
stack_release(stack);
return 0;
}
コンパイルして出力します。
# gcc -fsanitize=address -fno-omit-frame-pointer -g stack.c && ./a.out
(nil)
c
b
a
(nil)
完全なコード#
完全なコードについては、コードリストを参照してください。
https://github.com/austin2035/learn-data-structures