Đảo ngược Stack (Ngăn xếp) bằng đệ quy trong Python

Đệ quy: pop tất cả phần tử cho đến khi stack rỗng, sau đó chèn từng phần tử vào đáy stack (hàm insert_bottom).

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()
    def print_stack(self):
        for item in reversed(self.items):
            print(item)

def insert_bottom(st, data):
    if st.is_empty():
        st.push(data)
    else:
        temp = st.pop()
        insert_bottom(st, data)
        st.push(temp)

def reverse_stack(st):
    if not st.is_empty():
        temp = st.pop()
        reverse_stack(st)
        insert_bottom(st, temp)

st = Stack_structure()
vals = input("Nhập các số cách nhau bởi dấu cách: ").split()
for v in vals:
    st.push(int(v))
print("Stack ban đầu (top->bottom):")
st.print_stack()
reverse_stack(st)
print("Stack sau đảo ngược:")
st.print_stack()

Kết quả

Nhập các số cách nhau bởi dấu cách: 23 56 73 81 8 9 0
Stack ban đầu (top->bottom):
0
9
8
81
73
56
23
Stack sau đảo ngược:
23
56
73
81
8
9
0

Giải thích

• insert_bottom: đệ quy pop đến khi rỗng, push data, sau đó push lại các phần tử đã pop -> data nằm ở đáy.
• reverse_stack: pop top, đệ quy đảo ngược phần còn lại, chèn top cũ vào đáy.
• Độ phức tạp O(n^2) do insert_bottom O(n) gọi n lần.