Sử dụng hai queue: q1 và q2. Push: enqueue vào q1, sau đó chuyển tất cả từ q2 sang q1, rồi swap q1,q2. Pop: dequeue từ q2. Đảm bảo q2 luôn chứa phần tử mới nhất ở đầu.
Ví dụ
class Queue_structure:
def __init__(self):
self.items = []
self.size = 0
def is_empty(self):
return self.items == []
def enqueue(self, data):
self.size += 1
self.items.append(data)
def dequeue(self):
self.size -= 1
return self.items.pop(0)
def get_size(self):
return self.size
class Stack_structure:
def __init__(self):
self.q1 = Queue_structure()
self.q2 = Queue_structure()
def is_empty(self):
return self.q2.is_empty()
def push(self, data):
self.q1.enqueue(data)
while not self.q2.is_empty():
self.q1.enqueue(self.q2.dequeue())
self.q1, self.q2 = self.q2, self.q1
def pop(self):
return self.q2.dequeue()
s = Stack_structure()
print("Menu: push | pop | quit")
while True:
inp = input("Thao tác: ").split()
op = inp[0].lower()
if op == 'push':
s.push(int(inp[1]))
elif op == 'pop':
if s.is_empty():
print("Ngăn xếp rỗng")
else:
print("Phần tử lấy ra:", s.pop())
elif op == 'quit':
break
Kết quả
Menu: push| pop | quit Thao tác: push 56 Thao tác: push 34 Thao tác: push 78 Thao tác: push 90 Thao tác: pop Phần tử lấy ra: 90 Thao tác: quit
Giải thích
- Push: O(n) do phải chuyển toàn bộ q2 sang q1.
- Pop: O(1).
- Sau push, q2 chứa các phần tử theo thứ tự LIFO.