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

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

Câu trả lời

Một ngăn xếp có thể được triển khai bằng 2 hai hàng đợi. Một hàng đợi hỗ trợ các thao tác là enqueue và dequeue. Ta sẽ dùng chúng để tạo các thao tác push, pop.

Đầu tiên ta có hai hàng đợi là q1q2. Ngăn xếp được triển khai bởi hàng đợi theo hai cách.

  1. Tốn chi phí cho push:

Phương thức này đảm bảo các phần tử mới được thêm vào sẽ luôn ở đằng trước của q1, thế nên thao tác pop sẽ là deque từ q1.

q2 được dùng như một hàng đợi phụ trợ để phần tử mới vào trước q1 trong khi đảm bảo pop xảy ra ở độ phức tạp O(1).

Mã giả:

  • Push phần tử vào ngăn xếp: Độ phức tạp thời gian là O(n).
push(s, data):
    Enqueue data to q2
    Dequeue elements one by one from q1 and enqueue to q2.
    Swap the names of q1 and q2
  • Pop phần tử khỏi ngăn xếp: Độ phức tạp thời gian là O(...
entry

entry

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

entry

Khái niệm Tree Data Structure là gì?

entry

Heap là gì?

junior

Dynamic Arrays là gì?

Bình luận

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

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