データ構造 - スタック
スタック(Stack)は、後入れ先出し(Last In First Out、LIFO)の原則に従う線形データ構造です。積み重ねた皿のように、一番上からしか置けず、一番上からしか取り出せないと理解できます。
スタックの概念と原理
スタック (Stack) — LIFO 原理の模式図
スタックトップ (Top) — ここからしか操作できない
皿 1 (スタックの底)
皿 2
皿 3
皿 4 (スタックトップ)
スタックの底 (Bottom) — 最後にしか取り出せない
▲ push(プッシュ)
▼ pop(ポップ)
LIFO の確認:プッシュ 10→20→30、ポップ 30→20→10(後入れ先出し)| スタックはスタックトップのみを扱い、中間は気にしない
配列による実装(順序スタック)
格納:固定サイズ配列 + top ポインタ
push:items[++top] = value
pop:return items[top--]
利点:アクセスが速い、キャッシュに優しい、実装が簡単
欠点:容量が固定、オーバーフローする可能性がある
連結リストによる実装(連結スタック)
格納:動的ノード + スタックトップポインタ(連結リストの先頭)
push:先頭挿入法 newNode->next = top
pop:top = top->next; free(旧先頭)
利点:容量制限なし、柔軟に動的拡張可能
欠点:余分なポインタのオーバーヘッド、キャッシュに不向き
配列によるスタックの実装
例
#include <stdio.h>
#include <stdbool.h> /* bool 型 */
#define MAX_SIZE 100 /* スタックの最大容量 */
/* スタック構造体:データ配列とスタックトップポインタを含む */
struct Stack {
int items[MAX_SIZE]; /* スタック要素を格納する配列 */
int top; /* スタックトップポインタ、-1 はスタックが空を表す */
};
/* スタックの初期化:top を -1 にする */
void initStack(struct Stack* s) {
s->top = -1;
}
/* 空判定:top が -1 のときスタックは空 */
bool isEmpty(struct Stack* s) {
return s->top == -1;
}
/* 満杯判定:top が容量上限 -1 に達したときスタックは満杯 */
bool isFull(struct Stack* s) {
return s->top == MAX_SIZE - 1;
}
/* プッシュ(push):要素をスタックトップに置く
先に top を移動し、それからデータを書き込む */
void push(struct Stack* s, int value) {
if (isFull(s)) {
printf("スタックが満杯のため、プッシュできません!\n");
return;
}
s->items[++s->top] = value; /* top を先に +1 し、それから代入する */
printf("プッシュ: %d\n", value);
}
/* ポップ(pop):スタックトップの要素を削除して返す
先にデータを取り出し、それから top を移動する */
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("スタックが空のため、ポップできません!\n");
return -1; /* 特殊な値を返してエラーを表す */
}
return s->items[s->top--]; /* 先に値を返し、top を 1 減らす */
}
/* スタックトップの参照(peek):ポップせず、参照のみ */
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("スタックが空です!\n");
return -1;
}
return s->items[s->top];
}
int main() {
struct Stack s;
initStack(&s);
push(&s, 10); /* プッシュ: 10 */
push(&s, 20); /* プッシュ: 20 */
push(&s, 30); /* プッシュ: 30 */
printf("スタックトップの要素: %d\n", peek(&s)); /* 出力: スタックトップの要素: 30 */
printf("ポップ: %d\n", pop(&s)); /* 出力: ポップ: 30(後入れ先出し) */
printf("ポップ: %d\n", pop(&s)); /* 出力: ポップ: 20 */
printf("ポップ: %d\n", pop(&s)); /* 出力: ポップ: 10 */
if (isEmpty(&s)) {
printf("スタックは空です\n"); /* 出力: スタックは空です */
}
return 0;
}
#include <stdbool.h> /* bool 型 */
#define MAX_SIZE 100 /* スタックの最大容量 */
/* スタック構造体:データ配列とスタックトップポインタを含む */
struct Stack {
int items[MAX_SIZE]; /* スタック要素を格納する配列 */
int top; /* スタックトップポインタ、-1 はスタックが空を表す */
};
/* スタックの初期化:top を -1 にする */
void initStack(struct Stack* s) {
s->top = -1;
}
/* 空判定:top が -1 のときスタックは空 */
bool isEmpty(struct Stack* s) {
return s->top == -1;
}
/* 満杯判定:top が容量上限 -1 に達したときスタックは満杯 */
bool isFull(struct Stack* s) {
return s->top == MAX_SIZE - 1;
}
/* プッシュ(push):要素をスタックトップに置く
先に top を移動し、それからデータを書き込む */
void push(struct Stack* s, int value) {
if (isFull(s)) {
printf("スタックが満杯のため、プッシュできません!\n");
return;
}
s->items[++s->top] = value; /* top を先に +1 し、それから代入する */
printf("プッシュ: %d\n", value);
}
/* ポップ(pop):スタックトップの要素を削除して返す
先にデータを取り出し、それから top を移動する */
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("スタックが空のため、ポップできません!\n");
return -1; /* 特殊な値を返してエラーを表す */
}
return s->items[s->top--]; /* 先に値を返し、top を 1 減らす */
}
/* スタックトップの参照(peek):ポップせず、参照のみ */
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("スタックが空です!\n");
return -1;
}
return s->items[s->top];
}
int main() {
struct Stack s;
initStack(&s);
push(&s, 10); /* プッシュ: 10 */
push(&s, 20); /* プッシュ: 20 */
push(&s, 30); /* プッシュ: 30 */
printf("スタックトップの要素: %d\n", peek(&s)); /* 出力: スタックトップの要素: 30 */
printf("ポップ: %d\n", pop(&s)); /* 出力: ポップ: 30(後入れ先出し) */
printf("ポップ: %d\n", pop(&s)); /* 出力: ポップ: 20 */
printf("ポップ: %d\n", pop(&s)); /* 出力: ポップ: 10 */
if (isEmpty(&s)) {
printf("スタックは空です\n"); /* 出力: スタックは空です */
}
return 0;
}
連結リストによるスタックの実装
例
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/* 連結リストのノード */
struct Node {
int data;
struct Node* next;
};
/* プッシュ(push):連結リストの先頭をスタックトップとし、先頭挿入法
時間計算量:O(1) */
struct Node* push(struct Node* top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top; /* 新しいノードが元のスタックトップを指す */
printf("プッシュ: %d\n", value);
return newNode; /* 新しいノードが新しいスタックトップになる */
}
/* ポップ(pop):連結リストの先頭ノードを削除する
時間計算量:O(1) */
struct Node* pop(struct Node* top) {
if (top == NULL) {
printf("スタックが空です!\n");
return NULL;
}
struct Node* temp = top;
printf("ポップ: %d\n", top->data);
top = top->next; /* スタックトップを後へ移動 */
free(temp); /* 古いスタックトップを解放 */
return top;
}
/* 空判定 */
bool isEmpty(struct Node* top) {
return top == NULL;
}
int main() {
struct Node* stackTop = NULL; /* 初期状態ではスタックは空 */
stackTop = push(stackTop, 100); /* プッシュ: 100 */
stackTop = push(stackTop, 200); /* プッシュ: 200 */
stackTop = push(stackTop, 300); /* プッシュ: 300 */
printf("スタックトップ: %d\n", stackTop->data); /* 出力: スタックトップ: 300 */
stackTop = pop(stackTop); /* ポップ: 300 */
stackTop = pop(stackTop); /* ポップ: 200 */
stackTop = pop(stackTop); /* ポップ: 100 */
if (isEmpty(stackTop)) {
printf("スタックは空です\n"); /* 出力: スタックは空です */
}
return 0;
}
#include <stdlib.h>
#include <stdbool.h>
/* 連結リストのノード */
struct Node {
int data;
struct Node* next;
};
/* プッシュ(push):連結リストの先頭をスタックトップとし、先頭挿入法
時間計算量:O(1) */
struct Node* push(struct Node* top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top; /* 新しいノードが元のスタックトップを指す */
printf("プッシュ: %d\n", value);
return newNode; /* 新しいノードが新しいスタックトップになる */
}
/* ポップ(pop):連結リストの先頭ノードを削除する
時間計算量:O(1) */
struct Node* pop(struct Node* top) {
if (top == NULL) {
printf("スタックが空です!\n");
return NULL;
}
struct Node* temp = top;
printf("ポップ: %d\n", top->data);
top = top->next; /* スタックトップを後へ移動 */
free(temp); /* 古いスタックトップを解放 */
return top;
}
/* 空判定 */
bool isEmpty(struct Node* top) {
return top == NULL;
}
int main() {
struct Node* stackTop = NULL; /* 初期状態ではスタックは空 */
stackTop = push(stackTop, 100); /* プッシュ: 100 */
stackTop = push(stackTop, 200); /* プッシュ: 200 */
stackTop = push(stackTop, 300); /* プッシュ: 300 */
printf("スタックトップ: %d\n", stackTop->data); /* 出力: スタックトップ: 300 */
stackTop = pop(stackTop); /* ポップ: 300 */
stackTop = pop(stackTop); /* ポップ: 200 */
stackTop = pop(stackTop); /* ポップ: 100 */
if (isEmpty(stackTop)) {
printf("スタックは空です\n"); /* 出力: スタックは空です */
}
return 0;
}
連結リストによるスタックの利点は、理論上固定の容量制限がなく、システムの利用可能メモリのみに制限されることです。ただし、各ノードには追加のポインタ用記憶領域が必要です。
スタックの応用場面
| 応用場面 | 説明 | なぜスタックを使うのか |
|---|---|---|
| 関数呼び出しスタック | 関数の戻り先アドレスとローカル変数を保存する | 関数呼び出しは入れ子になっており、自然と LIFO になる |
| 括弧の対応 | コード内の括弧が正しく対応しているかを検査する | 左括弧が出たらスタックにプッシュし、右括弧がスタックトップと対応したらポップする |
| 元に戻す操作 | テキストエディタやブラウザの元に戻す機能 | 操作のたびにスタックにプッシュし、元に戻すときにポップする |
| 式の評価 | 中置記法/後置記法の式の値を計算する | オペランドをスタックにプッシュし、演算子で計算した結果をスタックにプッシュする |
| 深さ優先探索 | グラフの DFS 走査アルゴリズム | 明示的にスタックまたは再帰を使用(暗黙的に呼び出しスタックを使用) |