スタック（stack）とキュー（queue）

• スタック（stack）やキュー（queue）とは、その端（ends）に対してのみ操作が可能なリスト（list）である
• ここでは配列を使って物理的な実現を行なっているが、 連結リスト（linked list）等で実現することもできる

スタック（stack）

• スタック（stack）とは、何かが積み重なった山のことである
• 後入れ先出し（Last In First Out : LIFO）型の記憶装置である
• 以下の操作が許されている
  • ：スタックトップにデータを置く
    • プッシュ（push）
  • ：スタックトップのデータを取り出す
    • ポップ（pop）

　配列を用いたスタックの実現

• 配列の最後のデータをスタックトップとみなし
  プッシュ（Push）は新たなデータを最後（の次）に挿入し
  ポップ（Pop）は最後のデータを削除する
• スタックトップのインデックスあるいはポインタ（スタックポインタと呼ぶ）を増減するだけで、配列内のデータを移動する必要は無く、高速に処理できる
• 満杯／空の処理は必要である
  （オーバーフロー／アンダーフローしないように！）

/* スタックデータ */
	int data[DATANUM] = { 123, 106, 777, 580, 216 };
/* データの個数 */
	int datanum = 5;
/*
	datanum-1 がスタックトップのインデックスを表す
	int	*sp = data;
	としてスタックポインタ sp を使っても良い
*/

　プッシュ（Push）

• 新たなデータをスタックトップに挿入する
  ●スタックトップ（datanum-1）を進め、データを挿入する（例えば、当初の配列の大きさを越えて挿入できない場合は、ステータスとして-1を返す）関数を作成し、キー入力したデータを挿入してみよう
  int push( int n );
  

　ポップ（Pop）

• スタックトップのデータを取り出し、削除する
  ●スタックトップ（datanum-1）のデータを読み出し、スタックトップを戻す（例えば、スタックが空でポップできない場合は、ステータスとして-1を返す）関数を作成し、そのデータを表示してみよう
  int pop( int *n );
  

キュー（queue）

• キュー（queue）とは、待ち行列（line）のことである
• 先入れ先出し（First In First Out : FIFO）型の記憶装置である
• 以下の操作が許されている
  • キューの末尾、後端、後ろ、終端（tail, rear, back, end）に挿入する
    • 挿入する（insert）、置く（put）、加える（add）、加列する（enqueue）
  • キューの先頭、前端（head, front）から削除する
    • 削除する（remove）、消す（delete）、除列する（dequeue）

　配列を用いたキューの実現

• Enqueueは新たなデータを最後（の次）に挿入し
  Dequeueは最初のデータを削除し、後のデータを１個ずつずらす
  　or
• Enqueueは、データを１個ずつずらして、新たなデータを最初に挿入し
  Dequeueは最後のデータを削除する
• 何れにしても、配列内でのデータ移動が伴い、遅い！
• 満杯／空の処理は必要である
  （オーバーフロー／アンダーフローしないように！）

　配列を用いたキューの実現（その２）

• 配列領域の先頭に末尾をつないで環（リング）とみなし
  キューの先頭および末尾のインデックスあるいはポインタを用意する
• Enqueueは新たなデータを末尾（の次）に挿入して、末尾を後にずらし
  Dequeueは先頭のデータを読み出して、先頭を後にずらす
  
• 何れも、インデックスあるいはポインタを進めるだけで、配列内のデータを移動する必要は無く、高速に処理できる
• 満杯／空の処理は必要である
  （オーバーフロー／アンダーフローしないように！）
  両インデックスあるいはポインタの追い越しに注意を払う必要がある

/* キューデータ */
	int	data[DATANUM] = { 123, 106, 777, 580, 216 };
/* 先頭のインデックス */
	int	head = 0;
/* 末尾のインデックス */
	int	tail = 4;
/*
	(tail + 1) % DATANUM == head の時、キューが空であるとする
*/

　Enqueue

• 新たなデータをキューに挿入する
  ●データを末尾（tail）の次に挿入し、末尾（tail）を進める（例えば、キューが満杯（データ数が容量−1）の時、ステータスとして-1を返す）関数を作成し、キー入力したデータを挿入してみよう
  int enqueue( int n );
  

　Dequeue

• キューからデータを取り出し、削除する
  ●先頭（head）のデータを読み出し、先頭（head）を進める（例えば、キューが空の場合は、ステータスとして-1を返す）関数を作成し、そのデータを表示してみよう
  int dequeue( int *n );
  

プライオリティキュー（priority queue）

• プライオリティキューは、優先度の順に並んだキューである
• 削除は先頭からなされるが、挿入時にはキーの順に並べられる
  
  
• この実現では配列を使っているが、ヒープ（heap）が使われることが多い

　順序配列を用いたプライオリティキューの実現

• 順序配列の最後のデータをキューの先頭とみなし
• Enqueueは新たなデータを順序を守って挿入する、
  その場所以降にあったデータは１個ずつずらす
  Dequeueは順序配列の最後のデータ（キューの先頭）を削除する
• 何れにしても、配列内でのデータ移動が伴い、遅い！
• 満杯／空の処理は必要である
  （オーバーフロー／アンダーフローしないように！）

/* プライオリティキューデータ */
	int data[DATANUM] = { 106, 123, 136, 197, 216 };
/* データの個数 */
	int datanum = 5;
/*
	datanum-1 がキューの先頭のインデックスを表す
*/

　Enqueue

• 新たなデータをキュー即ち順序配列の順序を守って挿入する
  その場所以降にあったデータは１個ずつずらす
  ●データを挿入する（例えば、キューが満杯の時、ステータスとして-1を返す）関数を作成し、キー入力したデータを挿入してみよう
  int enqueue( int n );
  

　Dequeue

• キューからデータを取り出し、削除する
  ●キューの先頭（配列の最後）の（datanum-1）のデータを読み出し、最後を戻す（例えば、キューが空の場合は、ステータスとして-1を返す）関数を作成し、そのデータを表示してみよう
  int dequeue( int *n );
  

　ヒープを用いたプライオリティキューの実現

• ヒープのルート（配列の先頭）をキューの先頭とみなし
• Enqueueは新たなデータをヒープの順序を守って挿入する
  Dequeueはヒープのルート削除し、ヒープの整合性をとる
• データ移動は高々ヒープ木の高さ分で済む
• 満杯／空の処理は必要である
  （オーバーフロー／アンダーフローしないように！）

/* ヒーププライオリティキューデータ */
	int data[DATANUM] = { 216, 197, 136, 123, 106 };
/* データの個数 */
	int datanum = 5;

　Enqueue

• 新たなデータをヒープ配列の最後に挿入し、
  そこから上（ルート）に向かって所定の位置まで移動する
  ●データを所定の位置に挿入する（例えば、ヒープ配列が満杯の時、ステータスとして-1を返す）関数を作成し、キー入力したデータを挿入してみよう
  int enqueue( int n );
  

　Dequeue

• キューの先頭（ヒープ配列の最初）のデータを削除する
  ヒープ配列の最後のデータを先頭（ルート）に移動し、
  そこから下（リーフ）に向かって所定の位置まで移動する
  ●ヒープのルート削除し、ヒープの整合性をとる（例えば、ヒープ配列が空の場合は、ステータスとして-1を返す）関数を作成し、そのデータを表示してみよう
  int dequeue( int *n );