Triển khai hàng đợi bằng ngăn xếp

Một hàng đợi có thể triển khai bằng cách dùng hai ngăn xếp.

Cho hàng đợi q và hai ngăn xếp stack1 và stack2 để triển khai q. Ta biết ngăn xếp hỗ trợ các thao tác push, pop và peek, ta sẽ dùng các thao tác đó để mô phỏng các hoạt động của hàng đợi, enqueue và dequeue. Do đó, hàng đợi q có thể triển khai theo hai cách (cả hai cách đều có độ phức tạp không gian là O(n)):

1. Cần nhiều chi phí chi enqueue

Ở đây, phần tử cũ nhất luôn ở trên cùng của stack1 đảm bảo hoạt động dequeue xảy ra với độ phức tạp thời gian O (1).

Để đặt phần tử vào đầu stack1, stack2 được sử dụng.

Mã giả:

• Enqueue: Độ phức tạp thời gian là O(n):

enqueue(q, data):
    While stack1 is not empty:
        Push everything from stack1 to stack2.
        Push data to stack1
        Push everything back to stack1.

• Dequeue: Độ phức tạp thời gian là O(1):

dequeue(q):
    If stack1 is empty then error
    e...