【C言語/データ構造】スタックとキューの配列での実装方法

このページでは「スタック」と「キュー」について解説した後、これらを「配列」で実装する方法と、実際に実装したソースコードの紹介を行なっていきたいと思います。

特にキューの実装時には「リングバッファ」を用いますので、キューの実装方法を理解することでリングバッファの知識も身につくと思います！

スタックとキュー

スタックとキューそれぞれの解説をする前に、まずスタックとキューについて簡単に説明しておきます。

まず共通点として、スタックとキュー両方ともコンピュータで利用されるデータ構造になります。要はコンピュータ上の「データを管理するもの」ですね。

スタックとキューのユーザー（使い手）からすると、スタックやキューを使えば、好きなタイミングでスタックやキューにデータを追加し、好きなタイミングでスタックやキューからデータを取り出すことができます。

逆にスタックとキューを実装する場合は、ユーザーから “データの追加の指示” を受け付けてデータを保存し、さらに ユーザーから “データの追加の指示” を受け付けて、保存したデータをユーザーに返却するような処理を実現してやる必要があります。

プログラミング的に考えると、この “指示” は “関数呼び出し” と考えて良いです（他にも “メッセージ” などの場合などもあります）。

ですので、要はスタックやキューを実装する場合は、主に下記の２つの関数を作ってやれば良いことになります。

• データの追加
• データの取り出し

で、これは後述でも説明しますが、スタックやキューの特徴はデータの取り出し順にあります。

スタックとキューのデータの取り出し順は下記のようになります。

• スタック：後から追加されたデータから順に取り出す
• キュー：先に追加されたからデータから順に取り出す

なので、スタックを実装する場合は「後から追加されたデータから順に取り出す」ことができるように、データの追加を行う関数とデータの取り出しを行う関数を作成する必要があります。

キューを実装する場合も同様で、「先に追加されたデータから順に取り出す」ことができるように、データの追加を行う関数とデータの取り出しを行う関数を作成する必要があります。

この辺りの解説を踏まえてここからの解説を読んでいただくと、スタックやキューの実装方法のイメージも湧きやすくなると思います。

では、ここからスタックとキューの個別の解説や実装方法やソースコードの紹介をしていきたいと思います。

スタックとは

スタックは後から追加されたデータから順にデータを取り出しするデータ構造です。

スタックのイメージを図で表すと下のようになります。出入り口が１つの入れ物に、データを積み重ねるようにしてデータを管理するイメージです。

先に追加したデータの方がスタックの下の方に積まれていくので、後から追加したデータの方がスタックの上の方に積まれることになります。

データの出入り口はこのスタックの上側にありますので、データを取り出す順は「後から追加されたデータから」になります。

こんな感じで、後から追加したデータから順にデータの取り出しが行われるデータ構造がスタックです。

一般的なスタックでは、このデータの取り出しを行うとスタックからはデータが削除されます。

例えるなら「本屋の店頭に積まれてる本」ですかね。

店員さんは本を積むときに、下側から順に本を積んでいきます。つまり、下側ほど先に積んだ本になります。

逆にお客さんは上側に積まれた本から順に買いますよね。つまり後に積まれた本から取り出されることになります（もちろん下側に積んである本を選んで買うこともできますけどね！）。

スタックにおいては、データを追加することを push、データを取り出すことを pop と呼びます。

が、今後の解説では特にこれらの用語は使用せずに、単に「データの追加」及び「データの取り出し」と呼ばせていただきます（ソースコードの関数名では push と pop を使用しています）。

スポンサーリンク

スタックの実装方法

では、先程紹介したスタックの実装方法について解説していきます。

今回は、このスタックを “配列を用いて” 実装していきたいと思います。

つまり、データ追加時には、追加するデータを配列に格納することで保存します。さらに、データ取り出し時には、その配列からデータを取得するようにします。

また、スタックに保存できるデータ数は配列のサイズとなります。

スタックとはで示したイメージ図で考えると、スタックの下側から順に配列の各要素が並んでる感じになります。スタックの図を時計回りに９０度回転して考えるとイメージと配列の関係がわかりやすくなると思います。

データの追加とデータの取り出しの考え方

スタックは「後から追加されたデータから順に取り出す」ところがポイントなので、これを実現できるように、今回は下記のようにデータ追加とデータ取り出しを行うようにしたいと思います。

• スタックへのデータの追加：
  • 配列の “空の要素を除いた” 最後尾の位置の “１つ後ろ” の位置にデータを格納
    
• スタックからのデータの取り出し：
  • 配列の “空の要素を除いた” 最後尾の位置からデータを取得
    

“位置” というと抽象的ですので、配列の場合は “空の要素を除いた” 最後尾の要素の “添字” と考えると具体的なイメージがつきやすいと思います。

また、以降では、配列の “空の要素を除いた” 最後尾の位置」を「データの最後尾」と略させていただきます。

データの最後尾の管理

上記のようにデータの追加とデータの取り出しを行えば、データ取り出し時には、常に後から追加されたデータが取得されるようになります。

ただし、これを実現するためには、「データの最後尾」がどこであるかを管理しておく必要があります。

データの追加を行うとデータの最後尾は１つ後ろの位置に移動しますし、データの取り出しを行うとデータの最後尾は１つ前に移動することになります。

ですので、データの追加時やデータの取り出し時には、配列に対するデータの格納やデータの取得だけでなく、データの最後尾の更新も行う必要があります。

このデータの最後尾をしっかり管理するところが、スタック実装のポイントになります。

スポンサーリンク

スポンサーリンク

データの追加とデータの取り出しの実装

例えばデータを格納する配列を data、配列のサイズを MAX_NUM、データの最後尾を管理する変数を tail とします。

つまり、tail は配列における “空の要素を除いた” 最後尾の要素の添字 です。

この時スタックとしては、data[0] から data[tail] まではデータが既に格納されており、data[tail + 1] から data[MAX_NUM - 1] までは空であることになります。

ですので、次にデータを追加する際のデータの格納先は data[tail + 1] になります。

さらに、データ追加後は、データの最後尾も１つ後ろにずれるので、tail の値もインクリメントしてやる必要があります。

また、次にデータを取り出しする際のデータの格納先は data[tail] になります。

さらに、データ取り出し後は、データの最後尾も１つ前にずれるので、tail の値もデクリメントしてやる必要があります。

スタックを実装したソースコード

ここまで解説してきた内容を踏まえてスタックを実装したソースコードは下記のようになります。

#include <stdio.h>

/* 管理するデータの上限個数 */
#define MAX_NUM 10

/* スタック構造体 */
typedef struct STACK {
    /* データの最後尾 */
    int tail;
    /* スタックされているデータ */
    int data[MAX_NUM];
} STACK_T;

void initStack(STACK_T*);
void printStack(STACK_T*);
void push(STACK_T*, int);
int pop(STACK_T*);

/* スタックを初期化する関数 */
void initStack(STACK_T *stack){

    /* スタックを空に設定 */
    stack->tail = -1;
}

/* PUSHする関数 */
void push(STACK_T *stack, int input){

    /* スタックが満杯なら何もせず関数終了 */
    if(stack->tail >= MAX_NUM - 1){
        printf("スタックが満杯でPUSHできません\n");
        return;
    }

    /* データをデータの最後尾の１つ後ろに格納 */
    stack->data[stack->tail + 1] = input;

    /* データの最後尾を１つ後ろに移動 */
    stack->tail = stack->tail + 1;
}

/* POPする関数 */
int pop(STACK_T *stack){
    int ret = 0;

    /* スタックが空なら何もせずに関数終了 */
    if(stack->tail == -1){
        printf("スタックが空です\n");
        return -1;
    }

    /* データの最後尾からデータを取得 */
    ret = stack->data[stack->tail];

    /* データの最後尾を１つ前にずらす */
    stack->tail = stack->tail - 1;

    /* 取得したデータを返却 */
    return ret;
}

/* スタックの中身を表示 */
void printStack(STACK_T *stack){
    int i = 0;

    printf("左側がスタックの上側を表しています\n");
    for(i = 0; i <= stack->tail; i++){
        printf("%d,", stack->data[stack->tail - i]);
    }
    printf("\n");
}

int main(void){

    int m;
    int input;
    int output;
    STACK_T stack;

    /* スタックを初期化 */
    initStack(&stack);

    while(1){
        /* ユーザからメニューを選んでもらう */
        printf("メニュー\n 1:PUSH\n 2:POP\n 3:スタック表示\n それ以外の数字:終了\n");
        scanf("%d", &m);

        /* 選ばれたメニューに応じて処理を分岐 */
        if(m == 1){
            printf("PUSHする数は？（正の整数のみ化）");
            scanf("%d", &input);
            if (input < 0) {
                printf("負の値は受け付けていません!\n");
                continue;
            }
            printf("%dをPUSHします\n", input);
            push(&stack, input);
        }else if(m == 2){
            printf("POPします\n");
            output = pop(&stack);
            if(output != -1){
                printf("%dをPOPしました\n", output);
            }
        } else if(m == 3){
            printf("スタックの中身を表示します\n");
            printStack(&stack);
        } else {
            /* 1, 2, 3以外の場合はwhile文を抜け出すためにbreakを実行 */
            printf("終了します\n");
            break;
        }
    }
    return 0;
}

STACK_T 構造体を下記のように定義しており、data が追加したデータを格納する配列で、tail がデータの最後尾を管理するための変数になっています。

/* スタック構造体 */
typedef struct STACK {
    /* データの最後尾 */
    int tail;
    /* スタックされているデータ */
    int data[MAX_NUM];
} STACK_T;

data の型は int なので、スタックに追加できるデータは int 型の数値となります。この data の型を変更すれば、例えば文字列などをスタックに追加していくようなこともできます。

また、データの追加を行う関数は push、データの取り出しを行う関数は pop となっています。これらの関数はスタックの実装方法で解説した内容と照らし合わせて見ていただければ内容はすぐ理解できると思います。

ポイントは push と pop での tail の更新を行うところです。

プログラムを実行すれば、下記のような文字列が表示され、この案内に従って数字を入力していくことで、データの追加やデータの取り出し、スタックの内容の表示などを行うことができます。

メニュー
 1:PUSH
 2:POP
 3:スタック表示
 それ以外の数字:終了

スタックを表示しながら、色々データを追加したりデータを取り出したりしてみることで、よりスタックの理解も深まると思います！

キューとは

キューは先に追加されたデータから順にデータを取り出しするデータ構造です。

キューのイメージを図で表すと下のようになります。出入り口が別になっている入れ物にデータを詰めて管理するイメージです。

先に追加したデータの方が出口に近く、後から追加したデータの方が入り口近いデータ構造になります。

ですので、データを取り出す順は「先に追加されたデータから」になります。

こんな感じで、先に追加したデータから順にデータの取り出しが行われるデータ構造がキューです。

一般的なキューでは、このデータの取り出しを行うとキューからはデータが削除されます。

イメージしやすいのは買い物でのレジ待ちの行列です。先に並んだ人から先に会計してもらえますよね？

キューにおいては、データを追加することを enqueue、データを取り出すことを dequeue と呼びます。が、今後の解説では特にこれらの用語は使用せずに、単に「データの追加」及び「データの取り出し」と呼ばせていただきます（ソースコードの関数名では enqueue と dequeue を使用しています）。

スポンサーリンク

キューの実装方法

では先程紹介したキューの実装方法について解説していきます。

ここでは、このキューを “配列を用いて” 実装していきたいと思います。

つまり、データ追加時には、追加するデータを配列に格納することで保存します。さらに、データ取り出し時には、その配列からデータを取得するようにします。

キューとはで示したイメージ図で考えると、キューそのものが配列になる感じですね。そして、入り口に近い方から順に配列の各要素が並んでいる感じになります。

データの追加とデータの取り出しの考え方

で、キューは「先に追加されたデータから順に取り出す」ところがポイントなので、これを実現できるように、今回は下記のようにデータ追加とデータ取り出しを行うようにしたいと思います。

• キューへのデータの追加：
  • 配列の “空の要素を除いた” 最後尾の位置の “１つ後ろ” の位置にデータを格納
    
• キューからのデータの取り出し：
  • 配列の “空の要素を除いた” 先頭の位置からデータを取得
    

以降では、配列の “空の要素を除いた” 最後尾の位置」を「データの最後尾」、配列の “空の要素を除いた”先頭の位置」を「データの先頭」とそれぞれ略させていただきます。

データの最後尾とデータの先頭の管理

上記のようにデータの追加とデータの取り出しを行えば、データ取り出し時には、常に先に追加されたデータが取得されるようになります。

ただし、これを実現するためには、「データの最後尾」と「データの先頭」がどこであるかを管理しておく必要があります。

最後尾の場合はスタックと同じです。要は、データの追加を行うとデータの最後尾は１つ後ろの位置に移動することになります。

一方で、データの取り出しを行うとデータの先頭が１つ後ろの位置に移動することになります。

キューでは、このデータの最後尾とデータの先頭をしっかり管理するところが実装のポイントになります。

スポンサーリンク

スポンサーリンク

データの追加とデータの取り出しの実装

例えばデータを格納する配列を data、配列のサイズを MAX_NUM、データの最後尾を管理する変数を tail、データの先頭を管理する変数を head とします。

つまり、tail は配列における “空の要素を除いた” 最後尾の要素の添字で、head は配列における “空の要素を除いた” 先頭の要素の添字です。

この時、キューとしては、data[head] から data[tail] まではデータが既に格納されており、data[0] から data[head - 1] と data[tail + 1] から data[MAX_NUM - 1] までは空であることになります。

ですので、次にデータを追加する際のデータの格納先は data[tail + 1] になります。

さらに、データ追加後は、データの最後尾も１つ後ろにずれるので、tail の値もインクリメントしてやる必要があります。

また、次にデータを取り出しする際のデータの格納先は data[head] になります。

さらに、データ取り出し後は、データの先頭も１つ後ろにずれるので、head の値もインクリメントしてやる必要があります。

リングバッファの導入

上記のように実装すれば、「先に追加されたデータから順に取り出す」ことを実現することができます。

配列では格納できるデータの数がどんどん減っていく

ですが、キューの場合はスタックの場合とは異なり、データの取り出し時にも「データの先頭が後ろにずれる」ことになります。

ですので、データの追加やデータの取り出しを繰り返すと、データの先頭が後ろにどんどんずれていくことになります。

つまり、データの先頭が前側に戻ることがないので、キューからデータを取り出して空きになった要素が再利用されることがありません。

なので、キューに格納できるデータの個数がどんどん減っていくことになり、最終的には１つもデータが格納できなくなってしまいます。

リングバッファを用いて空きの要素を再利用する

これだと非常に使い勝手が悪いので、ここではリングバッファの考え方を取り入れてこの課題を解決したいと思います。

バッファというのはデータを一時的に保存しておくもののことを言います。今回は配列がこのバッファになります。

さらにリングバッファは、バッファの終端とバッファの先頭が繋がっているバッファのことです。

今回バッファは配列なので、配列の終端の次の要素が配列の先頭になるように配列を扱うことで、リングバッファを実現します。

配列をリングバッファとして扱うことで、データの先頭が配列の終端になったとしても、また配列の先頭に戻り、配列の “空の要素” を再利用してデータを追加していくことができます。

つまり、これにより、常にキューには最大配列のサイズ分のデータが保存できることになります。

配列をリングバッファとして扱う方法

配列では、このリングバッファを、”配列の添字を扱う変数” への計算時に「配列のサイズでの剰余算」を行うようにすることで実現することができます。

例えば、データの追加時には data[tail + 1] ではなく、data[(tail + 1) % MAX_NUM] にデータを格納するようにします。これにより、tail + 1 が配列のサイズ MAX_NUM になった場合は、0 の要素にデータが追加されるようになります。

つまり、この剰余算を行うことで、配列の終端の次の要素が配列の先頭になるように配列を扱うことができます。

ポイントは “配列の添字を扱う変数” への計算時に剰余算をするのを忘れないことです。

これを忘れると配列のサイズを超えた位置にデータの追加を行ったりして、データアクセス違反が発生することもあります。

リングバッファの「空」と「満杯」の判断

配列をリングバッファと見立てて扱うだけてあれば、添字の計算時に剰余算を取れば良いだけなので結構簡単だと思います。

リングバッファでは「空」と「満杯」を見分けるのが難しい

ただし、単純にリングバッファとして扱うと「リングバッファが空なのか満杯なのかの見分けが付かない」という問題があります。

リングバッファが空である時、「データの最後尾」の１つ後ろの位置に「データの先頭」が存在することになります。

つまり、(tail + 1) % MAX_NUM == head を満たす時にリングバッファは空であるということになります。

ではリングバッファが満杯の時はどうでしょう？

実はこの場合も、「データの最後尾」の１つ後ろの位置に「データの先頭」が存在することになります。

つまり、(tail + 1) % MAX_NUM == head を満たす時にはリングバッファは空であるとも言えるし、満杯であるとも言えることになります。

こんな感じで「空」なのか「満杯」なのかの見分けが付きません…。

リングバッファで「空」と「満杯」を見分ける方法

これは「データの先頭の１つ後ろにはデータを追加しない」という制限を加えることで解決することができます。

この制限を加えれば、リングバッファが満杯の場合は、「データの最後尾」の２つ後ろの位置に「データの先頭」が存在することになります。

つまり、(tail + 2) % MAX_NUM == head を満たす時にはリングバッファは満杯であると判断できます。

すなわち、「空」なのか「満杯」なのかを異なる条件式で判断できるようになります。

ただし、「データの先頭の１つ後ろにはデータを追加しない」となると、配列のサイズ - 1 個のデータしかキューに保存できないということになります。

なので、配列のサイズは、キューに保存したいデータの個数 + 1 に設定する必要があります。

リングバッファを利用した際の「空」と「満杯」を見分けるための方法をまとめると、下記のようになります。

• head の１つ後ろにはデータを追加できないようにする
• 空であるかどうかは下記で判断する
  • (tail + 1) % MAX_NUM == head
• 満杯であるかどうかは下記で判断する
  • (tail + 2) % MAX_NUM == head
• 配列のサイズ（リングバッファのサイズ）は キューに保存したいデータの個数 + 1 とする

スポンサーリンク

キューを実装したソースコード

ここまで解説してきた内容を踏まえてキューを実装したソースコードは下記のようになります。

#include <stdio.h>

/* 管理するデータの上限個数+1 */
#define MAX_NUM (10+1)

/* キュー構造体 */
typedef struct QUEUE {
    /* データの最後尾 */
    int tail;
    /* データの先頭 */
    int head;
    /* キューされているデータ */
    int data[MAX_NUM];
} QUEUE_T;

void initQueue(QUEUE_T*);
void printQueue(QUEUE_T*);
void enqueue(QUEUE_T*, int);
int dequeue(QUEUE_T*);

/* キューを初期化する関数 */
void initQueue(QUEUE_T *queue){

    /* キューを空に設定 */
    queue->head = 0;
    queue->tail = -1;
}

/* ENQUEUEする関数 */
void enqueue(QUEUE_T *queue, int input){

    /* キューが満杯なら何もせず関数終了 */
    if((queue->tail + 2) % MAX_NUM == queue->head){
        printf("キューが満杯でENQUEUEできません\n");
        return;
    }

    /* データをデータの最後尾の１つ後ろに格納 */
    queue->data[(queue->tail + 1) % MAX_NUM] = input;

    /* データの最後尾を１つ後ろに移動 */
    queue->tail = (queue->tail + 1) % MAX_NUM;
}

/* DEQUEUEする関数 */
int dequeue(QUEUE_T *queue){
    int ret = 0;

    /* キューが空なら何もせずに関数終了 */
    if((queue->tail + 1) % MAX_NUM == queue->head){
        printf("キューが空です\n");
        return -1;
    }

    /* データの先頭からデータを取得 */
    ret = queue->data[queue->head];

    /* データの先頭を１つ後ろにずらす */
    queue->head = (queue->head + 1) % MAX_NUM;

    /* 取得したデータを返却 */
    return ret;
}

/* キューの中身を表示 */
void printQueue(QUEUE_T *queue){
    int i = 0;
    int num;

    /* キュー内のデータの個数を計算 */
    if (queue->tail < queue->head) {
        num = queue->tail + MAX_NUM - queue->head + 1;
    } else {
        num = queue->tail - queue->head + 1;
    }

    printf("左側がキューの出口側を表しています\n");
    for(i = 0; i < num; i++){
        /* データの先頭からnum個分のデータを表示 */
        printf("%d,", queue->data[(queue->head + i) % MAX_NUM]);
    }
    printf("\n");
}

int main(void){

    int m;
    int input;
    int output;
    QUEUE_T queue;

    /* キューを初期化 */
    initQueue(&queue);

    while(1){
        /* ユーザからメニューを選んでもらう */
        printf("メニュー\n 1:ENQUEUE\n 2:DEQUEUE\n 3:キュー表示\n それ以外の数字:終了\n");
        scanf("%d", &m);

        /* 選ばれたメニューに応じて処理を分岐 */
        if(m == 1){
            printf("ENQUEUEする数は？（正の整数のみ化）");
            scanf("%d", &input);
            if (input < 0) {
                printf("負の値は受け付けていません!\n");
                continue;
            }
            printf("%dをENQUEUEします\n", input);
            enqueue(&queue, input);
        }else if(m == 2){
            printf("DEQUEUEします\n");
            output = dequeue(&queue);
            if(output != -1){
                printf("%dをDEQUEUEしました\n", output);
            }
        } else if(m == 3){
            printf("キューの中身を表示します\n");
            printQueue(&queue);
        } else {
            /* 1, 2, 3以外の場合はwhile文を抜け出すためにbreakを実行 */
            printf("終了します\n");
            break;
        }
    }
    return 0;
}

QUEUE_T 構造体を下記のように定義しており、data が追加したデータを格納する配列で、tail がデータの最後尾を管理するための変数、head がデータの先頭を管理するための変数になっています。

/* キュー構造体 */
typedef struct QUEUE {
    /* データの最後尾 */
    int tail;
    /* データの先頭 */
    int head;
    /* キューされているデータ */
    int data[MAX_NUM];
} QUEUE_T;

スタック同様に data の型は int としていますが、この data の型を変更すれば数値以外のデータもキューに追加することもできるようになります。

また、データの追加を行う関数は enqueue、データの取り出しを行う関数は dequeue となっています。これらの関数はキューの実装方法で解説した内容と照らし合わせて見ていただければ内容はすぐ理解できると思います。

enqueue と dequeue のポイントは下記の３点だと思います。

• tail や head の更新を行うところ
• 配列 data をリングバッファとして扱うために添字計算時には毎回剰余算を実行するところ
• キューの「空」「満杯」の判断の仕方

プログラムを実行すれば、下記のような文字列が表示され、この案内に従って数字を入力していくことで、データの追加やデータの取り出し、キューの内容の表示などを行うことができます。

メニュー
 1:ENQUEUE
 2:DEQUEUE
 3:キュー表示
 それ以外の数字:終了

リングバッファを使わないキューの実装方法

ここまで「リングバッファ」を用いることを前提にキューを実装してきましたが、実はリングバッファを用いなくてもキューを実現することはできます。

これは「データの先頭を固定」することで実現することができます。

キューの実装方法で紹介した「データの取り出し」では、データの取り出しを行なった後に、データの先頭を後ろにずらすようにしていたため、データの先頭がどんどん後ろ側にずれていってしまうという問題がありました。なのでリングバッファを利用しましたね！

逆に考えると、リングバッファを使用しないで済むようにするためには、データの取り出し時にデータの先頭を後ろにずらさないようにすれば良いことになります。

なので、データの取り出し時にはデータの先頭を後ろにずらすのではなく、取り出した位置の後ろ側のデータ全てを１つ前に移動させるようにします（データの最後尾も１つ前に移動する）。

これによって、データの先頭は常に配列の先頭と一致します。

データの先頭が後ろにずれるようなこともないので、リングバッファを利用する必要もないですし、データの先頭が常に配列の先頭と一致するため、もはやデータの先頭を管理する必要もなくなります。

リングバッファを使わずに実装したキューのソースコード

この方法でキューを実装したソースコードが下記になります。

#include <stdio.h>

/* 管理するデータの上限個数 */
#define MAX_NUM (10)

/* キュー構造体 */
typedef struct QUEUE {
    /* データの最後尾 */
    int tail;
    /* キューされているデータ */
    int data[MAX_NUM];
} QUEUE_T;

void initQueue(QUEUE_T*);
void printQueue(QUEUE_T*);
void enqueue(QUEUE_T*, int);
int dequeue(QUEUE_T*);

/* キューを初期化する関数 */
void initQueue(QUEUE_T *queue){

    /* キューを空に設定 */
    queue->tail = -1;
}

/* ENQUEUEする関数 */
void enqueue(QUEUE_T *queue, int input){

    /* キューが満杯なら何もせず関数終了 */
    if(queue->tail == MAX_NUM - 1){
        printf("キューが満杯でENQUEUEできません\n");
        return;
    }

    /* データをデータの最後尾の１つ後ろに格納 */
    queue->data[queue->tail + 1] = input;

    /* データの最後尾を１つ後ろに移動 */
    queue->tail = queue->tail + 1;
}

/* DEQUEUEする関数 */
int dequeue(QUEUE_T *queue){
    int ret = 0;
    int i;

    /* キューが空なら何もせずに関数終了 */
    if(queue->tail == -1){
        printf("キューが空です\n");
        return -1;
    }

    /* データの先頭からデータを取得 */
    ret = queue->data[0];

    /* データの先頭より後ろのデータを１つずつ前にずらす */
    for (i = 0; i < queue->tail; i++) {
        queue->data[i] = queue->data[i + 1];
    }

    /* データの最後尾も１つ前にずらす */
    queue->tail = queue->tail - 1;

    /* 取得したデータを返却 */
    return ret;
}

/* キューの中身を表示 */
void printQueue(QUEUE_T *queue){
    int i = 0;
    
    printf("左側がキューの出口側を表しています\n");
    for(i = 0; i <= queue->tail; i++){
        printf("%d,", queue->data[i]);
    }
    printf("\n");
}

int main(void){

    int m;
    int input;
    int output;
    QUEUE_T queue;

    /* キューを初期化 */
    initQueue(&queue);

    while(1){
        /* ユーザからメニューを選んでもらう */
        printf("メニュー\n 1:ENQUEUE\n 2:DEQUEUE\n 3:キュー表示\n それ以外の数字:終了\n");
        scanf("%d", &m);

        /* 選ばれたメニューに応じて処理を分岐 */
        if(m == 1){
            printf("ENQUEUEする数は？（正の整数のみ化）");
            scanf("%d", &input);
            if (input < 0) {
                printf("負の値は受け付けていません!\n");
                continue;
            }
            printf("%dをENQUEUEします\n", input);
            enqueue(&queue, input);
        }else if(m == 2){
            printf("DEQUEUEします\n");
            output = dequeue(&queue);
            if(output != -1){
                printf("%dをDEQUEUEしました\n", output);
            }
        } else if(m == 3){
            printf("キューの中身を表示します\n");
            printQueue(&queue);
        } else {
            /* 1, 2, 3以外の場合はwhile文を抜け出すためにbreakを実行 */
            printf("終了します\n");
            break;
        }
    }
    return 0;
}

ポイントは dequeue 関数の中で、データの取り出しが終わった後にデータの先頭より後ろ側のデータを１つずつ前側にコピーしているところになります。

リングバッファも head も使わなくなっているのでソースコードもスッキリしていますし、ほぼスタックと同じ実装でキューを実現することができています。

簡単に実装できるというメリットがある一方で、この方法だと dequeue が遅いというデメリットがあります。今回はキューのサイズが小さいのであまり目立ちませんが、”データの先頭より後ろのデータを全て” １つずつ前側にコピーする必要があるので、データ数が多くなればなるほど遅くなるという問題があります。

とにかく簡単にキューを実装したい場合はこの方法でも良いですが、実用的なキューを実装しようと思うと、やはりリングバッファを利用したキューの方が良いと思います。

スポンサーリンク

まとめ

このページでは、スタックとキューについて解説し、これらの配列を用いた実装方法の解説及び実際に実装したC言語ソースコードの紹介を行いました。

スタックもキューもどちらも「データの最後尾」と「データの先頭（キューのみ）」を管理することが重要で、これらを上手く管理できれば割と簡単に実装できるのではないかと思います。

ただキューの場合は、実用性を考えるとリングバッファを用いる必要があり、配列をリングバッファとして扱うところ（特に「空」と「満杯」を区別するところ）がちょっと難易度が高いかなぁと思います。

リングバッファの考え方は重要なものですし、さまざまな場面で活用できますので、是非この機会にこのリングバッファについてもしっかり理解しておきましょう！

「キュー」を “ポインタを用いて” 実装する方法やそのソースコードは下記ページで紹介していますので、ポインタでの実装方法に興味のある方は是非下記ページも読んでいただければと思います。

【C言語】キューのポインタでの実装方法

おすすめ参考書（PR）

もっとスタックやキューなどのデータ構造について学びたい方は下記の書籍がオススメです。スタックやキューだけでなく、リスト構造も学べますし、アルゴリズムも探索・ソート法などをC言語と一緒に学ぶことができます。

新・明解C言語で学ぶアルゴリズムとデータ構造

posted with ヨメレバ

柴田 望洋 SBクリエイティブ 2017年02月09日

楽天ブックス

Amazon

e-hon