RSS
この章の概要です。
この章では、キュー（待ち行列）というデータ構造を説明します。
キューは、前章で解説したスタックと同様、データの出し入れのルールに特徴があります。キューは、一番最初に格納したデータしか取り出せません。このような特徴を、先入れ先出しだとか、FIFO (First In First Out)と呼びます。
先入れ先出しのたとえ話として、店などの前にできる行列があります。先に行列に加わった人から用を済ますことができ、後から来た人は行列の最後尾に並ばされるということです。このとき、１人１人がキューに格納されるデータです。
キューへデータを格納することをエンキュー(enqueue)といい、データを取り出すことをデキュー(dequeue)といいます。
前章のスタックと同様、キューも抽象データ型として取り扱うことができます。抽象データ型に関する解説は繰り返しませんので、必要であれば前章を参照してください。
キューにとって最低限必要な機能を以下のように定義できます。
これらの機能を持ってさえいれば、キュー自身がどのようにデータを管理していても構わないといえます。
実際には、enqueue と dequeue に加えて、補助的な機能が必要かもしれません。よく必要になるのは、
です。
キューが空のときに dequeue を呼び出したらどうなるのか、という問題があります。int型のデータを管理しているキューが空だったとき、dequeue は何を返せばいいのでしょうか？ どうしても、エラーの類として扱わざるを得ないため、dequeue を呼び出す前に、呼び出し側で確認できる機能が欲しいのです。
また、キューに積まれているデータを、キューが空になるまで dequeue したいという場面もあるでしょう。そういうときにも、is_empty の機能が欲しくなります。
ここまでの説明から、スタックとよく似ているので簡単だと思うかもしれませんが、実装してみると意外とスタックと同じようにはいかないことが分かります。１度実際に取り組まれることをおすすめします。
本章では、キューの配列を使った実装と連結リストを使った実装を取り上げます。
まずは配列を使った実装を確認します。
スタックが後入れ先出しで、キューが先入れ先出しですが、データが取り出されるときの法則が異なるだけでなので、pop の関数を dequeue の操作になるように書き換えるだけで済みそうに思えるかもしれません。しかし、配列による実装は、意外にも簡単にはいきません。
動作をイメージしてみましょう。要素数４の配列を使うとします。
[0] [1] [2] [3] <-- 添字
<-- データ（何かあれば *）１回目の enqueue をするとこうなります。
[0] [1] [2] [3] <-- 添字
* <-- データ（何かあれば *）続けて enqueue します。
[0] [1] [2] [3] <-- 添字
* * <-- データ（何かあれば *）このような状態になることに異論はないと思いますが、実際にはどうやって格納位置を決めるのかという問題があります。先入れ先出しのルールを実現するには、後から enqueue されたデータは、配列の後ろに追加されれば良いでしょう。配列の先頭に近いほど、先に enqueue されたデータ、末尾に近いほど、あとから euqueue されたデータであるということです。
これを実現するためには、次にデータを入れる場所を管理しておくといいでしょう。tail という名前で指している箇所が、次にデータを入れる場所です。
tail
v
[0] [1] [2] [3] <-- 添字
* * <-- データ（何かあれば *）enqueue すると、tail のところにデータが入り、tail がずれます。
tail
v
[0] [1] [2] [3] <-- 添字
* * * <-- データ（何かあれば *）さて、今度は dequeue を行います。先入れ先出しなのですから、最初に enqueue されたデータが格納されている array[0] を取り除くことになります。
tail
v
[0] [1] [2] [3] <-- 添字
* * <-- データ（何かあれば *）ここで１つ問題がみえてきます。データが取り除かれた結果、array[0] は未使用な状態になります。つまり、「先頭」は array[0] ではなく array[1] になったのです。このように、先頭の位置は dequeue によって変化しますから、tail と同様に、先頭の位置も管理しておかなければなりません。front を導入します。
front tail
v v
[0] [1] [2] [3] <-- 添字
* * <-- データ（何かあれば *）dequeue されたとき、後続のデータを手前にずらすという方法も考えられるわけですが、配列でこのような処理は遅いのでした（第１章）。そのため、キューをこの方法で実装することはありません。
続けて dequeue します。front は array[1] を指しているので、ここから取り除きます。そして、front がずれます。
front tail
v v
[0] [1] [2] [3] <-- 添字
* <-- データ（何かあれば *）さて、今度は enqueue します。tail の位置に格納するのでした。格納すること自体は簡単ですが、新しい tail をどうするのかが問題です。tail はすでに配列の末尾にいるので、これ以上後ろにはいけません。
front tail（これはできない）
v v
[0] [1] [2] [3] <-- 添字
* * <-- データ（何かあれば *）かといって、これ以上 enqueue できないという割り切りは不適切です。配列の要素数は 4 なのに、現在データは 2個しか入っていません。ここで諦めてしまったら、front がずれるたびに、格納できるデータの個数は減ってしまうのです。
この問題を解決するには、配列の末尾まで使いきってしまったら、先頭に戻ってこさせるような仕組みを導入します。つまり、tail を配列の先頭に戻します。
tail front
v v
[0] [1] [2] [3] <-- 添字
* * <-- データ（何かあれば *）これは、front の方も同様で、配列の末尾に達してしまったら、先頭に戻せばいいです。
実際にデータが入っている位置は、front と tail があればきちんと分かりますから、このような実装ができます。この構造は、データを格納する領域（バッファ）が、輪のように周回しているような状態であることから、リングバッファと呼ばれます。配列版キューを実装するには、配列をリングバッファのように利用することがポイントです。
では、前章と同様に、実験ができる形でプログラムを作っていきます。
// main.c
#include <stdio.h>
#include <string.h>
#include "queue.h"
// コマンド
enum Cmd_tag {
CMD_ENQUEUE,
CMD_DEQUEUE,
CMD_EXIT,
CMD_NUM
};
// コマンド文字列の種類
enum CmdStr_tag {
CMD_STR_SHORT,
CMD_STR_LONG,
CMD_STR_NUM
};
// コマンドの戻り値
enum CmdRetValue_tag {
CMD_RET_VALUE_CONTINUE,
CMD_RET_VALUE_EXIT,
};
// コマンド文字列
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
{ "n", "enqueue" },
{ "d", "dequeue" },
{ "e", "exit" }
};
static void create_queue(void);
static void delete_queue(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_enqueue(void);
static enum CmdRetValue_tag cmd_dequeue(void);
static enum CmdRetValue_tag cmd_exit(void);
static void enqueue_elem(int value);
static int dequeue_elem(void);
static void get_line(char* buf, size_t size);
// コマンド実行関数
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
cmd_enqueue,
cmd_dequeue,
cmd_exit
};
static Queue gQueue;
int main(void)
{
create_queue();
while( 1 ){
print_explain();
if( get_cmd() == CMD_RET_VALUE_EXIT ){
break;
}
print_blank_lines();
}
delete_queue();
return 0;
}
/*
キューを作成
*/
void create_queue(void)
{
gQueue = queue_create( 128 );
}
/*
キューを削除
*/
void delete_queue(void)
{
queue_delete( gQueue );
gQueue = NULL;
}
/*
説明文を出力
*/
void print_explain(void)
{
puts( "コマンドを入力してください。" );
printf( " キューに要素を入れる: %s (%s)\n", CMD_STR[CMD_ENQUEUE][CMD_STR_SHORT], CMD_STR[CMD_ENQUEUE][CMD_STR_LONG] );
printf( " キューから要素を取り出す: %s (%s)\n", CMD_STR[CMD_DEQUEUE][CMD_STR_SHORT], CMD_STR[CMD_DEQUEUE][CMD_STR_LONG] );
printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
puts( "" );
}
/*
空白行を出力
*/
void print_blank_lines(void)
{
puts( "" );
puts( "" );
}
/*
コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
char buf[20];
get_line( buf, sizeof(buf) );
enum Cmd_tag cmd = CMD_NUM;
for( int i = 0; i < CMD_NUM; ++i ){
if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
|| strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
){
cmd = i;
break;
}
}
if( 0 <= cmd && cmd < CMD_NUM ){
return CMD_FUNC[cmd]();
}
else{
puts( "そのコマンドは存在しません。" );
}
return CMD_RET_VALUE_CONTINUE;
}
/*
enqueueコマンドの実行
*/
enum CmdRetValue_tag cmd_enqueue(void)
{
char buf[40];
int value;
puts( "キューに入れる数値データを入力してください。" );
fgets( buf, sizeof(buf), stdin );
sscanf( buf, "%d", &value );
enqueue_elem( value );
return CMD_RET_VALUE_CONTINUE;
}
/*
dequeueコマンドの実行
*/
enum CmdRetValue_tag cmd_dequeue(void)
{
if( queue_is_empty( gQueue ) ){
puts( "キューは空です。" );
}
else{
printf( "%d を降ろしました。\n", dequeue_elem() );
}
return CMD_RET_VALUE_CONTINUE;
}
/*
exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
puts( "終了します。" );
return CMD_RET_VALUE_EXIT;
}
/*
要素を入れる
引数：
value: 入れる要素の数値データ。
*/
void enqueue_elem(int value)
{
queue_enqueue( gQueue, value );
}
/*
要素を取り出す
戻り値：
取り出された要素。
*/
int dequeue_elem(void)
{
return queue_dequeue( gQueue );
}
/*
標準入力から１行分受け取る
受け取った文字列の末尾には '\0' が付加される。
そのため、実際に受け取れる最大文字数は size - 1 文字。
引数：
buf: 受け取りバッファ
size: buf の要素数
戻り値：
buf が返される
*/
void get_line(char* buf, size_t size)
{
fgets(buf, size, stdin);
// 末尾に改行文字があれば削除する
char* p = strchr(buf, '\n');
if (p != NULL) {
*p = '\0';
}
}// queue.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue.h"
static size_t get_next_index(Queue queue, size_t index);
static void* xmalloc(size_t size);
struct Queue_tag {
int* data; // 要素を格納する動的配列
size_t size; // data の要素数
size_t front; // 先頭の要素の位置
size_t tail; // 末尾の要素の位置
};
/*
キューを作る
*/
Queue queue_create(size_t size)
{
// front == tail を空の状態にしようとすると、配列全体を使い切った状態を作れない。
// そこで、指定された size を +1 して、１つ余分に領域を確保しておく。
size += 1;
struct Queue_tag* queue = xmalloc( sizeof(struct Queue_tag) );
queue->data = xmalloc( sizeof(int) * size );
queue->size = size;
queue->front = 0;
queue->tail = 0;
return queue;
}
/*
キューを削除する
*/
void queue_delete(Queue queue)
{
free( queue->data );
free( queue );
}
/*
キューに要素を入れる
*/
void queue_enqueue(Queue queue, int value)
{
assert( get_next_index(queue, queue->tail) != queue->front );
queue->data[queue->tail] = value;
// 次に要素を入れるときに使う位置を求める
// リングバッファ構造なので、単純に +1 するだけではダメ
queue->tail = get_next_index( queue, queue->tail );
}
/*
キューから要素を取り出す
*/
int queue_dequeue(Queue queue)
{
assert( !queue_is_empty(queue) );
int pop_value = queue->data[queue->front];
// 先頭から要素が１つ取り出されるので、先頭位置を更新する
// リングバッファ構造なので、単純に +1 するだけではダメ
queue->front = get_next_index( queue, queue->front );
return pop_value;
}
/*
キューが空かどうか調べる
*/
bool queue_is_empty(Queue queue)
{
return queue->front == queue->tail;
}
/*
１つ後ろの添字を取得する
*/
size_t get_next_index(Queue queue, size_t index)
{
return (index + 1) % queue->size;
}
/*
エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
void* p = malloc( size );
if( p == NULL ){
fputs( "メモリ割り当てに失敗しました。", stderr );
exit( EXIT_FAILURE );
}
return p;
}// queue.h
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
typedef struct Queue_tag* Queue;
/*
キューを作る
引数：
size: 格納できる要素数
戻り値：
作成されたキュー。
使い終わったら、queue_delete関数に渡して削除する。
*/
Queue queue_create(size_t size);
/*
キューを削除する
引数：
queue: キュー
*/
void queue_delete(Queue queue);
/*
キューに要素を入れる
引数：
queue: キュー
value: 入れる要素
*/
void queue_enqueue(Queue queue, int value);
/*
キューから要素を取り出す
引数：
queue: キュー
戻り値：
取り出された要素
*/
int queue_dequeue(Queue queue);
/*
キューが空かどうか調べる
引数：
queue: キュー
戻り値：
キューが空であれば true を返し、空でなければ false を返す。
*/
bool queue_is_empty(Queue queue);
#endifプログラムの作りは、前章のスタックのサンプルと同じになっています。
まず、構造体Queue_tag の実装ですが、最上段の位置だけ管理していればよかったスタックと違い、キューでは（というより、リングバッファでは）先頭と末尾の両方を管理する必要があります。先頭(front) が取り出される側、末尾(tail) が入れる側です。
front と tail は、配列内の要素を指すポインタでもいいですが、ここでは添字を使っています。リングバッファを作ることを考えると、添字のほうが楽です。
front と tail はいずれも、queue_create関数で新規のキューを作成した段階では、0 になっています。このように、front と tail の値が一致している状態を、キューが空の状態となるように実装しています。
キューが空であるかどうかを、front や tail が 0 であるかどうかでは判定できないことに注意してください。たとえば、最初の状態から、enqueue を 1回すると「front == 0, tail == 1」になり、その後 dequeue すると「front == 1, tail == 1」になりますが、この状態も空なのです。実際の値とは関係なく「front == tail」かどうかだけが判断の基準になります。
なお、このように実装すると、配列全体を使い切れなくなります。なぜなら、配列が満杯になったとき、front と tail の値が同じになるからです。これでは、キューが空の状態と区別できません。そこで、queue_create関数では、仮引数size の値をこっそり +1 して使っています。
enqueue するときには、まずキューが満杯になっていないかどうかを確認します。ここで、満杯かどうかをどう判断すればいいかが問題です。前述のとおり、front == tail の状態のときは空であるというルールなので、満杯の状態というのは、tail + 1 == front のときです。
実際にはリングバッファになっているので、front や tail の値は増え続けた後、0 に戻ってきます。したがって、満杯の状態というのは、「(tail + 1) % max_size == front」のときです。（max_size は、キューの最大数のこと）。
このように、リングバッファでは、“末尾の次は先頭” なので、その辺りを踏まえて添字を計算しなければならない機会が多くあります。サンプルでは、get_next_index関数を作り、これを何箇所かで使用しています。
dequeue の方も、基本的な考え方は同じです。
まずは、キューがすでに空になっていないかを確認します。この判定は、繰り返し述べているとおり、「front == tail」かどうかです。これは、外部へ公開するインターフェースの一部として、queue_is_empty関数に実装されているので、そのまま使えます。
要素を取り出した後、front の位置をずらしますが、ここでもリングバッファであることを踏まえて、get_next_index関数を使って添字計算を行っています。
配列版の実装の利点と欠点は、スタックのときと同様です。この章のまとめのところであらためて書くので、ここでは省略させていただきます。
連結リストによる実装は、配列版よりも簡単です。ただし、スタックのときと違って、連結リストの先頭と末尾を指すポインタを両方持つ必要があります。
配列版との違いは、queue.c だけなので、queue.c だけ掲載します。
// queue.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue.h"
static void* xmalloc(size_t size);
struct QueueList_tag {
struct QueueList_tag* next; // 次の要素へのポインタ
int value; // 要素の値
};
struct Queue_tag {
struct QueueList_tag* front; // 先頭の要素へのポインタ
struct QueueList_tag* tail; // 末尾の要素へのポインタ
};
/*
キューを作る
*/
Queue queue_create(size_t size)
{
struct Queue_tag* queue = xmalloc( sizeof(struct Queue_tag) );
queue->front = NULL;
queue->tail = NULL;
return queue;
}
/*
キューを削除する
*/
void queue_delete(Queue queue)
{
struct QueueList_tag* p = queue->front;
struct QueueList_tag* tmp;
// 連結リストの要素を削除
while( p != NULL ){
tmp = p->next;
free( p );
p = tmp;
}
free( queue );
}
/*
キューに要素を入れる
*/
void queue_enqueue(Queue queue, int value)
{
struct QueueList_tag* p = xmalloc( sizeof(struct QueueList_tag) );
p->value = value;
p->next = NULL;
// 新たな要素を末尾に置く
if( queue->tail != NULL ){
queue->tail->next = p;
}
queue->tail = p;
if( queue->front == NULL ){
queue->front = p;
}
}
/*
キューから要素を取り出す
*/
int queue_dequeue(Queue queue)
{
assert( !queue_is_empty(queue) );
struct QueueList_tag* p = queue->front;
int pop_value = p->value;
queue->front = p->next;
// 取り出された要素が末尾の要素でもあったとき（キューの中に要素が１つしか無かったとき）
// には、tailポインタの付け替えも必要
if( p == queue->tail ){
queue->tail = NULL;
}
free( p );
return pop_value;
}
/*
キューが空かどうか調べる
*/
bool queue_is_empty(Queue queue)
{
return queue->front == NULL;
}
/*
エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
void* p = malloc( size );
if( p == NULL ){
fputs( "メモリ割り当てに失敗しました。", stderr );
exit( EXIT_FAILURE );
}
return p;
}構造体Queue_tag が持つ front と tail が、それぞれ連結リストの先頭の要素と、末尾の要素とを管理しています。enqueue のときには tail側に追加し、dequeue のときには front側から取り出すように実装します。
配列版の tail は、次にデータを格納する位置、つまり実際にはまだデータがない場所指すことができましたが、連結リスト版では、まだ存在していない要素を指すことができません。
このことは、キューが空かどうかを判定する方法にも影響があります。配列版のときのように、front == tail で判定すると、要素が１つだけ格納されているときに空と判定されてしまいます。連結リスト版での空の判定は、front が NULL かどうかです。
連結リスト版の enqueue は、キューが満杯かどうかを確認する必要はありません。連結リストなら、メモリが許す限りは、新しい要素を作り続けられるからです。
この特性のおかげで、末尾から先頭に戻ってこさせるような実装にする必要もありません。配列版のリングバッファのイメージが強いと、循環リストにしなければならないような錯覚に陥るかもしれませんが、その必要はありません。
少し面倒なのは、要素は tail側に追加されるものの、最初の１個に関しては front も変更する必要がある点です。これをしないと、キューが空かどうかの条件式 front == NULL が、いつまでも真のままになってしまいます。
dequeue するときには、キューが空かどうかを調べます。これは前述のように、front が NULL かどうかで調べられます。この部分は queue_is_empty関数に関数化されていますから、これを呼び出すだけです。
dequeue に関しても少し面倒な作業があります。取り出される要素が、末尾の要素だった場合（これはキューの中身が１個しかないときにだけ起こります）、tail も変更しないといけません。これをしないと、tail が不正な場所を指し続けてしまいます。
連結リスト版の実装の利点と欠点は、スタックのときと同様です。この章のまとめのところであらためて書くので、ここでは省略させていただきます。
配列版と連結リスト版の長所と短所をまとめておきます。結局のところ、スタックと同じです。
問題① queue.c/h に、次の機能を追加してください。
問題② ２つのキューを作り、一方のキューに適当なデータを積みます。その後、空になるまで
dequeue を繰り返し、そのつど、他方のキューへ dequeue された要素を
enqueue
していくことを繰り返すプログラムを作成してください。この作業を終えた後、キューの中身はどうなっていますか？
（前章の練習問題でスタックで同じことをしました。キューならどのような結果になるでしょう？）
問題③ queue.c を改造して、キューの中に同じ値を持った要素が重複しないようにしてください。
要素数を意味している「サイズ」について、「要素数」に表記を改めた。
サンプルプログラムの改善（fgets が受け取った改行文字の削除の方法を修正。const、static の付加）
サンプルプログラムで、存在しないコマンドが入力されたときに、未初期化の変数を参照していたのを修正。
サンプルプログラムで、ファイルスコープでよい関数に static を付加。
サンプルプログラムで、コマンド処理の方法を整理。
新規作成。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |