使用 Python 檢查一個佇列是否可以透過棧排序成另一個佇列

假設我們有一個佇列，其中包含前 n 個自然數（未排序）。我們必須檢查給定的佇列元素是否可以透過使用棧在另一個佇列中按非遞減順序排序。我們可以使用以下操作來解決此問題：

  • 將元素壓入或彈出棧
  • 從給定佇列中刪除元素。
  • 將元素插入另一個佇列。

因此，如果輸入類似 Que = [6, 1, 2, 3, 4, 5]，則輸出將為 True，因為我們可以從 Que 中彈出 6，然後將其壓入棧中。現在從 Que 中彈出所有剩餘元素到另一個佇列，然後從棧中彈出 6 並將其壓入第二個佇列，因此新佇列中的所有元素都將按非遞減順序排序。

為了解決這個問題，我們將遵循以下步驟：

  • n := 佇列的大小
  • stk := 一個新的棧
  • exp_val := 1
  • front := null
  • 當佇列不為空時，執行以下操作
    • front := 佇列的第一個元素
    • 從佇列中刪除第一個元素
    • 如果 front 等於 exp_val，則
      • exp_val := exp_val + 1
    • 否則，
      • 如果 stk 為空，則
        • 將 front 壓入 stk
      • 否則，當 stk 不為空且棧頂 < front 時，則
        • 返回 False
      • 否則，
        • 將 front 壓入 stk
    • 當 stk 不為空且棧頂等於 exp_val 時，執行以下操作
      • 從 stk 中彈出
      • exp_val := exp_val + 1
  • 如果 exp_val - 1 等於 n 且 stk 為空，則
    • 返回 True
  • 返回 False

讓我們看看以下實現以獲得更好的理解：

示例

 即時演示

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

更新於： 2020-12-29

236 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

開始
廣告