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
    else
        Pop an item from stack1 and return it

2. Cần nhiều chi phí cho dequeue

Ở đây, đối với thao tác enqueue, phần tử mới được đẩy lên trên cùng của stack1.Thế nên, độ phức tạp thời gian hoạt động của enqueue là O(1).

Với dequeue, nếu stack2 trống, tất cả các phần tử từ stack1 sẽ được chuyển đến stack2 và pop phần tử trên cùng của stack2 để lấy kết quả. Về cơ bản, đảo ngược danh sách bằng cách đẩy vào một ngăn xếp và trả về phần tử được enqueue đầu tiên. Thao tác đẩy tất cả các phần tử vào ngăn xếp mới có độ phức tạp O(n).

Mã giả:

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

enqueue(q, data):
    Push data to stack1

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

dequeue(q):
    If both stacks are empty then raise error.
    If stack2 is empty:
        While stack1 is not empty:
            push everything from stack1 to stack2.
    Pop the element from stack2 and return it.