Làm thế nào để chuyển đổi một Queue thành Stack?
Làm thế nào để chuyển đổi một Queue thành Stack?
Có thể cài đặt Stack (LIFO) chỉ bằng Queue (FIFO) theo hai cách: dùng một queue và sau mỗi lần push thì xoay các phần tử cũ ra sau (push O(n), pop O(1)), hoặc dùng hai queue và dồn phần tử khi pop (push O(1), pop O(n)).
Vấn đề cốt lõi: queue chỉ cho lấy phần tử vào sớm nhất, còn stack cần lấy phần tử vào muộn nhất. Vì vậy phải sắp xếp lại thứ tự bên trong queue sao cho phần tử mới nhất luôn nằm ở đầu hàng, hoặc phải "đẩy qua" các phần tử cũ mỗi khi cần lấy phần tử mới nhất.
Cách 1: một queue, push tốn O(n). Sau khi thêm x vào cuối, lấy lần lượt n - 1 phần tử phía trước ra và thêm lại vào cuối. Khi đó x được xoay lên đầu queue.
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return not self.q
Ví dụ: push 1, push 2 thì queue là [2, 1]; push 3 thì sau khi xoay thành [3, 2, 1]. pop() trả về 3, đúng thứ tự LIFO.
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.