vi. キューとスタック

データの保存と取り扱いの方法です。

キューもスタックも、データを一列に並べます。 また、データの追加と取り出し方法に特徴があります。

• キューは
  • データを追加するときには、列の末尾に追加される。
  • データを取り出すときには、列の先頭から取り出される。
  • 例として、5,10,1 が保存されているキューにに 6を追加し、そこからデータを2つ取り出した場合の、キューの様子を以下に示します。
    
  • 待ち行列とも呼ばれます。売店とかのレジの並びとかを思い浮かべると、理解しやすいです。
  • リング状になったキューをリングキューと言います。
    
    リング状になっているので、先頭と末尾が一致するときが来ます。
• スタックは
  • データを追加するときには、列の先頭に追加される。
  • データを取り出すときには、列の先頭から取り出される。
  • スタックにデータが保存されていることを「スタックにデータが積まれている」、 スタックにデータを追加することを「スタックにデータを積む」と言います。
  • 例として、5,10,1 が積まれているスタックに 6を積み、そこからデータを2つ取り出した場合の、スタックの様子を以下に示します。
    

キューを実現する簡易なプログラムを、以下に示します。

#include<stdio.h>

#define N 1000

struct queue{
        char data[N];
        int head;
        int tail;
};

void initialize(struct queue *q){
        int i;

        q->head=0;
        q->tail=0;
        for(i=0; i < N; ++i){
                q->data[i]=' ';
        }
}

void enqueue(struct queue *q, int item){
        if (q->tail >= N) {
                printf("This queue is full! \n");
        }else{
                q->data[q->tail]=item;
                q->tail++;
        }
}

int dequeue(struct queue *q){
        int tmp;

        if(q->head == q->tail){
                return -1;
        }else{
                tmp=q->data[q->head];
                q->head++;
                return tmp;
        }
}

int main() {
        char symbol;
        int i, item;
        struct queue Q;

        initialize(&Q);
        do{
                printf("input ! or @:\n");
                scanf(" %c",&symbol);
                if ( symbol == '!'){
                        item = dequeue(&Q);
                        printf("dequeue %d \n",item);
                }else if( symbol == '@'){
                        printf("input an integer:\n");
                        scanf("%d",&item);
                        enqueue(&Q, item);
                        printf("enqueue %d \n",item);
                }

                printf("\n--------------- Now queue data:\n");
                for (i=Q.head; i < Q.tail; i++){
                        printf("  data[%d]=%d\n", i, Q.data[i]);
                }
                printf("---------------\n\n");
        }while (symbol != EOF );
}

このプログラムは

• ! が入力されると、キューからデータを取り出し。
• @ が入力されると、次に入力された値をキューにデータを追加。
• 何かを行うたびに、キューのデータを画面に出力。

ということを行います。

どんなにデータを取り出そうとも、 累計で1000個までしかデータを蓄えることができないので、 あまり良いプログラムではありません。

構造体として

struct queue{
    int data[N];
    int head;
    int tail;
}; 

を定義しています。それぞれのメンバは、

• data[N]：キューに蓄えられたデータ
• head：キューの先頭が、配列のどこにあるか
• tail：キューの最後尾が、配列のどこにあるか

を保存します。概略図は、次のようになります。

また、関数として、initialize、enqueue、dequeue を使用しています。

• initialize

  void initialize(struct queue *q){
          int i;
  
          q->head=0;
          q->tail=0;
          for(i=0; i < N; ++i){
                  q->data[i]=' ';
          }
  };
  

• enqueue

  void enqueue(struct queue *q, int item){
          if (q->tail >= N) {
                  printf("This queue is full! \n");
          }else{
                  q->data[q->tail]=item;
                  q->tail++;
          }
  }
  

  関数 enqueue は、

  1. tail の示す場所にitemの値を書き込み
  2. tail の値を1つ増やす

  ことで、キューにデータを追加します。概略図は、次のようになります。

  

• dequeue

  int dequeue(struct queue *q){
          int tmp;
  
          if(q->head == q->tail){
                  return -1;
          }else{
                  tmp=q->data[q->head];
                  q->head++;
                  return tmp;
          }
  }
  

  関数 dequeue は、

  1. head の場所から値を、tmp に保存する。
  2. head の値を1つ増やす
  3. tmp の値を戻り値として返す

  ことで、キューからデータを取り出します。また、キューにデータがないときは、-1 を返します。概略図は、次のようになります。