检查是否可以使用Python中的堆栈将一个队列分类到另一个队列中

假设我们有一个前n个自然数（未排序）的队列。我们必须检查给定的Queue元素是否可以通过使用堆栈按另一个队列中的降序排列。我们可以使用以下操作来解决这个问题-

• 从堆栈中推送或弹出元素

• 从给定队列中删除元素。

• 在另一个队列中插入元素。

因此，如果输入类似于Que = [6，1，2，3，4，5]，则输出为True，因为我们可以从Que中弹出6，然后将其压入堆栈。现在，将所有剩余元素从Que弹出到另一个队列，然后从堆栈中弹出6并压入第二个队列，因此新队列中的所有元素将以不降序排列。

为了解决这个问题，我们将遵循以下步骤-

• n：=大小

• stk：=一个新堆栈

• exp_val：= 1

• 前：= null

• 当que不为空时，执行

• 从stk弹出

• exp_val：= exp_val + 1

• 如果stk为空，则

• 否则，当stk不为空且stk的顶部<前面时，则

• 除此以外，

• 推入stk

• 返回False

• 推入stk

• exp_val：= exp_val + 1

• front：= que的前元素

• 从队列中删除前元素

• 如果front与exp_val相同，则

• 除此以外，

• 当stk不为空并且栈顶与exp_val相同时，执行

• 如果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