スタックを使ったキューの実装

世界で闘うプログラミング力を鍛える150問』を読んでいると、「スタックを使ってキューを実装する」というお題が出てきた。これは面白そうだ。本の中では Java での実装が出ているが、ここでは Python に内容を置き換えた上で自分の言葉に直し、解説してみようと思う。

スタックとキューの違い

スタックは FILO (First In Last Out) のデータ構造である。最初に入れたデータが最後に出てくる。一方で、キューは FIFO (First In First Out) のデータ構造だ。つまり、スタックを使ってキューを実装するときは “First In” の部分はそのままでよく、”Last Out” と “First Out” の部分だけ工夫すればいいことになる。

このことを踏まえ、一歩ずつ実装していこう。

スタックの実装

何はともあれ、スタックがなければ始まらない。Python のリストを使い、手抜きの実装をしてしまおう。

何も難しいことはない。MyStack クラスでは、リストの最後に値を append() することを push()、リストの最後の pop() することを pop() として実装している (同じ名前なのでややこしいけど…) だけだ。

キューの実装

さあ、ここからが本題だ。先にキューの実装を示そう。

__init__()enqueue_stackdequeue_stack が作られている。名前が示す通り、前者がエンキュー用で後者がデキュー用のデータ構造だ。enqueue()dequeue() の振る舞いをそれぞれ見ていこう。

まずは enqueue() だ。前述の通り、”First In” はスタックもキューも同じだ。なので encueue() メソッドは単に enqueue_stackpush() するだけだ。

次に dequeue() だ。最初は dequeue_stack は空っぽだ。これにデータを詰めるために、逐一 enqueue_stack からデータを pop() し、それを dequeue_stackpush() する。こうすることで、enqueue_stack にあったデータが逆順になって dequeue_stack に入るのだ。この作業により dequeue_stack から pop() する操作が “Last Out” から “First Out” になる。

全体

先ほどの二つをくっつけて、実際に動作するサンプルコードも載せておこう。

何かの参考になれば嬉しい。

コメントを残す

コメントを投稿するには、以下のいずれかでログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中