C言語でのスタックの実装方法！

# スタックの実装方法 🎉

> データ構造としては特別なものではなく、配列や連結リストの“上手な使い方”の一つにすぎません。使いどころを理解することが大切です
>
> [Qiita: スタックとキューを極める！ 〜 考え方と使い所を特集 〜](https://qiita.com/drken/items/6a95b57d2e374a3d3292)

---

## 目次 📖

* [スタックとキューの違い ✨](#スタックとキューの違い-✨)
* [スタックADTとは？ 📚](#スタックadtとは-📚)
* [スタックの実装方法](#スタックの実装方法)

  * [1. 単純配列実装 🗃️](#1-単純配列実装-🗃️)
  * [2. 動的配列実装 🔄](#2-動的配列実装-🔄)
  * [3. 連結リスト実装 🌿](#3-連結リスト実装-🌿)
* [おわりに 🎯](#おわりに-🎯)

---

## スタックとキューの違い ✨

* **スタック** は LIFO（Last In, First Out）
* **キュー** は FIFO（First In, First Out）

|   操作  |     スタック     |      キュー     |
| :---: | :----------: | :----------: |
| 追加する時 |   一番上に追加 🆙  |   一番下に追加 🆗  |
| 取り出す時 | 一番上から取り出し 🆙 | 一番下から取り出し 🆗 |

---

## スタックADTとは？ 📚

**ADT（Abstract Data Type）** とは、操作の意味と性質を抽象化した“型”のことです。
スタックADTでは、主に以下の操作を定義します。

* **push(data)**：データを追加
* **pop()**：一番上のデータを取り出して削除
* **top()**：一番上のデータを参照（削除しない）
* **size()**：要素数を返す
* **isEmpty()**：空かどうか判定
* **isFull()**：満杯かどうか判定（配列実装のみ）
* **delete()**：メモリ解放

---

## スタックの実装方法

### 1. 単純配列実装 🗃️

#### データ構造

```c
typedef struct {
    int top;        // 現在の先頭位置（インデックス）
    int capacity;   // 配列の最大サイズ
    int *array;     // データを格納する配列
} ArrayStack;
```

#### 作成・初期化

```c
ArrayStack* createStack() {
    ArrayStack *stack = malloc(sizeof(ArrayStack));
    if (!stack) return NULL;
    stack->capacity = 4;     // 初期容量はお好みでOK
    stack->top      = -1;    // 空のときは -1
    stack->array    = malloc(sizeof(int) * stack->capacity);
    if (!stack->array) {
        free(stack);
        return NULL;
    }
    return stack;
}
```

#### 主要操作

**push**

```c
int push(ArrayStack *stack, int data) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return 0;
    }
    stack->array[++(stack->top)] = data;
    return 1;
}
```

**pop**

```c
int pop(ArrayStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return stack->array[(stack->top)--];
}
```

#### 補助操作

**top**

```c
int top(const ArrayStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return stack->array[stack->top];
}
```

**size**

```c
int size(const ArrayStack *stack) {
    return stack->top + 1;
}
```

**isEmpty**

```c
int isEmpty(const ArrayStack *stack) {
    return (stack->top == -1);
}
```

**isFull**

```c
int isFull(const ArrayStack *stack) {
    return (stack->top == stack->capacity - 1);
}
```

**delete**

```c
void deleteStack(ArrayStack *stack) {
    if (!stack) return;
    free(stack->array);
    free(stack);
}
```

> 単純配列実装はシンプルですが、容量変更ができません。

---

### 2. 動的配列実装 🔄

容量を自動で拡張できるよう、**繰り返し二倍法**を使います。

#### DoubleStack 関数例

```c
void doubleStack(ArrayStack *stack) {
    int newCap = stack->capacity * 2;
    int *newArr = malloc(sizeof(int) * newCap);
    if (!newArr) return;
    for (int i = 0; i <= stack->top; i++) {
        newArr[i] = stack->array[i];
    }
    free(stack->array);
    stack->array    = newArr;
    stack->capacity = newCap;
}
```

#### push の改良例

```c
int push(ArrayStack *stack, int data) {
    if (isFull(stack)) {
        doubleStack(stack);  // 足りなくなったら容量拡張！
    }
    stack->array[++(stack->top)] = data;
    return 1;
}
```

> 動的配列実装なら要素数の増加を自動でカバーできます。

---

### 3. 連結リスト実装 🌿

ノードを使ってリンクすることで、容量制限なしのスタックを実現します。

#### データ構造

```c
typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;  // 先頭ノードを指す
} LinkedStack;
```

#### 作成・初期化

```c
LinkedStack* createStack() {
    LinkedStack *stack = malloc(sizeof(LinkedStack));
    if (!stack) return NULL;
    stack->top = NULL;
    return stack;
}
```

#### 主要操作

**push**

```c
void push(LinkedStack *stack, int data) {
    Node *node = malloc(sizeof(Node));
    if (!node) return;
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}
```

**pop**

```c
int pop(LinkedStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    Node *node = stack->top;
    int val   = node->data;
    stack->top = node->next;
    free(node);
    return val;
}
```

#### 補助操作

**isEmpty**

```c
int isEmpty(const LinkedStack *stack) {
    return (stack->top == NULL);
}
```

**top**

```c
int top(const LinkedStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return stack->top->data;
}
```

**size**

```c
int size(const LinkedStack *stack) {
    int cnt = 0;
    for (Node *p = stack->top; p; p = p->next) cnt++;
    return cnt;
}
```

**delete**

```c
void deleteStack(LinkedStack *stack) {
    Node *p = stack->top;
    while (p) {
        Node *next = p->next;
        free(p);
        p = next;
    }
    free(stack);
}
```

> 連結リスト実装は容量を気にせずに使えて便利です✨

---

## おわりに 🎯

* **スタック** は LIFO、**キュー** は FIFO。
* 配列／動的配列／連結リストで実装方法が変わるだけ！
* 使いどころに応じて選んでみましょう😊

---

### 参考リンク 🔗

* [Qiita: スタックとキューを極める！](https://qiita.com/drken/items/6a95b57d2e374a3d3292)
* 入門『データ構造とアルゴリズム』（オライリー）ISBN:978-4-87311-634-1
* 『プログラミングコンテストチャレンジブック 第2版』ISBN:978-4839941062