Implement Queue Using Stacks
2つのスタックだけを使って、先入れ先出しのキューを実装してください。スタックでは、アイテムを一番上に追加する、一番上のアイテムを取り出す、一番上のアイテムを読み取る、空かどうかを確認する操作だけができます。キューは、push x（末尾にxを追加）、pop（先頭のアイテムを取り出して返す）、peek（先頭のアイテムを返す）、empty（キューが空かどうかを返す）をサポートします。
操作は順番にopsとして与えられます。args[i]には、pushの場合は値が、それ以外のすべての操作の場合は0が格納されています。空の状態で始まる1つのキューに対して操作を実行し、操作ごとに1つの文字列を返してください。pushの場合は"null"、popまたはpeekの場合は数値を文字列にしたもの、emptyの場合は"true"または"false"を返します。
関数
- opsstring-array
- 実行される順序での操作
- argsinteger-array
- push ごとの値、それ以外のすべての操作では 0
- 戻り値string-array
- 各操作につき1つの回答（テキストとして）
制約
1 ≤ ops.length ≤ 2000args.length == ops.length- 各
ops[i]は、push、pop、peekまたはemptyです。 -109 ≤ args[i] ≤ 109はpushの場合、またその他の操作ではargs[i] == 0です。popとpeekは、キューに少なくとも 1 つの項目がある場合にのみ呼び出されます。
例
- 入力
- ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
- 出力
- ["null", "null", "1", "1", "false"]
- 説明
- 1をプッシュし、その後2をプッシュすると、先頭は1なので、
peekとpopはどちらも"1"を返します。2はまだ中にあるため、emptyは"false"を返します。
- 入力
- ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
- 出力
- ["null", "null", "4", "null", "7", "9", "true"]
- 説明
- 最初のポップで、最も古い項目である4が取り出されます。7がまだ待っている間に9が入り、7の後に入ったため、7の後に取り出されます。その後キューは空になるので、最後の答えは
"true"です。
- 入力
- ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
- 出力
- ["true", "null", "-3", "-3", "true"]
- 説明
- キューは空の状態から始まるので、最初の答えは
"true"です。負の数もほかの数と同じように格納されます。peek と pop はどちらも"-3"を返し、その後キューは再び空になります。
提出時に隠しテスト+15件
発展問題
他の操作の償却計算量を崩さずに、最新の項目を O(1) で返す back 操作をどのように追加しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
スタックは項目を新しいものから順に取り出し、キューは古いものから順に取り出します。あるスタックからすべての項目をポップして別のスタックにプッシュすると、順序はどうなりますか？
一方のスタックにもう一方を注ぎ移すと順序が逆になるため、最も古い要素が一番上にきます。それぞれのスタックに役割を持たせましょう。一方は新しい要素のプッシュを受け付け、もう一方はポップやピークに使います。
popスタックが空の場合にのみ、pushスタックからpopスタックへ移します。それより早く移すと、そこで待っている古い項目が新しい項目の下に埋もれてしまいます。これにより、各項目の移動は最大1回になります。
解説
スタックは、追加された順序とは逆の順序で項目を取り出し、キューは同じ順序で取り出します。スタックの内容を別のスタックに移すと、もう一度順序が逆になり、スタックの順序がキューの順序になります。問題はいつ移すかです。操作のたびに移すと毎回 O(n) のコストがかかりますが、2つ目のスタックが空になったときだけ移せば、各項目を移動させるのは一度だけです。
プッシュのたびにスタック全体を並べ替える
考え方
すべての項目を1つのスタックmainに入れ、最も古い項目が一番上になるように並べます。そうすれば、pop、peek、emptyはそれぞれ単一のスタック操作になります。
手間がかかるのはpushです。新しい項目は、すでに待機しているすべての項目の下、つまり一番下に置く必要がありますが、スタックに追加できるのは一番上だけです。そこで、mainのすべての項目を2つ目のスタックhelperに移し、空になったmainに新しい項目をプッシュしてから、すべてを元に戻します。移動のたびに順序が逆になり、2回の移動で元の順序に戻るため、新しい項目は一番下に配置されます。
これは正しい方法ですが、プッシュするたびに保存済みのすべての項目に2回触れることになります。1,000個の項目を続けてプッシュすると、約2 × (0 + 1 + ... + 999)回、つまりほぼ100万回の移動が必要になります。一方、本物のキューなら1,000ステップで済みます。
アルゴリズム
- 2つのスタックを用意します。
mainには最も古い項目を上に置き、helperは空にしておきます。 push xの場合：mainからすべての項目をhelperに移し、xをmainにプッシュしてから、helperからすべての項目をmainに戻します。popとpeekの場合：mainの先頭を取り出すか、読み取ります。emptyの場合：mainが空かどうかを返します。- 各答えをテキストとして記録し、リストを返します。
class TwoStackQueue:
def __init__(self):
self.main = [] # the oldest item is on top
self.helper = []
def push(self, x):
# Move everything aside, put x at the bottom, move everything back.
while self.main:
self.helper.append(self.main.pop())
self.main.append(x)
while self.helper:
self.main.append(self.helper.pop())
def pop(self):
return self.main.pop()
def peek(self):
return self.main[-1]
def empty(self):
return not self.main
def queueOps(ops, args):
queue = TwoStackQueue()
result = []
for op, arg in zip(ops, args):
if op == "push":
queue.push(arg)
result.append("null")
elif op == "pop":
result.append(str(queue.pop()))
elif op == "peek":
result.append(str(queue.peek()))
else:
result.append("true" if queue.empty() else "false")
return result遅延転送を使用した受信箱と送信箱のスタック
考え方
スタックに別々の役割を持たせます。プッシュはすべて O(1) でinboxに追加します。ポップとピークではoutboxから読み取ります。outboxの先頭には、キュー内で最も古い項目が常にあります。
outboxが空のときにポップまたはピークが要求されたら、inboxの内容をすべて移します。最も新しい項目が最初にinboxから取り出されるため、outboxの底に置かれ、最も古い項目が先頭に置かれます。移すのはoutboxが空のときだけです。項目が残っている間、それらはinbox内のどの項目よりも古いため、先に取り出す必要があります。2つ目の例では、最初のポップの前に 4 と 7 が移されます。その後、7 が取り出されるまで 9 はinboxで待ちます。
1回のポップで多くの項目を移動することがありますが、項目ごとに処理を数えます。各値はinboxに1回プッシュされ、outboxに1回移され、1回ポップされます。したがって、n 回の操作にかかる合計時間は O(n) であり、操作あたりの償却時間は O(1) です。両方のスタックが空のとき、キューは空です。
アルゴリズム
- 空のスタック
inboxとoutboxを用意します。 push xの場合:xをinboxにプッシュします。popまたはpeekの場合:outboxが空なら、inboxのすべての要素をoutboxに移します。その後、outboxの先頭を取り出すか読み取ります。emptyの場合: 両方のスタックが空かどうかを返します。- 各回答をテキストとして記録し、リストを返します。
class TwoStackQueue:
def __init__(self):
self.inbox = [] # new items go on top
self.outbox = [] # the oldest item is on top
def push(self, x):
self.inbox.append(x)
def _refill(self):
# Only when the outbox is empty: pouring the inbox over reverses it,
# so the oldest item lands on top.
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._refill()
return self.outbox.pop()
def peek(self):
self._refill()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
def queueOps(ops, args):
queue = TwoStackQueue()
result = []
for op, arg in zip(ops, args):
if op == "push":
queue.push(arg)
result.append("null")
elif op == "pop":
result.append(str(queue.pop()))
elif op == "peek":
result.append(str(queue.peek()))
else:
result.append("true" if queue.empty() else "false")
return result
落とし穴と境界ケース
ほとんどのバグは、誤ったタイミングで移し替えること、または片方のスタックしか確認しないことが原因です。
outboxに項目が残っている間に、inboxをoutboxに移し替えること。新しい項目が古い項目の上に積まれ、先に取り出されるため、キューの順序が崩れます。2つ目の例では、7より先に9が取り出されます。outboxだけを見てemptyと報告すること。pushの直後は新しい項目がinboxにあるため、outboxが空でもキューは空ではありません。peekにもpopと同じ補充が必要だということを忘れること。最初のpushの直後にpeekすると、outboxは空です。- ライブラリのキューを使ったり、インデックスでスタックの底を読んだりすること。目的は、スタック操作だけでキューの順序を実現することです。
- テキストではなく数値やブール値を返すこと。pushに対する
"null"も含め、すべての答えは文字列です。
よくある質問4
2つのスタックから構成されたキューの時間計算量は何ですか？
Push は O(1) です。Pop と peek は償却 O(1) です。1回の呼び出しで、すべての項目が一方のスタックからもう一方へ移動することがありますが、各項目が移動するのはその生涯で最大1回なので、n 回の操作にかかる合計時間は O(n) です。2つのスタックを合わせると各項目を1回ずつ保持するため、空間計算量は O(n) です。
ここで償却 O(1) とはどういう意味ですか？
これは、単一の操作に時間がかかることがあっても、シーケンス全体での操作あたりの平均コストは一定であることを意味します。1,000 個の要素を注ぎ出す pop のコストは、その前に行われた 1,000 回の安価な push によってまかなわれます。これらの要素が再び注ぎ出されることはないからです。n 回の操作からなるシーケンスのコストが、およそ 4n 回のスタック操作を超えることはありません。
スタックが1つではなく2つ必要なのはなぜですか？
スタックは最新の項目だけを取り出せますが、キューでは最も古い項目が必要です。スタックの底にある項目にたどり着くには、その上にあるすべての項目を取り除く必要があり、それらの項目を待機させておく場所が必要です。それが2つ目のスタックです。項目を移動すると順序が逆になり、この逆転によって「最新のものが先」から「最も古いものが先」へと変わります。
代わりにキューを使ってスタックを実装できますか？
はい。ただし、一般的な方法では償却計算量の節約はできません。よく使われる方法の1つはキューを1つ使います。新しい項目を追加した後、古い項目を前から1つずつ取り出して後ろに追加することで、新しい項目が先頭に来るようにします。この方法では、push の計算量は O(n)、pop の計算量は O(1) になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def queueOps(ops, args):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
ops = ["push", "push", "peek", "pop", "empty"] args = [1, 2, 0, 0, 0]
期待値
["null", "null", "1", "1", "false"]