イヌとネコを格納するキュー

世界で闘うプログラミング力を鍛える150問』から、データ構造に関する問題を解いていこう。

イヌとネコしか入ることのできない動物保護施設があります。この施設は「先入れ先出し」の操作を厳格に行います。施設からは一番長い時間入っている動物を外に出すか、イヌとネコの好きなほう (で一番長い時間入っているもの) を外に出すことができます。どの動物でも好きなように連れ出せるわけではありません。このような仕組みを扱うデータ構造を作ってください。さらに enqueuedequeueAnydequeueDogdequeueCat の操作を実装してください。あらかじめ用意された連結リストのデータ構造は用いてもよいものとします。 (P.213)

データ構造

今回は次のようなアイディアを考えた。

  1. イヌ用のキューとネコ用のキューを持つ ZooQueue クラスを作る
  2. Animal クラスを作成し、インスタンス変数 kind に “dog” か “cat” という値を格納できるようにする
  3. ZooQueue クラスの enqueue() メソッドは引数として Animal クラスのオブジェクトを受け取り、次の処理を行う
  • 引数に与えられたオブジェクトの kind が “dog” であれば、イヌ用のキューに「カウンタの値」と「オブジェクト」を追加する (カウンタの値はインクリメントする)
  • 引数に与えられたオブジェクトの kind が “cat” であれば、ネコ用のキューに「カウンタの値」と「オブジェクト」を追加する (カウンタの値はインクリメントする)

ここまでがデータを格納するときの動作だ。

データを取得するときのメソッドについて考えてみよう。dequeueDog()dequeueCat() は簡単だ。dequeueDog() ならイヌ用のキューからふたつ値を取り出し、ふたつ目の値を返せばよい (カウンタの値は不要)。dequeueCat() ならネコ用のキューで同様のことをする。

dequeueAny() の場合は、イヌ用のキューとネコ用のキューから、それぞれ値を peek() する。小さい値を返すキューから、ふたつ値を取り出し、ふたつ目の値を返す。

それほど実装の難しくないデータ構造だろう。

実装

では、Python でこのデータ構造を実装してみよう。

考察

この実装は、本に書かれている Java の実装とは異なる。Java の場合はキューに入れるオブジェクトの型を指定する必要があるため、整数値 (オーダー) と Animal クラスのオブジェクトを交互に入れることはできない。Python は型に関して柔軟で、書き心地がよい。

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中