0Pricing
DSA Interview Prep · レッスン

スタックとキューの相互シミュレーション

2つのスタックでキューを、2つのキューでスタックを実装し、それぞれの方法の償却コストを説明します。

「スタックとキューの相互シミュレーション」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。

一方をもう一方で再現する理由

2つのスタックでキューを実装することと、2つのキューでスタックを実装することは、設計に関する面接でよく出る問題です。これらは、両方のデータ構造の不変条件を理解しているか、また一方の構造の保証をもう一方の基本操作で維持できるかを確認します。面接では、償却計算量について話すきっかけとしても使われます。

重要なポイントは、スタックがLIFOでキューがFIFOだということです。両者を変換するには順序を反転する必要があります。スタックを別のスタックに移すと元の挿入順序になるため、FIFOを実現できます。

2つのスタックでキューを実装（遅延方式）

遅延方式では、プッシュ用にinboxスタック、ポップ用にoutboxスタックを使います。dequeueが呼び出されたとき、outboxが空なら、inboxのすべての要素をoutboxへ移します。この反転によってFIFOの順序が復元されます。outboxが空でなければ、そこから直接ポップします。転送は必要になったときだけ行うため、O(n)の転送コストを複数の操作にわたって償却できます。

class MyQueue:
    def __init__(self):
        self.inbox  = []
        self.outbox = []

    def push(self, x):
        self.inbox.append(x)

    def _transfer(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._transfer()
        return self.outbox.pop()

    def peek(self):
        self._transfer()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek())  # 1
print(q.pop())   # 1
print(q.pop())   # 2
q.push(4)
print(q.pop())   # 3

スタックからキューを作る場合の償却O(1)解析

各要素はinboxからoutboxへ高々1回しか移されません。outboxからのポップがO(1)で、outboxが空のときだけ転送が行われる場合、n回のプッシュとn回のポップにかかる総作業量は最大2n回のスタック操作です。したがって、全体ではO(n)、1操作あたりの償却計算量はO(1)です。個々の操作は最悪の場合O(n)になることがありますが、平均ではO(1)になります。

# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
    def __init__(self):
        self.inbox = []; self.outbox = []; self.transfers = 0

    def push(self, x): self.inbox.append(x)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.transfers += 1
        return self.outbox.pop()

q = TrackedQueue()
for i in range(5):
    q.push(i)
for _ in range(5):
    q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers)  # at most n

2つのキューでスタックを実装（遅延ポップ）

キューはFIFOであるため、2つのキューでスタックを実装するのは自然ではありません。遅延ポップ方式では、メインキューを1つと一時キューを1つ用意します。pushではメインキューにエンキューします（O(1)）。popまたはpeekでは、最後の要素以外をすべて一時キューへデキューし、最後の要素を保存してからキューを交換します。これはポップ1回あたりO(n)ですが、プッシュ1回あたりはO(1)です。

from collections import deque

class MyStack:
    def __init__(self):
        self.main = deque()
        self.temp = deque()

    def push(self, x):
        self.main.append(x)   # O(1)

    def pop(self):
        # Move all but last element to temp
        while len(self.main) > 1:
            self.temp.append(self.main.popleft())
        val = self.main.popleft()   # the 'top'
        self.main, self.temp = self.temp, self.main  # swap
        return val

    def top(self):
        while len(self.main) > 1:
            self.temp.append(self.main.popleft())
        val = self.main[0]
        self.temp.append(self.main.popleft())
        self.main, self.temp = self.temp, self.main
        return val

    def empty(self):
        return len(self.main) == 0

s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.pop())  # 2

1つのキューでスタックを実装（プッシュ時に回転）

1つのキューを使う洗練された実装では、pushで新しい要素をエンキューし、その後キューを回転させて新しい要素を先頭に移します。回転とは、プッシュ前から存在していたすべての要素をデキューして再びエンキューすることです。これにより、popとpeekはO(1)になります（先頭をデキューまたはpeekするだけです）。一方、pushはO(n)で、2つのキューを使う実装とは逆のトレードオフになります。

from collections import deque

class MyStackOneQueue:
    def __init__(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        # Rotate: move all preceding elements behind x
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return len(self.q) == 0

s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.top())  # 2

トレードオフのまとめ：どの実装を選ぶか

2つのスタックからキューを作る場合：pushはO(1)、pop/peekは償却O(1)です。ポップ操作が頻繁な場合に適しています。2つのキューからスタックを作る場合：pushはO(1)、popはO(n)です。ポップよりもプッシュの方がはるかに多い場合に適しています。1つのキューからスタックを作る場合：pushはO(n)、popはO(1)です。ポップが中心となる場合に適しています。面接では、このトレードオフを明確に説明し、「動けばよい」だけでなく、その先まで考えていることを示してください。

print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue:  push O(n), pop O(1)')

反転するとFIFOが復元される理由

要素1、2、3をスタック（inbox）にプッシュすると、下から上に1、2、3の順で並びます。これらをすべて2つ目のスタック（outbox）へポップすると順序が反転し、outboxでは下から3、2、1の順になります。outboxからポップすると1、2、3の順に取り出され、FIFOの挿入順序と完全に一致します。これが、ちょうど2回の反転（2つのスタック）でFIFOが復元され、1つのスタックだけではLIFOになる理由です。

# Demonstrate double-reversal = FIFO
inbox  = [1, 2, 3]   # pushed in this order
outbox = []
while inbox:
    outbox.append(inbox.pop())
print('outbox (one reversal):', outbox)  # [3, 2, 1] top-to-bottom

# Pop from outbox gives FIFO
result = []
while outbox:
    result.append(outbox.pop())
print('dequeued:', result)  # [1, 2, 3] — FIFO!

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

LeetCode 232は、直接的な「2つのスタックからキューを作る」問題です。想定される解法は、遅延方式でのoutboxへの転送です。面接では、各要素がinboxからoutboxへ高々1回しか移動しないため、すべての操作が償却O(1)になると説明してください。個々のpop呼び出しは、outboxが空の場合に最悪O(n)になりますが、n回の操作全体で見ると平均O(1)になることも付け加えてください。

class MyQueue:
    def __init__(self):
        self.inbox  = []
        self.outbox = []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        self.peek()             # ensure outbox is populated
        return self.outbox.pop()

    def peek(self):
        if not self.outbox:
            while self.inbox:   # transfer lazily
                self.outbox.append(self.inbox.pop())
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek())  # 1
print(q.pop())   # 1
print(q.empty()) # False

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

LeetCode 225は、「キューからスタックを作る」問題です。最もすっきりした解法は、1つのキューを使ってプッシュ時に回転する方法です。要素xをプッシュした後、すでにキューにあるすべての要素をxの後ろへ移動して、キューを回転させます。これにより、プッシュ1回あたりO(n)かかりますが、topとpopはO(1)になります。このトレードオフを説明し、制約（たとえばpushが少ない、またはpopが多いワークロード）に合っていることを確認してください。

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x):       # O(n)
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):           # O(1)
        return self.q.popleft()

    def top(self):           # O(1)
        return self.q[0]

    def empty(self):
        return len(self.q) == 0

s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.top())  # 2
print(s.empty()) # False

1つの配列で3つのスタックに拡張する

関連する設計上の課題として、1つの配列を使って3つのスタックを実装する方法があります。1つの方法は、配列を3つの同じ大きさの固定領域に分割することです。より柔軟な方法では、ポインターを使って格子状に格納し、それぞれのスタックを担当領域から伸ばし、領域の境界が衝突したときにコピーします。これは動的配列の管理能力が問われる、シニアレベルの面接で出題される問題です。固定領域方式はより単純ですが、スタックの成長が均等でない場合は領域を無駄にします。

class ThreeStacks:
    def __init__(self, size):
        self.data = [0] * (3 * size)
        self.tops = [-1, -1, -1]  # relative top of each stack
        self.size = size

    def push(self, stack_num, val):
        self.tops[stack_num] += 1
        if self.tops[stack_num] >= self.size:
            raise OverflowError('stack full')
        self.data[stack_num * self.size + self.tops[stack_num]] = val

    def pop(self, stack_num):
        if self.tops[stack_num] < 0:
            raise IndexError('stack empty')
        val = self.data[stack_num * self.size + self.tops[stack_num]]
        self.tops[stack_num] -= 1
        return val

ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2))  # 10 20 30

重要ポイント：シミュレーションのパターン

相互シミュレーションの問題から学べる、より広い原則があります。十分な中間バッファーと反転処理があれば、どのデータ構造も別のデータ構造から構築できます。シミュレーションのコストは、どの操作を最適化するかによって変わります。push を常に O(1) にすることも、pop を常に O(1) にすることもできますが、両方を O(1) にするには、償却計算量または複数の補助データ構造が必要です。

面接では、必ず「どの操作の頻度が高いですか？」と尋ねてください。この質問によって実装方式の選択方針が決まり、操作要件についてシニアレベルの思考ができることも示せます。

理解度チェック

このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、2つのスタックからキューを作ると、inbox から outbox へ要素を遅延転送することで、pop を償却 O(1) にできること、1つのキューからスタックを作ると、push のたびにキューを回転させることで pop を O(1) にできること（push は O(n)）、そしてどの操作を O(1) にするかは利用パターンによって決まることを学びました。次は、ハッシュマップの内部構造と衝突処理について学びます。

よくある質問

「スタックとキューの相互シミュレーション」レッスンは無料ですか？

はい。「スタックとキューの相互シミュレーション」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。

「スタックとキューの相互シミュレーション」で何を学びますか？

2つのスタックでキューを、2つのキューでスタックを実装し、それぞれの方法の償却コストを説明します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

DSA Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「スタックとキューの相互シミュレーション」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このDSA Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. スタックの実装と応用
  2. キューの実装とdeque
  3. 単調スタックパターン
  4. スタックとキューの相互シミュレーション
← DSA Interview Prepに戻る