Pythonでスタックを使ってキューを別のキューに昇順ソートできるか判定する方法

最初のn個の自然数(未ソート)が格納されたキューがあるとします。スタックを1つ使用して、与えられたキューの要素を別のキューへ非減少順(昇順)に並べ替えることができるかどうかを判定する問題です。

この問題を解くために使用できる操作は次のとおりです。

• スタックへの要素のプッシュ(push)またはポップ(pop)
• 元のキューから要素を削除する
• 別のキューへ要素を挿入する

動作例

たとえば、入力が Que = [6, 1, 2, 3, 4, 5] の場合、出力は True になります。手順は以下のとおりです。

1. Queから先頭の「6」を取り出し、スタックにプッシュします。
2. 残りの要素「1, 2, 3, 4, 5」をQueから別のキューへ順番に移動します。
3. 最後にスタックから「6」をポップし、2番目のキューの末尾に追加します。

これにより、新しいキューには「1, 2, 3, 4, 5, 6」が入り、非減少順にソートされた状態になります。

アルゴリズムの手順

この問題は、次の手順で解決できます。

• n := キューのサイズ
• stk := 新しいスタック
• exp_val := 1(次に期待する値)
• front := null
• キューが空でない間、以下を繰り返します。
  • front := キューの先頭要素を取得し、キューから削除
  • front が exp_val と等しい場合:
    • exp_val := exp_val + 1
  • それ以外の場合:
    • スタックが空なら、front をスタックにプッシュ
    • スタックが空でなく、スタックのトップが front より小さい場合は False を返す(昇順にできないため)
    • それ以外は front をスタックにプッシュ
  • スタックが空でなく、スタックのトップが exp_val と等しい間、以下を繰り返します。
    • スタックからポップし、exp_val := exp_val + 1
• ループ終了後、exp_val - 1 が n と等しく、かつスタックが空なら True を返します。
• それ以外は False を返します。

実装例(Python)

from queue import Queue
def solve(que):
    n = que.qsize()
    stk = []
    exp_val = 1
    front = None
    while (not que.empty()):
        front = que.queue[0]
        que.get()
        if (front == exp_val):
            exp_val += 1
        else:
            if (len(stk) == 0):
                stk.append(front)
            elif (len(stk) != 0 and stk[-1] < front):
                return False
            else:
                stk.append(front)
    while (len(stk) != 0 and stk[-1] == exp_val):
        stk.pop()
        exp_val += 1
    if (exp_val - 1 == n and len(stk) == 0):
        return True
    return False
que = Queue()
items = [6, 1, 2, 3, 4, 5]
for i in items:
    que.put(i)
print(solve(que))

入力

[6, 1, 2, 3, 4, 5]

出力

True

ポイントまとめ

このアルゴリズムの計算量は O(n)、空間計算量も O(n) です。重要なのは、スタックのトップより大きい値を後からプッシュしようとした時点で昇順ソートが不可能になるという点です。これは、スタックがLIFO(後入れ先出し)構造であるため、大きな値が小さな値の上に積まれると、小さな値を先に出力できなくなるからです。したがって、そのような状況を検出したら即座に False を返すことで効率的に判定できます。