Pythonのスタックを使用して、キューを別のキューに並べ替えることができるかどうかを確認します

最初のn個の自然数（ソートされていない）を持つキューがあるとします。スタックを使用して、指定されたキュー要素を別のキューで降順ではない順序で並べ替えることができるかどうかを確認する必要があります。この問題を解決するには、次の操作を使用できます-

• スタックから要素をプッシュまたはポップします
• 指定されたキューから要素を削除します。
• 他のキューに要素を挿入します。

したがって、入力がQue =[6、1、2、3、4、5]のような場合、Queから6をポップしてスタックにプッシュできるため、出力はTrueになります。次に、残りのすべての要素をキューから別のキューにポップし、次にスタックから6をポップして、2番目のキューにプッシュします。これにより、新しいキューのすべての要素が減少しない順序で並べ替えられます。

これを解決するには、次の手順に従います-

• n：=queのサイズ
• stk：=新しいスタック
• exp_val：=1
• フロント：=null
• queが空でない間は、
  • front：=queのフロント要素
  • 前の要素をqueから削除します
  • frontがexp_valと同じ場合、
    • exp_val：=exp_val + 1
  • それ以外の場合、
    • stkが空の場合、
      • フロントをstkに押し込みます
    • それ以外の場合、stkが空でなく、stkの上部が
    • Falseを返す
  • それ以外の場合、
    • フロントをstkに押し込みます
• stkが空ではなく、スタックの最上位がexp_valと同じである場合、do
  • stkからポップ
  • exp_val：=exp_val + 1

理解を深めるために、次の実装を見てみましょう-

例

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