Dùng một queue. Push: enqueue vào queue. Pop: dequeue n-1 phần tử và enqueue lại, phần tử cuối cùng (đã được đẩy về cuối) là phần tử top -> dequeue và trả về.
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.q = Queue_structure()
def is_empty(self):
return self.q.is_empty()
def push(self, data):
self.q.enqueue(data)
def pop(self):
for _ in range(self.q.get_size() - 1):
self.q.enqueue(self.q.dequeue())
return self.q.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 89 Thao tác: push 43 Thao tác: push 76 Thao tác: push 56 Thao tác: pop Phần tử lấy ra: 56 Thao tác: quit
Giải thích
- Push: O(1).
- Pop: O(n) do phải xoay vòng n-1 lần.
- Queue đơn giản dùng list Python (pop(0) O(n) -> tổng O(n^2), nhưng để demo thuật toán).