Sử dụng hai stack (in_stack để enqueue, out_stack để dequeue). Khi dequeue mà out_stack rỗng, chuyển tất cả phần tử từ in_stack sang out_stack (đảo ngược thứ tự -> FIFO).
Ví dụ
class Stack_structure:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, data):
self.items.append(data)
def pop(self):
return self.items.pop()
class Queue_structure:
def __init__(self):
self.in_stack = Stack_structure()
self.out_stack = Stack_structure()
def is_empty(self):
return self.in_stack.is_empty() and self.out_stack.is_empty()
def enqueue(self, data):
self.in_stack.push(data)
def dequeue(self):
if self.out_stack.is_empty():
while not self.in_stack.is_empty():
self.out_stack.push(self.in_stack.pop())
return self.out_stack.pop()
q = Queue_structure()
while True:
print("enqueue | dequeue | quit")
inp = input("Thao tác: ").split()
op = inp[0].lower()
if op == 'enqueue':
q.enqueue(int(inp[1]))
elif op == 'dequeue':
if q.is_empty():
print("Hàng đợi rỗng")
else:
print("Phần tử lấy ra:", q.dequeue())
elif op == 'quit':
break
Kết quả
enqueue| dequeue | quit Thao tác: enqueue 45 Thao tác: enqueue 23 Thao tác: enqueue 78 Thao tác: dequeue Phần tử lấy ra: 45 Thao tác: quit
Giải thích
- Enqueue: push vào in_stack (O(1)).
- Dequeue: nếu out_stack rỗng, pop tất cả từ in_stack push vào out_stack (đảo ngược), sau đó pop từ out_stack (O(1) amortized).