3 posts tagged with "Stack"

1. 主なデータの管理・取り出し方法

1. LIFO (Last-In First-Out): キューなどに使われる。
2. FIFO (First-In First-Out): スタック。再帰的な処理をする際、実行中の状態を保存しておく為にも使われる。
3. LFU (Least Frequently Used): 参照頻度が最も少ないものを取り出す。
4. LRU (Least Recently Used): 未使用時間が最も長いものを取り出す。

ソースコード​

#!/usr/bin/python
# coding: UTF-8
# リストの要素の追加と削除(取出し) | append()、extend()、pop()、remove()メソッドの使い方
a = [3, 5, 7, 9, 11]
print a
a.append(13)               # 引数のオブジェクトをリストの末尾に追加
print a
a.extend([15, 17, 19, 21]) # 引数のシーケンスを展開して末尾に追加
print a
elm = a.pop()              # リストの末尾から要素を1つ取り出す
print 'elm == %d' % elm
print a
elm = a.pop(4)             # 引数にリストのインデックスを取り、その要素を取り出す
print 'elm == %d' % elm
print a
a.remove(13)               # 引数のオブジェクトをリスト要素から削除する
print a

実行結果​

[3, 5, 7, 9, 11]
[3, 5, 7, 9, 11, 13]
[3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
elm == 21
[3, 5, 7, 9, 11, 13, 15, 17, 19]
elm == 11
[3, 5, 7, 9, 13, 15, 17, 19]
[3, 5, 7, 9, 15, 17, 19]

リファレンス​

• 3.6 Sequence Types -- str, unicode, list, tuple, buffer, xrange
• deque 型(参考)
  • 5.3.1 deque objects
  • 5.3.1.1 Recipes

チュートリアル​

• 3. An Informal Introduction to Python
  • 3.1.4 Lists

先日勉強会でこの辺のテーマを取り上げたので、字句解析や構文解析(の一部)とスタックの復習も兼ねて作成(required for 1h+)。

実装のポイント​

• 閉じ括弧の有無の判定は、ファイルの終端が読み終わった後。
• 開き括弧の判定は、閉じ括弧を読み込んだ際に行い、スタックの最上位に対応する開き括弧があるか否かで。
• 入れ子の(または再帰的な)構造で、どの深さにスレッドがいるか調べるにはスタックを用いる。