使用 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 次浏览

启动你的 职业生涯

通过完成课程获得认证

开始
广告