【C言語】データ構造の基本を学ぼう！スタックとキューを配列で実装する

f:id:paiza:20180910132940p:plain こんにちは。倉内です。

プログラムでデータを効率よく扱うために欠かせないのが「データ構造」の理解です。

データ構造というとなんだか難しそうな感じがしますが、配列や連結リストもデータ構造のひとつであり、プログラミング学習中の方は実際にコードを書いたこともあると思います。

他にもスタックとキューや木構造、グラフなどのデータ構造がありますが、今回はその中でも基本となるスタックとキューについて学べる動画講座「C言語入門編9: データ構造について理解しよう」を紹介します。

まずはスタックとキューがどのようなデータ構造かを理解し、配列を使って実装する方法を学びます。最終的にはRPGの攻撃シーンのようなプログラムを作成しましょう！

C言語でデータ構造を学ぼう

本題に入る前にC言語の基本を押さえておきたいという方は「C言語入門編」を受講してみてください。

特に配列についてはこちらの講座で復習しておくと、このあとの内容が理解しやすいと思います。

C言語入門編4: 配列の基礎

スタックとキューとは？

「＃01:スタックとキューについて学習しよう」より

スタックとキューは以下のような特徴があり、データを追加することをプッシュ（push）、取り出すことをポップ（pop）と表現することが多いです。

スタック

スタックは最後に追加したデータを最初に取り出す、後入れ先出し方式です。LIFO（Last In First Out）と呼ばれます。

図のようにお皿を積み重ねて、取るときをイメージすると分かりやすいと思います。

キュー

キューは最初に追加したデータを最初に取り出す、先入れ先出し方式です。FIFO（First In First Out）と呼ばれます。

図のように列に最初に並んだ人から注文できるというのをイメージすると分かりやすいと思います。

配列で実装してみよう

スタックとキューがどういったものか分かったので、さっそくC言語で実装していきましょう。

はじめにスタックを配列で実装する方法を学習します。スタックの基本操作は、データの追加（push）と削除（pop）ですよね。

「＃02:スタックを実装しよう (1)」より

paizaラーニングではこの画面のように左側に学習動画、右側にエディタという構成になっているため、動画の説明を見てすぐにコードを書いて実行することができます。

まずは基本操作をさせるための準備からです。動画で説明があったコードを書いてみると…

#include <stdio.h>

#define N 10
typedef int data_t;

data_t stack[N];
int size;

void init(void)
{
    size = 0;
}

int main(void)
{

}

ここではスタックのサイズをマクロを使って定義しています。defineマクロは、配列の大きさを後から変更するときなどに便利です。

次のチャプターで実際にデータの追加と削除の処理を実装します。

「＃03:スタックを実装しよう (2)」より

データ追加（push）の関数をこのように定義しました。

void push(data_t x)
{
    if (size >= N) {
        printf("stack overflow\n");
        return;
    }

    stack[size] = x;
    size++;
}

size 変数の値が N 以上のときは、それ以上データを追加できないので、「stack overflow」と出力して return で処理を終了させます。

つづいて、削除（pop）の関数はこのように定義しました。

void pop(data_t *x)
{
    if (size <= 0) {
        printf("stack underflow\n");
        return;
    }

    *x = stack[size - 1];
    size--;
}

今度はsize 変数の値が 0 以下のときは、それ以上データを取り出せないので、「stack underflow」と出力して return で処理を終了させます。

同様にキューの実装も「＃05:キューを実装しよう (1)」と「＃06:キューを実装しよう (2) 」で説明しています。

キューを応用してRPGの攻撃シーンを作ろう

ただデータの入出力の処理を書いてもあまりおもしろくないので、最後にRPGの攻撃シーンを想定した実装をしてみましょう！

「＃08:RPGの攻撃シーンをつくろう」より

ここではキューに構造体を追加して取り出したり、攻撃値をランダムな値で生成したりといった処理も扱っています。

    // main関数に定義するコードの一部
    // キューに追加する
    data_t slime = {"スライム", 5};
    data_t monster = {"モンスター", 10};
    data_t dragon = {"ドラゴン", 20};

    enqueue(slime);
    enqueue(monster);
    enqueue(dragon);

    // キューから取り出す
    data_t target;
    dequeue(&target);
    printf("%s\n", target.name);