Views
Document
Event
File
Folder
Image
Link
News Item
Photo
Photo Album
Topic
Weblog
Wiki Page
スタックと待ち行列
Document Actions
線形(linear)なデータ構造
レコード(Record)
- 複数のフィールド(Field)からなるデータ
氏名 生年月日 出身 吉澤ひとみ 1985年4月12日 埼玉県 高橋愛 1986年9月14日 福井県 紺野あさ美 1987年5月7日 北海道 - はろぷろ より抜粋引用
- 横（行）がレコード。
- 同じフィールドを持つレコードの集まり -> テーブル(Table, 表)
関係
- レコード間の関係（大小関係）
- テーブル間の関係 -> リレーショナル・データベース
- Oracle, PostgreSQL などのリレーショナルデータベースが使いこなせると、飯が食える（かもしれない）
論理構造と物理構造
- レコードは C 言語の構造体に相当
struct helopro { char name[30]; char birth[11]; char pref[15]; };struct helopro mormusu[] = ... ;
- この例では、論理構造＝物理構造
リスト構造
- ポインタを使って、レコード間の連鎖を表す。
struct helopro_list { char name[30]; char birth[11]; char pref[15]; struct helopro_list *next; };
もっとポインタを使う
struct list_helopro { struct helopro ＊talent; struct list_helopro ＊next; };
例（次回の演習）
リストへ要素を挿入
スタックと待ち行列
- 線形リストで
- 追加、取り出し（削除）は一端のみ ... スタック(stack)
- 追加は先頭、取り出し（削除）は末尾 ... 待ち行列(queue)
スタック
- push （追加）
- pop （取り出し・削除）
- LIFO ... Last-In-First-Out （後入れ先出し）
スタックの例(CPU)
- Motorola M6800 (1976)
8bitレジスタの push/pop
副プログラムの呼び出し
- 戻りアドレスを push
割り込み
- CPU レジスタを全部 push
Python での実装
- リスト型のメソッド（メンバー関数）を使う
>>> a = [] >>> a.append(1) >>> a.append(2) >>> a.append(3) >>> a.pop() 3 >>> a.pop() 2 >>> a.pop() 1 >>>
待ち行列
- Queue （キュー）
- enqueue （追加、入力）
- dequeue （取り出し、出力）
待ち行列の例
- 通信機器では必須
- UNIX のパイプ (|)
$ ls -lt | head
$ tail -f /var/log/syslog | grep reject
mkfifo コマンドで作るパイプ(FIFO)
- ターミナルを２つ立ち上げて実験する。
$ mkfifo pipe $ cat > pipe ABC DEF GHI JKL ^D
$ ls -l pipe prw-r--r-- 1 tkikuchi tkikuchi 0 5 2 14:41 pipe $ cat pipe ABC DEF GHI JKL
Python での実装
- リスト型を使う
>>> q = [] >>> q.append(1) >>> q.append(2) >>> q.append(3) >>> q.pop(0) 1 >>> q.pop(0) 2 >>> q.pop(0) 3 >>>
本日の問題
- リストの例としてあげた以下の図で、２番目の要素をリストから取り除くと、ポインタによる 参照を表す矢印はどのようになるか。
回答
- 1本矢印（線）を付け替える。
