Chương trình Python triển khai ngăn xếp (stack) sử dụng danh sách liên kết

Khi cần triển khai cấu trúc dữ liệu ngăn xếp (stack) sử dụng danh sách liên kết, phương thức thêm (push) phần tử vào danh sách liên kết và phương thức xóa (pop) phần tử của danh sách liên kết được định nghĩa.

Ví dụ

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack_structure:
    def __init__(self):
        self.head = None
    
    def push_val(self, data):
        if self.head is None:
            self.head = Node(data)
        else:
            newNode = Node(data)
            newNode.next = self.head
            self.head = newNode
    
    def pop_val(self):
        if self.head is None:
            return None
        else:
            del_Val = self.head.data
            self.head = self.head.next
            return del_Val

my_instance = Stack_structure()
while True:
    print('push ')
    print('pop')
    print('quit')
    my_input = input('Hành động bạn muốn thực hiện? ').split()
    operation = my_input[0].strip().lower()
    if operation == 'push':
        my_instance.push_val(int(my_input[1]))
    elif operation == 'pop':
        del_Val = my_instance.pop_val()
        if del_Val is None:
            print('Ngăn xếp rỗng.')
        else:
            print('Giá trị bị xóa là: ', int(del_Val))
    elif operation == 'quit':
        break

Kết quả

push 
pop
quit
Hành động bạn muốn thực hiện? push 56
push 
pop
quit
Hành động bạn muốn thực hiện? push 78
push 
pop
quit
Hành động bạn muốn thực hiện? push 90
push 
pop
quit
Hành động bạn muốn thực hiện? pop
Giá trị bị xóa là: 90
push 
pop
quit
Hành động bạn muốn thực hiện? quit

Giải thích

• Lớp Node được tạo.
• Lớp Stack_structure với các thuộc tính cần thiết được tạo.
• Phương thức __init__ khởi tạo phần tử đầu tiên (head) là None.
• Phương thức push_val giúp thêm giá trị vào ngăn xếp.
• Phương thức pop_val giúp xóa giá trị từ đỉnh ngăn xếp và trả về giá trị bị xóa.
• Một instance của Stack_structure được tạo.
• Ba tùy chọn được đưa ra: push, pop và quit.
• Tùy chọn push thêm một giá trị cụ thể vào ngăn xếp.
• Tùy chọn pop xóa phần tử đỉnh khỏi ngăn xếp.
• Tùy chọn quit thoát khỏi vòng lặp.
• Dựa trên lựa chọn/đầu vào của người dùng, các thao tác tương ứng được thực hiện.
• Kết quả được hiển thị trên console.