読者です 読者をやめる 読者になる 読者になる

No Caffeine, No Life

プログラミング(主にPython)

Aizu Online Judge: 双方向連結リスト(dequeの使い方)

双方向連結リスト

以下の命令を受けつける双方向連結リストを実装してください。
 
- insert x: 連結リストの先頭にキー x を持つ要素を継ぎ足す
- delete x: キー x を持つ最初の要素を連結リストから削除する
- deleteFirst: リストの先頭の要素を削除する
- deleteLast: リストの末尾の要素を削除する
 
全ての命令が終了した後の、連結リスト内のキーを順番に出力してください。連続するキーは1つの空白文字で区切って出力してください。

 基本的には普通のリストを用いれば書けるが、より効率的にスタック・キュー処理が行えるものとしてpythonではdequeが用意されている。 通常のリストでも append pop insert などのキュー・スタック的処理は行えるが、キュー・スタック処理のためだけに設計されたものではないため効率的ではないようで。一方この deque はキュー・スタック的処理を行うことを念頭に作られているため、先頭での処理、末尾での処理ともに O(1) のオーダーで高速に実行できるらしい。。。

 

実際、リストを用いた場合はAOJのテストケースのうち、#10だけはTLEとなってしまう。 そこでdequeを用いてみる。

dequeの使い方はたとえば

www.lifewithpython.com

を見てみるとよい。ついでに、上記プログラム中のtry: ~ excep:の使い方も注目。

広告を非表示にする