スタック1つだけでキューをシミュレートする
とあるブログを読んでいて出てきた問題を,Pythonで解いてみた.
def enqueue(stack,d): stack.append(d) def dequeue(stack): d = stack.pop() if stack: a = dequeue(stack) enqueue(stack,d) return a else: return d stack = [1,2,3] enqueue(stack,10) print stack #[1, 2, 3, 10] print dequeue(stack) #1 print dequeue(stack) #2 print dequeue(stack) #3 enqueue(stack,20) enqueue(stack,30) print dequeue(stack) #10 print dequeue(stack) #20 print dequeue(stack) #30
スタックでキューを実装する場合,取り出す要素はスタックの一番深いところにいるので,まずは再帰で一番下まで掘り進む.
一番下の要素を返しつつ,スタックに順番にデータを戻していく.
dequeueの中のenqueueは,どちらかというとstack.push(d)という意味合い.
pythonのリストにpushメソッドが無いので,enqueue使っているけどappendの方が読むときにはわかりやすいかもしれない.
LISPerにあこがれてSICPとかやっていたおかげで,再帰を使うのが苦にならなくなったけど,普通に解くのに時間がかかるなー.
一瞬で思いつくようになりたい.