Câu hỏi phỏng vấn Data Structures
Câu hỏi

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

Câu trả lời

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 stack1stack2 để 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):
text Copy
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):
text Copy
dequeue(q):
    If stack1 is empty then error
    e...
entry

entry

Gợi ý câu hỏi phỏng vấn

senior

Đồ thị hai phía (Bipartite Graph) là gì? Làm thế nào để phát hiện một đồ thị là đồ thị hai phía?

junior

Khi nào thì Linked Lists hữu ích?

middle

Độ phức tạp của Hash Table là bao nhiêu?

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào