Theo em, có thể dùng danh sách liên kết để biểu diễn hàng đợi hay không?

Có, bạn có thể sử dụng danh sách liên kết để biểu diễn hàng đợi. Danh sách liên kết là một cấu trúc dữ liệu linh hoạt và phù hợp để triển khai hàng đợi.

Trong danh sách liên kết, mỗi phần tử trong hàng đợi được biểu diễn bởi một nút (node), và mỗi nút sẽ chứa hai thông tin chính là giá trị của phần tử và một con trỏ (hoặc tham chiếu) đến phần tử tiếp theo trong hàng đợi.

Ưu điểm của sử dụng danh sách liên kết để biểu diễn hàng đợi là:

• Không có giới hạn về kích thước của hàng đợi, vì bạn có thể cấp phát bộ nhớ động cho từng nút.

• Thêm và xóa phần tử ở đầu (enqueue và dequeue) có thể thực hiện nhanh chóng với độ phức tạp thời gian là O(1).

Dưới đây là một ví dụ về cách triển khai hàng đợi sử dụng danh sách liên kết đơn trong Python:

class Node:

    def __init__(self, data):

       self.data = data

       self.next = None

class Queue:

    def __init__(self):

       self.front = None  # Nút đầu hàng đợi

       self.rear = None   # Nút cuối hàng đợi

    def is_empty(self):

        return self.front is None

    def enqueue(self, item):

        new_node = Node(item)

        if self.is_empty():

           self.front = new_node

           self.rear = new_node

        else:

           self.rear.next = new_node

           self.rear = new_node

    def dequeue(self):

        if self.is_empty():

           raise Exception("Queue is empty")

        else:

           removed_item = self.front.data

           self.front = self.front.next

            if self.front is None:

               self.rear = None

           return removed_item

    def display(self):

        current = self.front

        while current:

           print(current.data, end=" ")

           current = current.next

        print()

# Sử dụng hàng đợi danh sách liên kết

queue = Queue()

queue.enqueue("Một")

queue.enqueue("Hai")

queue.enqueue("Ba")

queue.enqueue("Bốn")

print("Hàng đợi sau khi enqueue các phần tử:")

queue.display()

removed_item = queue.dequeue()

print(f"Phần tử đã dequeue: {removed_item}")

print("Hàng đợi sau khi dequeue một phần tử:")

queue.display()

Kết quả của đoạn mã trên sẽ là:

Hàng đợi sau khi enqueue các phần tử:

Một Hai Ba Bốn 

Phần tử đã dequeue: Một

Hàng đợi sau khi dequeue một phần tử:

Hai Ba Bốn 

Trong mã trên:

• Lớp Node đại diện cho mỗi nút trong danh sách liên kết, lưu trữ giá trị (data) và con trỏ đến nút tiếp theo (next).

• Lớp Queue triển khai hàng đợi sử dụng danh sách liên kết đơn.

• Phương thức enqueue(item) thêm một phần tử vào cuối hàng đợi.

• Phương thức dequeue() lấy ra và trả về phần tử ở đầu hàng đợi.

• Phương thức display() hiển thị tất cả các phần tử trong hàng đợi từ đầu đến cuối.