アルゴリズムとデータ構造編【データ構造】 第11章 両端キュー

先頭へ戻る

この章の概要

この章の概要です。

両端キュー

両端キュー(両端待ち行列、双方向キュー、両頭キュー、head-tail linked list)は、先頭と末尾の両方で、要素の追加・削除が行えるデータ構造です。 double-ended queue と呼ばれることもあり、これを略して deque (デク) とも呼ばれます。

稀に、deque を dequeue と書くことがありますが、dequeue は「デキュー」であり、キューから要素を取り出す操作のような誤解を与えかねません。 そのため、多くの場合に deque と書きます。

このように、非常に呼び名が多いデータ構造ですが、意味していることは同じです。 ごく単純化して言えば、スタック(第5章)とキュー(第6章)の両方の面を持った構造と言えます。 つまり、先に入れた要素と、後に入れた要素とのどちらからでも取り出しが可能であるということです。

むしろ、両端キューの方が一般化された構造であり、スタックやキューは、それに制限を加えて特殊化したものであるとも考えられます。

両端キューを実装する方法は幾つか考えられますが、 本章では、3つの方法を取り上げます。
それぞれを説明する前に、まず実験用の main関数を作ってみます。

/* main.c */

#include <stdio.h>
#include "deque.h"


int main(void)
{
	Deque deque = deque_create();
	int i;

	for( i = 0; i < 10; ++i ){
		deque_push_back( deque, i );
	}

	while( !deque_is_empty(deque) ){
		printf( "%d\n", deque_pop_front(deque) );
	}

	
	for( i = 0; i < 10; ++i ){
		deque_push_front( deque, i );
	}

	while( !deque_is_empty(deque) ){
		printf( "%d\n", deque_pop_back(deque) );
	}
	
	deque_delete( deque );
	return 0;
}

両端キューの末尾へ 0 ~ 10 を順番に格納し、空になるまで先頭から取り出しては printf関数で要素の値を出力します。 その後、今度は 0 ~ 10 を先頭へ格納し、空になるまで末尾から取り出しては値を出力します。 次のような実行結果になれば想定通りです。

実行結果:

0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9

どの実装方法でも、このプログラムをそのまま使えるようにします。 そのため、deque.h についても共通化しておきます。

/* deque.h */

#ifndef DEQUE_H
#define DEQUE_H


/*
	両端キュー型
*/
typedef struct Deque_tag* Deque;


/*
	両端キューを作る

	戻り値:
		作成された両端キュー。
		使い終わったら、deque_delete関数に渡して削除する。
*/
Deque deque_create();

/*
	両端キューを削除する

	引数:
		deque:	両端キュー
*/
void deque_delete(Deque deque);

/*
	両端キューの先頭へ要素を追加する

	引数:
		deque:	両端キュー
		value:	追加する要素
*/
void deque_push_front(Deque deque, int value);

/*
	両端キューの末尾へ要素を追加する

	引数:
		deque:	両端キュー
		value:	追加する要素
*/
void deque_push_back(Deque deque, int value);

/*
	両端キューの先頭から要素を取り出す

	引数:
		deque:	両端キュー
	戻り値:
		取り出された要素
*/
int deque_pop_front(Deque deque);

/*
	両端キューの末尾から要素を取り出す

	引数:
		deque:	両端キュー
	戻り値:
		取り出された要素
*/
int deque_pop_back(Deque deque);

/*
	両端キューが空かどうか調べる

	引数:
		deque:	両端キュー
	戻り値:
		両端キューが空であれば 0以外を返し、空でなければ 0 を返す。
*/
int deque_is_empty(Deque deque);


#endif

この先で、3つの実装方法を取り上げますが、すべて main.c と deque.h は上記の実装のまま使います。

双方向循環リストによる実装

両端キューを実装するには、双方向循環リスト(第4章)を使うのが簡単です。
双方向循環リストの実装には、 コードライブラリにある ppps_int_clist を使ってみます。

/* deque.c */

#include "deque.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ppps_int_clist.h"


struct Deque_tag {
	PPPSIntClist  list;  /* 双方向循環リスト */
};

static void* xmalloc(size_t size);


/* 両端キューを作る */
Deque deque_create()
{
	struct Deque_tag* deque;

	deque = xmalloc( sizeof(struct Deque_tag) );
	deque->list = ppps_int_clist_create();

	return deque;
}

/* 両端キューを削除する */
void deque_delete(Deque deque)
{
	ppps_int_clist_delete( deque->list );
	free( deque );
}

/* 両端キューの先頭へ要素を追加する */
void deque_push_front(Deque deque, int value)
{
	int ret;

	ret = ppps_int_clist_add_front( deque->list, value );
	assert( ret != 0 );
}

/* 両端キューの末尾へ要素を追加する */
void deque_push_back(Deque deque, int value)
{
	int ret;

	ret = ppps_int_clist_add_tail( deque->list, value );
	assert( ret != 0 );
}

/* 両端キューの先頭から要素を取り出す */
int deque_pop_front(Deque deque)
{
	PPPSIntClist elem;
	int value;
	int ret;

	/* リストから先頭の要素を取得 */
	elem = ppps_int_clist_get_head( deque->list );
	assert( elem != NULL );

	/* 要素をリストから削除してしまうので、先に値をコピーしておく */
	value = elem->value;

	/* リストから先頭の要素を削除 */
	ret = ppps_int_clist_remove_elem( elem );
	assert( ret != 0 );

	return value;
}

/* 両端キューの末尾から要素を取り出す */
int deque_pop_back(Deque deque)
{
	PPPSIntClist elem;
	int value;
	int ret;

	/* リストから末尾の要素を取得 */
	elem = ppps_int_clist_get_tail( deque->list );
	assert( elem != NULL );

	/* 要素をリストから削除してしまうので、先に値をコピーしておく */
	value = elem->value;

	/* リストから末尾の要素を削除 */
	ret = ppps_int_clist_remove_elem( elem );
	assert( ret != 0 );

	return value;
}

/* 両端キューが空かどうか調べる */
int deque_is_empty(Deque deque)
{
	return ppps_int_clist_count( deque->list ) == 0;
}



/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
	void* p = malloc( size );
	if( p == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( EXIT_FAILURE );
	}
	return p;
}

リスト構造の先頭と末尾の要素を効率よくアクセスできれば、両端キューの効率も良くなります。 その意味で、先頭と末尾の要素へアクセスしやすい循環式のリスト構造を用いています。

この実装方法の問題点は、両端キューの途中の要素へのアクセスを効率的に実装できないことです。 両端キューというデータ構造としては、先頭と末尾以外へのアクセスは必須機能ではありませんが、できれば便利ではあります。 このような機能が必要であれば、この後の項で取り上げる動的配列による実装を検討して下さい。

動的配列による実装①

動的配列を使って実装する方法もあります。
配列を使って実装する両端キューは、Array Deque と呼ばれることもあります。 リスト構造を使う実装と違い、Array Deque の場合は、途中の要素への直接アクセスが効率的に実装できるという点が優れています。

Array Deque の実装には、よく知られた方法が2つあります。
1つは、動的配列の中央から前方と後方のそれぞれに向かって要素を追加していく形式で、 どちらか一方が端に達したら、より大きな動的配列を作り、そちらに要素を移動させます。
もう1つの方法は、この後の項で取り上げます

それでは、1つ目の方法を使って deque.c を実装してみます。

/* deque.c */

#include "deque.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>


struct Deque_tag {
	int* array;    /* 動的配列 */
	size_t size;   /* array の大きさ */
	size_t head;   /* 先頭要素のインデックス (要素数 0 のときは無効) */
	size_t tail;   /* 末尾要素のインデックス (要素数 0 のときは無効) */
	size_t count;  /* 要素数 */
};

static void* xmalloc(size_t size);


/* 両端キューを作る */
Deque deque_create()
{
	const size_t size = 4;
	struct Deque_tag* deque;

	deque = xmalloc( sizeof(struct Deque_tag) );
	deque->array = xmalloc( sizeof(int) * size );
	deque->size = size;
	deque->head = 0;
	deque->tail = 0;
	deque->count = 0;

	return deque;
}

/* 両端キューを削除する */
void deque_delete(Deque deque)
{
	free( deque->array );
	free( deque );
}

/* 両端キューの先頭へ要素を追加する */
void deque_push_front(Deque deque, int value)
{
	size_t index;

	if( deque_is_empty(deque) ){
		/* 1つ目の要素の場合は、配列の中央部分を使う */
		index = deque->size / 2;
	}
	else {
		if( deque->head <= 0 ){
			/* 領域が無い */

			int* new_array;
			const size_t new_size = deque->size * 2;
			const size_t add_size = new_size - deque->size;

			/* 新しい動的配列を確保 */
			new_array = xmalloc( sizeof(int) * new_size );

			/* 古い領域の内容をコピー。
			   ここでは、先頭付近に領域を作りたいので、コピー先は新しい配列の後半に置く
			*/
			memcpy( &new_array[add_size], deque->array, sizeof(int) * deque->size );

			/* 古い配列を解放し、ポインタを付け替える */
			free( deque->array );
			deque->array = new_array;

			/* 要素数やインデックスの調整 */
			deque->size = new_size;
			deque->head += add_size;
			deque->tail += add_size;
		}

		index = deque->head - 1;
	}

	deque->array[index] = value;
	deque->head = index;
	deque->count++;

	/* 要素数が1の場合、追加された要素の位置 == head == tail になる */
	if( deque->count == 1 ){
		deque->tail = deque->head;
	}
}

/* 両端キューの末尾へ要素を追加する */
void deque_push_back(Deque deque, int value)
{
	size_t index;

	if( deque_is_empty(deque) ){
		/* 1つ目の要素の場合は、配列の中央部分を使う */
		index = deque->size / 2;
	}
	else {
		if( deque->tail >= deque->size - 1 ){
			/* 領域が無い */

			int* new_array;
			const size_t new_size = deque->size * 2;
			const size_t add_size = new_size - deque->size;

			/* 新しい動的配列を確保 */
			new_array = xmalloc( sizeof(int) * new_size );

			/* 古い領域の内容をコピー。
			   ここでは、末尾付近に領域を作りたいので、コピー先は新しい配列の前半に置く
			*/
			memcpy( new_array, deque->array, sizeof(int) * deque->size );

			/* 古い配列を解放し、ポインタを付け替える */
			free( deque->array );
			deque->array = new_array;

			/* 要素数の調整 */
			deque->size = new_size;
		}

		index = deque->tail + 1;
	}

	deque->array[index] = value;
	deque->tail = index;
	deque->count++;

	/* 要素数が1の場合、追加された要素の位置 == head == tail になる */
	if( deque->count == 1 ){
		deque->head = deque->tail;
	}
}

/* 両端キューの先頭から要素を取り出す */
int deque_pop_front(Deque deque)
{
	assert(!deque_is_empty(deque));

	deque->count--;
	return deque->array[deque->head++];
}

/* 両端キューの末尾から要素を取り出す */
int deque_pop_back(Deque deque)
{
	assert(!deque_is_empty(deque));

	deque->count--;
	return deque->array[deque->tail--];
}

/* 両端キューが空かどうか調べる */
int deque_is_empty(Deque deque)
{
	return deque->count == 0;
}



/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
	void* p = malloc( size );
	if( p == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( EXIT_FAILURE );
	}
	return p;
}

動的配列を表すポインタ変数の他、先頭と末尾の要素がどの位置にあるかを覚える変数、 動的配列の大きさと、実際の要素数を管理する変数が必要になります。

基本的な考え方としては、最初に追加された要素は配列の中心部分に置き、 以降、先頭へ要素を追加する際には配列の前方(添字の小さい方)へ、末尾へ追加する際には配列の後方(添字の大きい方)へ追加していきます。
このとき、配列の先頭や末尾に空きが無いときには、倍の大きさを持つ配列を生成して、そちらへ要素を移し替えます。 前方への要素追加の際に、この移し替えが必要になった場合には、新しく生成した配列の後半部分へコピーしていることに注意して下さい。 こうして先頭付近に空きを作らないと、結局、要素を追加する場所ができません。

また、最初に追加された要素は、先頭要素であると同時に末尾要素でもあるので、 ここだけ特殊処理を行い、head と tail を同じ値にしています。 2つ目以降に追加される要素は、head か tail のいずれかをずらせば大丈夫です。

動的配列による実装②

動的配列を使った2つ目の実装方法は、リングバッファを用いるものです。 リングバッファは、第6章でキューの実装のために用いました。

リング状なので、先頭への追加は反時計周り、末尾への追加は時計回りというようにイメージすれば、 実現できることが分かると思います。
リングバッファの一方の端に要素を追加するとき、他方の端に行き着いてしまう場合に、 新たなリングバッファを生成して、そちらに要素を移動させます。

この方法で実装した deque.c は次のようになります。

/* deque.c */

#include "deque.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>


struct Deque_tag {
	int* array;    /* 動的配列 (リングバッファ) */
	size_t size;   /* data の要素数 */
	size_t head;   /* 先頭の要素の位置 */
	size_t tail;   /* 末尾の要素の位置 */
	size_t count;  /* 要素数 */
};

static void realloc_array(Deque deque);
static size_t get_prev_index(Deque deque, size_t index);
static size_t get_next_index(Deque deque, size_t index);
static void* xmalloc(size_t size);


/* 両端キューを作る */
Deque deque_create()
{
	const size_t size = 4;
	struct Deque_tag* deque;

	deque = xmalloc( sizeof(struct Deque_tag) );
	deque->array = xmalloc( sizeof(int) * size );
	deque->size = size;
	deque->head = 0;
	deque->tail = 0;
	deque->count = 0;

	return deque;
}

/* 両端キューを削除する */
void deque_delete(Deque deque)
{
	free( deque->array );
	free( deque );
}

/* 両端キューの先頭へ要素を追加する */
void deque_push_front(Deque deque, int value)
{
	if( deque->count == deque->size ){
		/* 領域が無い */
		realloc_array( deque );
	}

	deque->head = get_prev_index(deque, deque->head);
	deque->array[deque->head] = value;
	deque->count++;

	/* 要素数が1の場合、追加された要素の位置 == head == tail になる */
	if( deque->count == 1 ){
		deque->tail = deque->head;
	}
}

/* 両端キューの末尾へ要素を追加する */
void deque_push_back(Deque deque, int value)
{
	if( deque->count == deque->size ){
		/* 領域が無い */
		realloc_array( deque );
	}

	deque->tail = get_next_index(deque, deque->tail);
	deque->array[deque->tail] = value;
	deque->count++;

	/* 要素数が1の場合、追加された要素の位置 == head == tail になる */
	if( deque->count == 1 ){
		deque->head = deque->tail;
	}
}

/* 両端キューの先頭から要素を取り出す */
int deque_pop_front(Deque deque)
{
	int value;

	assert(!deque_is_empty(deque));

	value = deque->array[deque->head];
	deque->head = get_next_index(deque, deque->head);
	deque->count--;

	return value;
}

/* 両端キューの末尾から要素を取り出す */
int deque_pop_back(Deque deque)
{
	int value;

	assert(!deque_is_empty(deque));

	value = deque->array[deque->tail];
	deque->tail = get_prev_index(deque, deque->tail);
	deque->count--;

	return value;
}

/* 両端キューが空かどうか調べる */
int deque_is_empty(Deque deque)
{
	return deque->count == 0;
}



/* 配列を再確保 */
void realloc_array(Deque deque)
{
	int* new_array;
	const size_t new_size = deque->size * 2;

	/* 新しい動的配列を確保 */
	new_array = xmalloc( sizeof(int) * new_size );

	/* 古い領域の内容をコピー */
	if( deque->head <= deque->tail ){
		memcpy( new_array, &deque->array[deque->head], sizeof(int) * deque->count );
	}
	else{
		/* head の方が tail より大きい場合、配列の先頭と末尾がつながった状態 */
		int n = deque->size - deque->head;
		memcpy( new_array, &deque->array[deque->head], sizeof(int) * n );
		memcpy( &new_array[n], deque->array, sizeof(int) * (deque->count - n) );
	}

	/* 古い配列を解放し、ポインタを付け替える */
	free( deque->array );
	deque->array = new_array;

	/* 要素数やインデックスの調整 */
	deque->size = new_size;
	deque->head = 0;
	deque->tail = deque->count - 1;
}

/* 1つ手前の添字を取得する */
size_t get_prev_index(Deque deque, size_t index)
{
	return (index == 0) ? deque->size - 1 : index - 1;
}

/* 1つ後ろの添字を取得する */
size_t get_next_index(Deque deque, size_t index)
{
	return (index + 1) % deque->size;
}

/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
	void* p = malloc( size );
	if( p == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( EXIT_FAILURE );
	}
	return p;
}

リングバッファ版の場合、head や tail で表される位置情報を進めたり戻したりする際に、 単に -1 や +1 してはならないことに注意して下さい。 要素数が有限の配列を使ってリングを表現しているので、先頭と末尾はつながっています。 そのため、末尾の次は先頭ですし、先頭の手前は末尾です。

このように添字計算の部分で、常に余分な計算が加わってしまう点は、性能的にはやや不利になります。

添字計算の関数は、マクロ(C言語編第28章)やインライン関数(C言語編第28章)に置き換えることで、性能を向上させることができます。

領域が足りなくなったときには、新しいリングバッファを確保して、要素をコピーします。 このとき、元の配列の先頭と末尾がつながっている可能性を考慮しなければならないことに注意が必要です。
例えば、元の配列の要素数が 4、head が 3、tail が 1 だとすると、インデックス[3][0][1] が使われている訳ですが、 拡張後の配列 (要素数 8) で、インデックス[3][0][1] に要素を入れてしまうと [3] と [0] はつながっていないので (間に [4]~[7] があるので)、 要素が分断されてしまいます。
このサンプルプログラムの場合は、拡張後の配列は、必ずインデックス[0] を head にして、 そこから連続して要素を入れていくように実装しています。

まとめ

両端キューを実装する方法を3通り取り上げました。 大きく分けると、連結リストを使う方法と、動的配列を使う方法があります。

途中の要素への直接アクセスの機能が必要であれば、性能の問題から、連結リストでの実装という手段は取れません。 しかしながら、要素の追加も削除も O(1) で行えるので、全体的に性能は高いと言えます。
一方、動的配列で実装すると、容量が有限になるので、 要素の追加時に、領域の再確保&コピーという大きなコストが掛かる可能性があります。


練習問題

問題① 動的配列によって実装された両端キューに、インデックスによる直接アクセスを行う機能を追加して下さい。


解答ページはこちら


参考リンク

更新履歴

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2015/1/17 新規作成。





前の章へ(第10章 優先度付きキュー)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS