Kiểm tra xem một hàng đợi có thể được sắp xếp thành một hàng đợi khác hay không bằng cách sử dụng một ngăn xếp trong Python

Giả sử chúng ta có một Hàng đợi với n số tự nhiên đầu tiên (chưa được sắp xếp). Chúng ta phải kiểm tra xem các phần tử Hàng đợi đã cho có thể được sắp xếp theo trình tự không giảm trong Hàng đợi khác hay không bằng cách sử dụng một ngăn xếp. Chúng ta có thể sử dụng các thao tác sau để giải quyết vấn đề này -

• Đẩy hoặc bật các phần tử từ ngăn xếp
• Xóa phần tử khỏi Hàng đợi đã cho.
• Chèn phần tử vào Hàng đợi khác.

Vì vậy, nếu đầu vào giống như Que =[6, 1, 2, 3, 4, 5], thì đầu ra sẽ là True vì chúng ta có thể bật 6 từ Que, sau đó đẩy nó vào ngăn xếp. Bây giờ bật tất cả các phần tử còn lại từ Hàng đợi sang hàng đợi khác, sau đó bật 6 từ ngăn xếp và đẩy vào hàng đợi thứ hai, vì vậy tất cả các phần tử trong hàng đợi mới sẽ được sắp xếp theo trình tự không giảm.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của que
• stk:=một ngăn xếp mới
• exp_val:=1
• front:=null
• trong khi hàng không trống, hãy thực hiện
  • front:=phần tử phía trước của que
  • loại bỏ phần tử phía trước khỏi hàng đợi
  • nếu phía trước giống với exp_val, thì
    • exp_val:=exp_val + 1
  • nếu không,
    • nếu stk trống, thì
      • đẩy trước vào stk
    • ngược lại khi stk không trống và đầu stk
    • trả về Sai
  • nếu không,
    • đẩy trước vào stk
• trong khi stk không trống và đỉnh của ngăn xếp giống như exp_val, hãy thực hiện
  • bật ra từ stk
  • exp_val:=exp_val + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

True