Chương trình Python triển khai cấu trúc dữ liệu hàng đợi sử dụng danh sách liên kết

Khi cần triển khai cấu trúc dữ liệu hàng đợi (queue) sử dụng danh sách liên kết, phương thức thêm (enqueue) phần tử vào danh sách liên kết và phương thức xóa (dequeue) 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 Queue_structure:
    def __init__(self):
        self.head = None
        self.last = None
    
    def enqueue_operation(self, data):
        if self.last is None:
            self.head = Node(data)
            self.last = self.head
        else:
            self.last.next = Node(data)
            self.last = self.last.next
    
    def dequeue_operation(self):
        if self.head is None:
            return None
        else:
            val_returned = self.head.data
            self.head = self.head.next
            return val_returned

my_instance = Queue_structure()
while True:
    print('enqueue ')
    print('dequeue')
    print('quit')
    my_input = input('Bạn muốn thực hiện thao tác nào? ').split()
    operation = my_input[0].strip().lower()
    if operation == 'enqueue':
        my_instance.enqueue_operation(int(my_input[1]))
    elif operation == 'dequeue':
        dequeued = my_instance.dequeue_operation()
        if dequeued is None:
            print('Hàng đợi rỗng.')
        else:
            print('Phần tử bị xóa là: ', int(dequeued))
    elif operation == 'quit':
        break

Kết quả

enqueue 
dequeue
quit
Bạn muốn thực hiện thao tác nào? enqueue 45
enqueue 
dequeue
quit
Bạn muốn thực hiện thao tác nào? enqueue 12
enqueue 
dequeue
quit
Bạn muốn thực hiện thao tác nào? dequeue
Phần tử bị xóa là: 45
enqueue 
dequeue
quit
Bạn muốn thực hiện thao tác nào? quit

Giải thích

• Lớp Node được tạo.
• Lớp Queue_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 enqueue_operation giúp thêm giá trị vào hàng đợi.
• Phương thức dequeue_operation giúp xóa giá trị từ hàng đợi và trả về giá trị bị xóa.
• Một instance của Queue_structure được tạo.
• Ba tùy chọn được đưa ra: enqueue, dequeue và quit.
• Tùy chọn enqueue thêm một giá trị cụ thể vào hàng đợi.
• Tùy chọn dequeue xóa phần tử khỏi hàng đợi.
• 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.