要素を１列に並べたもの。どの要素でも自由に参照、

上級プログラミング !

キュー !"#$%$%&

キュー !"#$%$%&! とは

• 

基本的な抽象データ型としての「リスト」

– 

要素を１列に並べたもの。どの要素でも自由に参照、

挿入、削除できる柔軟な構造をもつ。

– 

特殊なリスト：スタック

、キュー

• 

スタック

– 

挿入や削除がいつも一方の端からしかできないもの

後入れ先出しリスト 

• 

キュー

– 

挿入が一方の端（最後尾）から行われ、削除は反対 の端（最先端）からしかできないもの

– 

先入れ先出しリスト

キュー !"#$%$%&! とは（続き）

• 

逐次的な入出力が繰り返されるときに使用

• 

データを一時的に蓄えておくためのデータ構造

• 

入ってきたデータの順にデータを取り出す

• 

日本語で「待ち行列」

8 99 : ;

出力

入力

8 99 : ;

99 : ; <

8

<

<

キューが使われているところ

• 

プリンタの印刷待ち

• 

キーボードの入力待ち

•  =>?!

の計算待ち

•  @

キューの基本操作

• 

入力

– %4A$%$%!

とよぶ

– 

入力データは順次最後尾に追加される

• 

出力

– B%A$%$%!

とよぶ

– 

データは先頭から順に出力される

【参考】スタックの基本操作

– C$1D5!C7C!

キューの実現：データ構造

• 

リストの実現方法

– 

配列

– 

連結リスト（ポインタ）

• 

キューの特性をどのように実現するか？

– 

キューがキューたるに必要な何か

– 

先頭

最後尾

– 

データ長（キューにあるデータの個数：可変）

配列による実現（入力）

8 EFGE9GE;G E<G EHG EIGEJGE8G

8

EFGE9GE;G E<G EHG EIGEJGE8G

8 99

EFGE9GE;G E<G EHG EIGEJGE8G

初期状態B)()

B)()

B)()

%4A$%$%

99

%4A$%$%

データ長：F

データ長：9

データ長：; 先頭

配列による実現（出力）

8 99 : ; <

8

EFGE9GE;G E<G EHG EIGEJGE8G

99 : ; <

EFGE9GE;G E<G EHG EIGEJGE8G

: ; <

EFGE9GE;G E<G EHG EIGEJGE8G B)()

B)()

B)()

B%A$%$%

99

B%A$%$%

データ長：I

データ長：H

データ長：<

入力に関する問題点

8 99 : ; < 9 H 9I

K EFGE9GE;G E<G EHG EIGEJGE8G

B)()

%4A$%$%

データ長：:!

（最大長）

追加不能

配列のサイズまでしかデータを追加できない

出力に関する問題点

8 99 : ; <

8

EFGE9GE;G E<G EHG EIGEJGE8G

EFGE9GE;G E<G EHG EIGEJGE8G

: ; <

EFGE9GE;G E<G EHG EIGEJGE8G B)()

B)()

B)()

B%A$%$%

99

B%A$%$%

データ長：I

データ長：H

データ長：<

99 : ; <

１つずつ左にシフト

１つずつ左にシフト

B%A$%$%!

の度にデータをシフトするのは非効率

先頭

出力に関する課題

• 

データをシフトさせないためには

– 

データをシフトするのは、キューの先頭が配列の 第

番めに固定されているから

– L%A$%$%!

の度にキューの先頭を「ずらす」

8 99 : ; < 9

EFGE9GE;G E<G EHG EIGEJGE8G B)()

8 先頭

B%A$%$%

8 99 : ; < 9

EFGE9GE;G E<G EHG EIG EJG E8G B)()

先頭

とはいえ、このままでは、

データの最大長が減ってしまう

出力に関する課題（続き）

• 

データをシフトさせない

– 

キューの先頭とみなす配列要素番号をずらせば よさそう

• 

データの最大長を維持するには

8 99 : ; < 9

EFGE9GE;G E<G EHG EIG EJG E8G B)()

先頭 移動した要素の個数分だけ! あたかも続いているように@!

扱えないものか？

出力の問題点への解決手法

8 99 : ; < 9

EFGE9GE;G E<G EHG EIGEJGE8G B)()

EFG

E9G

E;G E<G

EHG EIG

EJG

E8G

< ;

: 99 8

9

配列を環状に考える

B)()

配列を環状にするための要件

• 

先頭が配列要素を移動しても、キューに入っている データ順序は変わらず、かつそれぞれのデータは配 列要素に一意に格納される。

• 

キューの先頭をどのように表すべきか？

– 

データの先頭を指す変数を導入する

その変数は具体的 に何を示しているか？

• 

最後尾はどのように表されるか？

– 

先頭からデータ長の分だけ「先に」ある

• 

配列の末端要素まで辿り着いたとき、その次の要素と

して配列の先端要素に戻るにはどうすればよいか？

配列を環状にする !"9&

8 99 : ; <

8

EFGE9GE;G E<G EHG EIGEJGE8G

8 99 : ; <

EFGE9GE;G E<G EHG EIGEJGE8G

8 99 : ; <

EFGE9GE;G E<G EHG EIGEJGE8G B)()

B)()

B)()

B%A$%$%

99

B%A$%$%

データ長：I

データ長：H

データ長：<

41!

を１つ移動

41!

を１つ移動

データの先頭を指す変数を導入する

41

41

41

41!N!F!から 始める

データをシフトせずに!41!をシフトさせる

配列を環状にする !";&

8 99 : ; <

EFGE9GE;G E<G EHG EIGEJGE8G

8 99 : ; < 9

EFGE9GE;G E<G EHG EIGEJGE8G B)()

B)()

データ長! O%4P(D!N!<

データ長! O%4P(D!N!H

;M!

最後尾

の位置にデータを追加する

41

41

%4A$%$%

41!Q!O%4P(D

9

配列を環状にする !"<&

8 99 : ; < 9 H 9I EFGE9GE;G E<G EHG EIGEJGE8G

K 99 : ; < 9 H 9I EFGE9GE;G E<G EHG EIGEJGE8G B)()

B)()

データ長! O%4P(D!N!H

データ長! O%4P(D!N!I

;RM!"41!Q!O%4P(D&!S!)66)T'3U%

の位置にデータを追加する

41

41

K

%4A$%$%

41!Q!O%4P(D

このままでは!41!Q!O%4P(D!は! 配列のサイズ以上

8 99 : ; < 9 H 9I EFGE9GE;G E<G EHG EIG EJG E8G B)()

41

配列のサイズ! )66)T'3U%!N!:

"41!Q!O%4P(D&!S!)66)T'3U%

"41!Q!O%4P(D&!S!)66)T'3U% 41!も同様に巡回的に動くようにする

配列を環状にしている!

（添字が巡回的に動く）

使用済みデータに上書き

「S」を利用する

入力に関する課題と解決方法

• 

配列のサイズ以上の入力を可能にするに は

• 

配列を動的に確保する

– 4%V!

と

を使った配列の動的確保

• 

キューの実現に配列を使わない

– 

配列を使うから終わりがある

連結リストを使う

– W%*(76!

などを使う

4%V!

と

を使った配列の動的確保

4%V!

と

を使って任意のサイズの配列を動的に確保

!!XX!9F

個の要素をもった 

型配列を確保

!!int *xvec = new int[10];!

!!XX!9;F

個の要素をもった

型配列の確保

!!double *yvec = new double[120];!

!!XX!

入力値を大きさとする 

型配列を確保

!!int num;!

!!cout << ”Input array size -->”;!

!!cin >> num; !XX!

配列サイズの入力

!!int *avec = new int[num];!

4%V!

と

を使った配列の動的確保

（イメージ）

9F;F 9FFF

9FFH 9FF:

9F9;

9F9J 9F;F 9F;H 9F;:

9F<;

9F<J 9FHF 9FHH

//

５個の要素をもった

型配列を確保

int *xvec = new int[5];!

配列要素にアクセスする方法

*xvec or xvec[0]

*(xvec + 1) or xvec[1]

*(xvec + 4) or xvec[4]

4%V!で確保された領域!

メモリ上のどこかに領域が確保され、

その先頭アドレスが 

に返る

確保した領域の解放

B%O%(%!

と

を使って動的に確保した配列を解放する

!!XX!9F

個の要素をもった 

型配列を確保

!!int *xvec = new int[10];!

（

を使った処理）

!!delete [] xvec; // xvec

が指し示す先で確保

//

されている配列の領域全体

をまとめて解放

※１ 上記の例で、仮に

を忘れて「

」としてもコンパイルは

   通るが、正しく解放されない。

※２ 

に指定するポインタとして、

ポインタを指定することも

   文法的には認められており、特に何も起こらない。

キューをクラスとして実装

//

クラスの実装例

class QueueInt{ !// int

型データのみを扱えるキュー

int ns; ! ! !//

データの先頭

データ長

int arraySize; !//

配列のサイズ

int *data; ! !// int

型データを格納する配列の先頭アドレス

public:!

QueueInt(const int = 10);!

void push(const int); // enqueue!

// front()

と

の２つで 

int front() const;!

void pop();!

int size() const;!

};!

コンストラクタ、 %4A$%$%

//

コンストラクタ

QueueInt::QueueInt(const int aSize) {!

ns = 0; length = 0; arraySize = aSize;!

data = new int[arraySize]; !//

データ領域の確保

//

データの追加

void QueueInt::push(const in num) {!

if (length >= arraySize) {!

cerr << ”ERROR:

データを追加できません

exit(EXIT_FAILURE);!

}!

data[(ns + length) % arraySize] = num;!

++length;!

}!

B%A$%$%

int QueueInt::front() const {!

if (length <= 0) {!

cerr << “”ERROR:

データが１つもありません

exit(EXIT_FAILURE);!

}!

return data[ns];!

}!

void QueueInt::pop() {!

if (length <= 0) {!

cerr << ”ERROR:

データが１つもありません

exit(EXIT_FAILURE);!

}!

// ns

が 

以上にならないように制御する

--length;!

}!

データ長

//

データ長を返す

int QueueInt::size() const {!

return length;!

}!

簡単なプログラム例と実行結果

int main(){!

QueueInt q(5);!

for (int i = 4; i >= 0; --i) {!

q.push(i * 10); !// 40,30,20,10,0 が順にキューに溜まる! }!

cout << ”q.front() = ” << q.front() << endl;!

q.pop();!// 先頭要素を削除!

cout << ”q.size() = ” << q.size() << endl;!

q.push(99);!

cout << ”q.size() = ” << q.size() << endl;!

// キューに溜まっている数値をすべて表示する! while (q.size() > 0) {!

cout << q.front() << ” ”;!

q.pop();!

}!

cout << endl;!

return EXIT_SUCCESS;!

}!

実行結果!

q.front() = 40!

q.size() = 4!

q.size() = 5!

30 20 10 0 99!

データ長が 

以上に

なったときの対処法

9M 

例えば 

の

倍のサイズの領域

を別に確保する

;M  41!

の位置から順にデータを

に複製する

<M  B)()!

が指し示している配列領域をまとめて解放

した後に、

に格納されているアドレスを

に複製する

HM  415!)66)T'3U%!

を更新する

IM  "41!Q!O%4P(D&!S!)66)T'3U%!

の位置に新しい数値を

追加する

具体的手順１

K ; J I < 9 H 9I

: EFGE9GE;G E<G EHG EIGEJGE8G

B)()

%4A$%$%

データ長! O%4P(D!N!:

9M!

例えば 

の

倍のサイズの領域を別に確保する

(%^C

EFGE9GE;G E<G EHG EIGEJGE8G E:G EKGE9FGE99GE9;GE9<GE9HGE9IG 41

"41!Q!O%4P(D&!S!)66)T'3U%

配列のサイズ! )66)T'3U%!N!:

これ以上追加不能！!

%4A$%$%!する前に!

4%V!と!E!G!を使って )66)T'3U%!の

;倍のサイズの領域を確保! このままでは無理!

具体的手順２

K ; J I < 9 H 9I EFGE9GE;G E<G EHG EIGEJGE8G B)()

;M!41!

の位置から順に複製する

< 9 H 9I K ; J I (%^C

EFGE9GE;G E<G EHG EIGEJGE8G E:G EKGE9FGE99GE9;GE9<GE9HGE9IG 41

具体的手順３

K ; J I < 9 H 9I EFGE9GE;G E<G EHG EIGEJGE8G B)()

<M!B)()!

が指し示している配列領域をまとめて解放した後に、

(%^C!

に格納されているアドレスを

に複製する

< 9 H 9I K ; J I (%^C

EFGE9GE;G E<G EHG EIGEJGE8G E:G EKGE9FGE99GE9;GE9<GE9HGE9IG (%^C!

に格納されている

アドレスを

に複製

解放

以降、

~

は、それぞれ

~

と

まったく同じ場所を表す

具体的手順４

HM!415!)66)T'3U%!

の更新する

< 9 H 9I K ; J I B)()

EFG E9G E;G E<G EHG EIGEJGE8G E:G EKGE9FGE99GE9;GE9<GE9HGE9IG

)66)T'3U%

41

・先頭要素は

となるので、

とする

・新しい配列サイズは、今の場合 

となるので、

とする

具体的手順５

IM!"41!Q!O%4P(D&!S!)66)T'3U%!

の位置に新しい数値を追加する

< 9 H 9I K ; J I B)()

EFG E9G E;G E<G EHG EIGEJGE8G E:G EKGE9FGE99GE9;GE9<GE9HGE9IG 41

< 9 H 9I K ; J I : B)()

EFGE9GE;G E<G EHG EIG EJG E8G E:G EKGE9FGE99GE9;GE9<GE9HGE9IG 41

"41!Q!O%4P(D&!S!)66)T'3U% データ長!

O%4P(D!N!:

:

%4A$%$%

"41!Q!O%4P(D&!S!)66)T'3U% データ長! O%4P(D!N!K

連結リストによるキューの実現

•  %4A$%$%!

– 

構成要素をリストに追加する（繋げ方に注意）

•  B%A$%$%!

– 

リストから先頭の要素を削除する

%4A$%$%

H5!9:5!I!

というデータが順に入力されたとき

B)() 4%Z(

B)() 4%Z(

B)() 4%Z(

初期状態： IntBox *pf = NULL, *pe = NULL;

B)() 4%Z(

B)() 4%Z(

B)() 4%Z(

C_

C%

C_

C_

H

%4A$%$%

9:

%4A$%$%

I

%4A$%$%

H

9:

I ]?,,

]?,,

]?,, H

H 9:

C%

C%

C_!0!リストの先頭を指し示すポインタ!

C%!0!リストの末尾を指し示すポインタ!

B%A$%$%

B)() 4%Z(

B)() 4%Z(

B)() 4%Z(

B)() 4%Z(

B)() 4%Z(

C_

C_

I I

]?,, ]?,,

9:

H 9:

C%

C%

H

B%A$%$%

データが１つ出力されたとき