【データ構造】スタックとキューをC言語で実装

このページではスタックとキューについての解説と、それぞれをC言語で実装したときのソースコードについて紹介していきたいと思います。

スタック

スタックとはデータ構造のひとつです。英語では”stack”と書きます。日本語に訳すと「積み重ねる」や「積み重ね」といった意味の単語になります。

スタックの特徴

特徴は、データを積み重ねるようにして管理し、後に入力されたデータから先に出力するようにデータを管理することです。

イメージしやすいのは買い物でのレジ待ちの行列です。先に並んだ人から先に会計してもらえますよね?キューではこういった感じに、先入先出方式でデータを管理します。

MEMO

後入れ先出しのことをLIFO(Last In, First Out)とも言います

スタックでは下記のPUSHとPOPの仕組みにより先入先出方式を実現しています。

PUSH

データをスタックに追加することをPUSHと呼びます。PUSHでは必ずスタックの一番上にデータを追加します。

POP

データをスタックから取り出すことをPOPと呼びます。POPではスタックの一番上のデータを取り出します。

スタックのC言語での実装

このページではスタックを配列を用いて実装したソースコードを紹介したいと思います。

配列による実装

配列によるスタック実装のイメージを図で表すと下のようになります。

ポイント

配列の要素0がスタックの一番下であり、配列の要素num-1(numはスタックに存在しているデータ数)がスタックの最後尾となります。要素num以降はデータを入れる箱としては存在していますが、何も入っていない空の状態になります。

そのため、PUSHは「一番上のnum-1よりも1つ上の要素num」にデータを格納することで実現することが可能です。スタックに入っているデータ数が1増えますので、PUSH時にはデータ数を表すnumも1増やす必要があります。

POPはスタックの一番上の要素num-1を取得する処理になります。スタックのデータ数が1減りますので、numも1減らす必要があります。

ソースコード

 C言語でスタックを配列により実装した時のソースコードは下のようになります。

stack_array.c
#include <stdio.h>
#include <stdlib.h>

/* スタックに入るデータの上限 */
#define MAX_STACK_NUM 10

/* スタック構造体 */
typedef struct STACK {
  /* スタックされているデータの数 */
  int num;
  /* スタックされているデータ */
  int data[MAX_STACK_NUM];
} STACK_T;

void initSack(STACK_T*);
void printSack(STACK_T*);
void push(STACK_T*, int);
int pop(STACK_T*);

/* スタックを初期化する関数 */
void initStack(STACK_T *stack){
  int i = 0;
  stack->num = 0;
  for(i = 0; i < MAX_STACK_NUM; i++){
    stack->data[i] = 0;
  }
}

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

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

  /* データをスタックの最後に追加 */
  stack->data[stack->num] = input;

  /* データの数もカウントアップ */
  stack->num++;
}

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

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

  /* 一番最後にPUSHした数(配列の最後尾)を取得 */
  ret = stack->data[stack->num-1];

  /* POPしたのでスタックのデータの数を1つ減らす */
  stack->num--;

  return ret;
}

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

  printf("左側がスタックの上側を表しています\n");
  for(i = 0; i < stack-&t;num; i++){
    printf("%d,", stack->data[stack->num-1-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する数は?(0以上の整数のみ可)");
      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;
}

キュー

続いてキューに移ります。キューとはデータ構造のひとつであり、待ち行列とも言います。英語では”queue”と書きます。

キューの特徴

特徴は、先に入力されたデータから先に出力するようにデータを管理することです。

イメージしやすいのは買い物でのレジ待ちの行列です。先に並んだ人から先に会計してもらえますよね?キューではこういった感じに、先入先出方式でデータを管理します。

MEMO

先入れ先出しのことをFIFO(First In, First Out)とも言います

キューでは下記のエンキューとデキューの仕組みにより先入先出方式を実現しています。

エンキュー

データをキューに追加することをエンキューと呼びます。エンキューでは必ずキューの最後尾にデータを追加します。

デキュー

データをキューから取り出すことをデキューと呼びます。デキューでは必ずキューの先頭のデータを取り出します。

C言語での実装

このキューの実装方法はたくさん存在すると思いますが、このページでは配列による実装とポインタによる実装のソースコードを紹介したいと思います。

配列による実装

配列によるキューの実装のイメージを図で表すと下のようになります。

ポイント

配列の要素0がキューの先頭であり、配列の要素num-1(numはキューに存在しているデータ数)がキューの最後尾となります。要素num以降はデータを入れる箱としては存在していますが、何も入っていない空の状態になります。

そのため、エンキューは「最後尾のnum-1よりも後ろの要素num」にデータを格納することで実現することが可能です。最後尾も後ろにずれる点に注意です。

デキューはちょっとだけややこしいです。データの取得先はキューの先頭である配列の要素0になります。ただし、取得するだけだと列が進みませんので、配列の要素0を取り出した後は配列の要素1以降のデータを先頭に向かってひとつずつ進めてやる必要があります。

ソースコード

 C言語でキューを配列により実装した時のソースコードは下のようになります。

queue_array.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* キューに入るデータの上限 */
#define MAX_QUEUE_NUM 10

/* キュー構造体 */
typedef struct QUEUE {
  /* エンキューされているデータの数 */
  int num;
  /* エンキューされているデータ */
  int data[MAX_QUEUE_NUM];
} QUEUE_T;

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

/* キューを初期化する関数 */
void initQueue(QUEUE_T *queue){
  int i = 0;
  queue->num = 0;
  for(i = 0; i < MAX_QUEUE_NUM; i++){
    queue->data[i] = 0;
  }
}

/* エンキューする関数 */
void enqueue(QUEUE_T *queue, int input){

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

  /* データをキューの最後に追加 */
  queue->data[queue->num] = input;

  /* データの数もカウントアップ */
  queue->num++;
}

/* デキューする関数 */
int dequeue(QUEUE_T *queue){
  int i = 0;
  int ret = 0;

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

  /* デキューした数を取得 */
  ret = queue->data[0];

  /* キューのデータを一つずつ先頭側に移動 */
  for(i = 0; i < queue->num-1; i++){
    queue->data[i] = queue->data[i+1];
  }

  /* キューの最後のデータは不要になるので0で初期化 */
  queue->data[queue->num-1] = 0;

  /* デキューしたのでキューのデータの数を1つ減らす */
  queue->num--;

  return ret;
}

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

  for(i = 0; i < queue->num; 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:エンキュー\n 2:デキュー\n 3:キュー表示\n それ以外:終了\n");
    scanf("%d", &m);

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

ポインタによる実装

続いてポインタによる実装について解説していきます。ポインタが苦手という方は是非下のページも合わせて読んでみてください。

ポインタ解説ページのアイキャッチ徹底図解!C言語ポインタを初心者向けに分かりやすく解説

ポインタによるキューの実装のイメージを図で表すと下のようになります。

ポイント

headポインタとtailポインタを用意し、それぞれがキューの先頭と最後尾を指すようにします。また、キューのデータそれぞれに、次のデータを指すnextポインタを持たせ、各データをリスト構造的につなぎ合わせることでキューを実現します。

エンキューは下記の3つの処理を行うことで実現します。

  1. 追加データをメモリ空間に確保
  2. tailポインタが指しているデータのnextポインタを追加データのアドレスにセット
  3. tailポインタを追加データのアドレスにセット

これにより、追加分のデータはキューの最後尾に追加されることになります。

デキューは下記の4つの処理を行うことで実現します。

  1. headポインタの指すデータを取得
  2. 取得したデータのnextポインタの指すアドレス退避
  3. headポインタの指す先のデータを削除
  4. headポインタを退避していたアドレスにセット

これにより取得したデータは削除され、先頭の次に追加されたデータが先頭に並ぶようになります。

ソースコード

C言語でキューをポインタにより実装した時のソースコードは下のようになります。

queue_pointer.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/* キューのデータ */
typedef struct DATA {
  int data;
  struct DATA *next;
} DATA_T;

/* キューの情報を構造体 */
typedef struct QUEUE {
  /* キューの先頭を指すポインタ */
  DATA_T *head;
  /* キューの最後尾を指すポインタ */
  DATA_T *tail;
} QUEUE_T;

void initQueue(QUEUE_T*);
void finishQueue(QUEUE_T*);
void printQueue(QUEUE_T*);
void enqueue(QUEUE_T*, int);
int deqeueue(QUEUE_T*);

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

  queue->head = NULL;
  queue->tail = NULL;
}

/* キューの終了処理をする関数 */
void finishQueue(QUEUE_T *queue){
  DATA_T *p, *next;
  p = queue->head;
  while(p != NULL){
    next = p->next;
    free(p);
    p = next;
  }
}

/* エンキューする関数 */
void enqueue(QUEUE_T *queue, int input){

  DATA_T *add;

  /* エンキューするデータを保持するメモリを確保 */
  add = (DATA_T*)malloc(sizeof(DATA_T));

  /* メモリが足りなければ何もせず関数終了 */
  if(add == NULL){
    printf("メモリが取得ないためエンキューできません\n");
    return ;
  }

  add->data = input;
  add->next = NULL;

  /* キューが空の場合は先頭に追加するのみ */
  if(queue->head == NULL){
    queue->head = add;
    queue->tail = add;
    return ;
  }

  /* キューの最後尾に追加したデータを追加 */
  /* キューの最後尾のデータのnextを追加データのアドレスにセット */
  queue->tail->next = add;

  /* キューの最後尾を指すtailを追加したデータのアドレスにセット */
  queue->tail = add;
}

/* デキューする関数 */
int dequeue(QUEUE_T *queue){
  int i = 0;
  int ret = 0;
  DATA_T *tmpNext;

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

  /* デキューする数(先頭データ)を取得 */
  ret = queue->head->data;

  /* デキューするデータのnextポインタの指すアドレスを退避 */
  tmpNext = queue->head->next;

  /* デキューしたデータ(先頭データ)を削除 */
  free(queue->head);

  /* 先頭を指すheadポインタを先頭の次のデータのアドレス(退避したアドレス)にセット */
  queue->head = tmpNext;

  return ret;
}

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

  p = queue->head;
  while(p != NULL){
    printf("%d,", p->data);
    p = p->next;
  }
  printf("\n");
}

int main(void){

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

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

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

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

  finishQueue(&queue);

  return 0;
}

スポンサーリンク

まとめ

このページでは、キューとスタックについて解説し、C言語で実装した時のソースコードと実装のポイントを説明しました。

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

他のデータ構造について

リスト構造の解説やC言語ソースコードも下記で解説しています。

リスト構造をC言語プログラムの実例を用いて解説

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です