Giả sử chúng ta có một hàng đợi (Queue) chứa n số tự nhiên đầu tiên (chưa sắp xếp). Cần kiểm tra xem các phần tử của hàng đợi đã cho có thể được sắp xếp theo thứ tự không giảm vào một hàng đợi khác bằng cách sử dụng một ngăn xếp (stack). Các phép toán cho phép: push/pop từ stack, dequeue từ hàng đợi ban đầu, enqueue vào hàng đợi mới.
Ví dụ, Que = [6, 1, 2, 3, 4, 5], đầu ra True vì: pop 6 -> push stack, pop 1,2,3,4,5 -> hàng đợi mới, pop 6 từ stack -> hàng đợi mới. Kết quả [1,2,3,4,5,6].
Các bước giải quyết:
- n := kích thước que.
- stk := ngăn xếp rỗng.
- exp_val := 1 (giá trị mong đợi tiếp theo).
- front := None.
- Trong khi que không rỗng:
- front := phần tử đầu que, dequeue.
- Nếu front == exp_val: exp_val += 1.
- Ngược lại:
- Nếu stk rỗng: push front vào stk.
- Ngược lại nếu đỉnh stk < front: trả về False (vi phạm thứ tự stack).
- Ngược lại: push front vào stk.
- Trong khi stk không rỗng và đỉnh stk == exp_val: pop stk, exp_val += 1.
- Nếu exp_val - 1 == n và stk rỗng, trả về True, ngược lại False.
Xem ví dụ dưới đây để hiểu rõ hơn:
Ví dụ
from queue import Queue
def solve(que):
n = que.qsize()
stk = []
exp_val = 1
while not que.empty():
front = que.queue[0]
que.get()
if front == exp_val:
exp_val += 1
else:
if not stk:
stk.append(front)
elif stk[-1] < front:
return False
else:
stk.append(front)
while stk and stk[-1] == exp_val:
stk.pop()
exp_val += 1
if exp_val - 1 == n and not stk:
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