RSS
この章の概要です。
両端キュー（両端待ち行列、双方向キュー、両頭キュー、head-tail linked list）は、要素の追加・削除を、キューの先頭と末尾の両方で行えるデータ構造です。double-ended queue と呼ばれることもあり、これを略して deque (デク) とも呼ばれます。
まれに、deque を dequeue と書くことがありますが、dequeue は「デキュー」であり、キューから要素を取り出す操作のような誤解を与えかねません。そのため、多くの場合に deque と書きます。
このように、非常に呼び名が多いデータ構造ですが、意味していることは同じです。ごく単純化して言えば、スタック（第５章）とキュー（第６章）の両方の面を持った構造と言えます。つまり、先に入れた要素と、後に入れた要素とのどちらからでも取り出しが可能であるということです。
むしろ、両端キューの方が一般化された構造であり、スタックやキューは、それに制限を加えて特殊化したものであるとも考えられます。
両端キューを実装する方法はいくつか考えられますが、本章では、３つの方法を取り上げます。それぞれを説明する前に、まず実験用の main関数を作ってみます。
// main.c
#include <stdio.h>
#include "deque.h"
int main(void)
{
Deque deque = deque_create();
for( int i = 0; i < 10; ++i ){
deque_push_back( deque, i );
}
while( !deque_is_empty(deque) ){
printf( "%d\n", deque_pop_front(deque) );
}
for( int 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_INCLUDED
#define DEQUE_H_INCLUDED
#include <stdbool.h>
/*
両端キュー型
*/
typedef struct Deque_tag* Deque;
/*
両端キューを作る
戻り値：
作成された両端キュー。
使い終わったら、deque_delete関数に渡して削除する。
*/
Deque deque_create(void);
/*
両端キューを削除する
引数：
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: 両端キュー
戻り値：
両端キューが空であれば true を返し、空でなければ false を返す。
*/
bool deque_is_empty(Deque deque);
#endifこの先で、３つの実装方法を取り上げますが、main.c と deque.h は上記の実装のまま使います。
両端キューを実装するには、双方向循環リスト（第４章）を使うのが簡単です。
双方向循環リストの実装には、コードライブラリにある 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(void)
{
struct Deque_tag* 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)
{
bool ret = ppps_int_clist_add_front( deque->list, value );
assert( ret );
}
/*
両端キューの末尾へ要素を追加する
*/
void deque_push_back(Deque deque, int value)
{
bool ret = ppps_int_clist_add_tail( deque->list, value );
assert( ret );
}
/*
両端キューの先頭から要素を取り出す
*/
int deque_pop_front(Deque deque)
{
// リストから先頭の要素を取得
PPPSIntClist elem = ppps_int_clist_get_head( deque->list );
assert( elem != NULL );
// 要素をリストから削除してしまうので、先に値をコピーしておく
int value = elem->value;
// リストから先頭の要素を削除
bool ret = ppps_int_clist_remove_elem( elem );
assert( ret );
return value;
}
/*
両端キューの末尾から要素を取り出す
*/
int deque_pop_back(Deque deque)
{
// リストから末尾の要素を取得
PPPSIntClist elem = ppps_int_clist_get_tail( deque->list );
assert( elem != NULL );
// 要素をリストから削除してしまうので、先に値をコピーしておく
int value = elem->value;
// リストから末尾の要素を削除
bool ret = ppps_int_clist_remove_elem( elem );
assert( ret );
return value;
}
/*
両端キューが空かどうか調べる
*/
bool 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 の実装には、よく知られた方法が２つあります。
１つは、動的配列の中央から前方と後方のそれぞれに向かって要素を追加していく形式で、どちらか一方が端に達したら、より大きな動的配列を作り、そちらに要素を移動させます。
もう１つの方法は、この後の項で取り上げます。
それでは、１つ目の方法を使って 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(void)
{
const size_t size = 4;
struct Deque_tag* 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) ){
// １つ目の要素の場合は、配列の中央部分を使う
index = deque->size / 2;
}
else {
if( deque->head <= 0 ){
// 領域がない
const size_t new_size = deque->size * 2;
const size_t add_size = new_size - deque->size;
// 新しい動的配列を確保
int* 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++;
// 要素数が１の場合、追加された要素の位置 == 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) ){
// １つ目の要素の場合は、配列の中央部分を使う
index = deque->size / 2;
}
else {
if( deque->tail >= deque->size - 1 ){
// 領域がない
const size_t new_size = deque->size * 2;
const size_t add_size = new_size - deque->size;
// 新しい動的配列を確保
int* 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++;
// 要素数が１の場合、追加された要素の位置 == 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--];
}
/*
両端キューが空かどうか調べる
*/
bool 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 を同じ値にしています。２つ目以降に追加される要素は、head か tail のいずれかをずらせば大丈夫です。
動的配列を使った２つ目の実装方法は、リングバッファを用いるものです。リングバッファは、第６章でキューの実装のために用いました。
リング状なので、先頭への追加は反時計周り、末尾への追加は時計回りというようにイメージすれば、実現できることが分かると思います。リングバッファの一方の端に要素を追加するとき、他方の端に行き着いてしまう場合に、新たなリングバッファを生成して、そちらに要素を移動させます。
この方法で実装した 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; // 先頭の要素の位置
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(void)
{
const size_t size = 4;
struct Deque_tag* 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++;
// 要素数が１の場合、追加された要素の位置 == 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++;
// 要素数が１の場合、追加された要素の位置 == head == tail になる
if( deque->count == 1 ){
deque->head = deque->tail;
}
}
/*
両端キューの先頭から要素を取り出す
*/
int deque_pop_front(Deque deque)
{
assert(!deque_is_empty(deque));
int value = deque->array[deque->head];
deque->head = get_next_index(deque, deque->head);
deque->count--;
return value;
}
/*
両端キューの末尾から要素を取り出す
*/
int deque_pop_back(Deque deque)
{
assert(!deque_is_empty(deque));
int value = deque->array[deque->tail];
deque->tail = get_prev_index(deque, deque->tail);
deque->count--;
return value;
}
/*
両端キューが空かどうか調べる
*/
bool deque_is_empty(Deque deque)
{
return deque->count == 0;
}
/*
配列を再確保
*/
void realloc_array(Deque deque)
{
const size_t new_size = deque->size * 2;
// 新しい動的配列を確保
int* 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 より大きい場合、配列の先頭と末尾がつながった状態
size_t 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;
}
/*
１つ手前の添字を取得する
*/
size_t get_prev_index(Deque deque, size_t index)
{
return (index == 0) ? deque->size - 1 : index - 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 してはならないことに注意してください。要素数が有限の配列を使ってリングを表現しているので、先頭と末尾はつながっています。そのため、末尾の次は先頭ですし、先頭の手前は末尾です。
このように、添字計算の部分でつねに余分な計算が加わってしまうので、実行効率としてはやや不利になります。
添字計算の関数は、関数形式マクロ（Ｃ言語編第２８章）やインライン関数（Ｃ言語編第５７章）に置き換えることで、実行効率を向上できます。
領域が足りなくなったときには、新しいリングバッファを確保して、要素をコピーします。このとき、元の配列の先頭と末尾がつながっている可能性を考慮しなければならないことに注意が必要です。
たとえば、元の配列の要素数が 4、head が 3、tail が 1 だとすると、インデックス[3][0][1] が使われていますが、拡張後の配列 (要素数 8) で、インデックス[3][0][1] に要素を入れてしまうと [3] と [0] はつながっていないので (間に [4]～[7] があるので)、要素が分断されてしまいます。
このサンプルプログラムの場合は、拡張後の配列は、必ずインデックス[0] を head にして、 そこから連続して要素を入れていくように実装しています。
両端キューを実装する方法を３通り取り上げました。大きく分けると、連結リストを使う方法と、動的配列を使う方法があります。
途中の要素への直接アクセスの機能が必要であれば、性能の問題から、連結リストでの実装という手段は取れません。しかしながら、要素の追加も削除も O(1) で行えるので、全体的に性能は高いと言えます。
一方、動的配列で実装すると、容量が有限になるので、要素の追加時に、領域の再確保＆コピーという大きなコストが掛かる可能性があります。
問題① 動的配列によって実装された両端キューに、インデックスによる直接アクセスを行う機能を追加してください。
’2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。
’2015/1/17 新規作成。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |