Ibaraki Univ. Dept of Electrical & Electronic Eng.

Presentation on theme: "Ibaraki Univ. Dept of Electrical & Electronic Eng."— Presentation transcript:

1 Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 Ibaraki Univ. Dept of Electrical & Electronic Eng. Keiichi MIYAJIMA

2 スタックとキュー

3 バッファ，キュー，スタック，キャッシュ CPU コンピュータ内部だけでなく、インターネット上にも、伝送速度が異なる者同士が接続されている
高速な装置 バッファ 低速な装置 CPU キャッシュメモリ 主記憶装置 ハードディスク 主記憶装置 ディスクキャッシュ

4 キュー・スタック スタック(stack) データを順に積み上げていく データ１ Push : データを順に積み上げていく動作

5 キュー・スタック スタック(stack) データを順に積み上げていく データ２ データ１

6 キュー・スタック スタック(stack) データを順に積み上げていく データ３ データ２ データ１

7 キュー・スタック スタック(stack) データを順に積み上げていく データ４ データ３ データ２ データ１

8 キュー・スタック スタック(stack) 出すときは上から Pop : データを取り出す操作 データ４ データ３ データ２ データ１

9 キュー・スタック スタック(stack) 出すときは上から データ４ FILO (First In Last Out)方式 データ３
データ２ データ１

10 キュー・スタック キュー(Queue: 待ち行列) データ１ 入口 出口 Enque : データをキューに入れる操作

11 キュー・スタック キュー(Queue: 待ち行列) データ２ データ１ 入口 出口

12 キュー・スタック キュー(Queue: 待ち行列) データ３ データ２ データ１ 入口 出口

13 キュー・スタック キュー(Queue: 待ち行列) データ４ データ３ データ２ データ１ 入口 出口

14 キュー・スタック キュー(Queue: 待ち行列) データ４ データ３ データ２ データ１ 入口 出口
Deque : データをキューから取り出す操作

15 キュー・スタック キュー(Queue: 待ち行列) データ５ データ４ データ３ データ２ 入口 出口 データ１

16 キュー・スタック キュー(Queue: 待ち行列) データ６ データ５ データ４ データ３ データ２ 入口 出口
FIFO (First In First Out)方式 最初(First)に入った(In)ものが、 最初(First)に出る(Out)

17 キューの実現方法 リングバッファ キューの先頭 データ１ データ２ キューの最後 データ３

18 キューの実現方法 リングバッファ データ１ キューの先頭 キューの最後 データ３ データ２

19 キューの実現方法 リングバッファ キューの先頭 データ３ データ２ キューの最後 データ４ データ５

20 キューの実現方法 リングバッファ キューの最後 データ４ データ５ データ３ キューの先頭 データ２

21 本日の課題 空の状態のキューとスタックの二つのデータ構造がある。次の手順を順に実行した場合、変数xに代入されるデータは何か？　プログラムを作成し、実行結果を示せ。 ここで、 データyをスタックに挿入することを push(y) スタックからデータを取り出すことを pop() データyをキューに挿入することを enq(y) キューからデータを取り出すことを deq() と、それぞれ表す。 手順： push(a) push(b) enq(pop()) enq(c) push(d) push(deq()) x=pop() なお、キューとスタックはそれぞれ文字が1文字入るデータ型(char型)で構成されるものとして良い。

22 レポートの〆切と提出先 レポート提出先： E2棟（旧システム棟）６F606室（宮島教員室）前 レポートBOX レポート〆切：
５月１１日月曜日　PM５：００頃 課題について、プログラムを作成し、プログラムと実行結果をプリントアウトしたものを提出すること。