make

まけ

スタック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とかやっていたおかげで,再帰を使うのが苦にならなくなったけど,普通に解くのに時間がかかるなー.
一瞬で思いつくようになりたい.