データ構造とアルゴリズム 第13回 スタックとキュー データ構造とアルゴリズム 第13回　スタックとキュー 静岡大学工学部 安藤 和敏 2011.07.08

目次 復習 データ処理の２つの順番 スタックの概念 リスト構造を用いたスタックの実装 キューの概念 リスト構造を用いたキューの実装 演習

目次 復習 データ処理の２つの順番 スタックの概念 リスト構造を用いたスタックの実装 キューの概念 リスト構造を用いたキューの実装 演習

複数の仕事やデータの処理の順番 あなたは図書館で勉強していた．そこへ，あなたの親友がやってきて恋愛相談に乗って欲しいと声をかけられた．返事をしようとしていたら，親から携帯に電話がかかってきた． 図書館で勉強する． 親友の恋愛相談に乗る． 携帯電話にでる． (C) → (B) → (A) の順番で仕事をするのが普通．

複数の仕事やデータの処理の順番 あなたはファーストフード店で注文を受けるバイトをしている．レジの前には3人の客が並んでいる．あなたはこの3人の客から， チーズバーガーとコーラ てりやきバーガーとコーヒー フィッシュバーガーとコーヒー という順番で注文を受けた． (A) → (B) → (C) の順番で仕事をする．

複数の仕事やデータの処理の順番 処理要求の順番が遅いものから処理を済ませる． 処理要求の順番が早いものから処理を済ませる． アルゴリズムの分野では，(1) の処理方法を LIFO (Last In First Out の略，ライフォ，リフォと読む)と呼び，(2) の処理をFIFO (First In First Out の略，ファイフォ，フィフォと読む)と呼ぶ． (1) のLIFO はスタック (stack) によって，(2) のFIFO はキュー (queue) によって実現される．

目次 復習 データ処理の２つの順番 スタックの概念 リスト構造を用いたスタックの実装 キューの概念 リスト構造を用いたキューの実装 実習

スタックみたいなもの スピンドルケース入りCD 本の山

スタックの概念図 格納 取り出し 6 3 2 4 1 5

スタックに対する操作（Push) Push(x): スタックにデータ x を格納する． x 2 4 1

スタックに対する操作（Pop) Pop(): スタックからデータの取り出しを行い,取り出したデータを返す． 2 4 1

目次 復習 データ処理の２つの順番 スタックの概念 リスト構造を用いたスタックの実装 キューの概念 リスト構造を用いたキューの実装 演習

リスト構造を用いたスタックの実装 格納 取り出し 2 4 1 root ２ 4 １

関数 Push の説明 2 4 1 x void Push(int x) { struct CELL *newcell; newcell = (struct CELL *) malloc(sizeof(struct CELL)); newcell->data = x; newcell->next = root; root = newcell; } root 2 4 1 x newcell

関数 Pop の説明 1 4 2 int Pop(void) { int x; struct CELL *temp; if (root == NULL) { printf("Error: Stack is empty.\n"); return; } x = root->data; temp = root; root = root->next; free(temp); return x; temp 1 4 2 root

目次 復習 データ処理の２つの順番 スタックの概念 リスト構造を用いたスタックの実装 キューの概念 リスト構造を用いたキューの実装 演習

キューみたいなもの ラーメン屋

キューの概念図 3 5 1 4 2 取り出し 格納

キューに対する操作 (Enqueue) Enqueue(x): キューにデータ x　を格納する． x 1 4 2

キューに対する操作 (Dequeue) Dequeue(): キューからデータの取り出しを行い，取り出したデータを返す． 1 4 2

目次 復習 データ処理の２つの順番 スタックの概念 リスト構造を用いたスタックの実装 キューの概念 リスト構造を用いたキューの実装 演習

リスト構造を用いたキューの実装 1 4 2 取り出し 格納 tail head 1 4 2

関数 Dequeue の説明 1 4 2 int Dequeue(void) { int x; struct CELL *temp; if (head == NULL) { printf("Error: Queue is empty.\n"); return; } x = head->data; temp = head; head = head->next; free(temp); if(head==NULL) tail=NULL; return x; temp tail 1 4 2 head

関数 Enqueue の説明 2 4 1 x void Enqueue(int x) { struct CELL *newcell; newcell = (struct CELL *) malloc(sizeof(struct CELL)); newcell->data = x; newcell->next = NULL; if(tail!=NULL) tail->next = newcell; tail = newcell; if(head==NULL) head = newcell; } head 2 4 1 tail x newcell

目次 復習 データ処理の２つの順番 スタックの概念 リスト構造を用いたスタックの実装 キューの概念 リスト構造を用いたキューの実装 演習