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

Có, danh sách liên kết (linked list) có thể được sử dụng để biểu diễn hàng đợi (queue). Thực tế, việc sử dụng danh sách liên kết để biểu diễn hàng đợi mang lại nhiều lợi ích so với mảng tĩnh (array).

Lợi ích của việc sử dụng danh sách liên kết để biểu diễn hàng đợi

1. Kích thước linh hoạt: Danh sách liên kết không có giới hạn về kích thước như mảng tĩnh. Điều này có nghĩa là hàng đợi có thể mở rộng hoặc thu hẹp mà không cần phải xác định trước kích thước tối đa.

2. Thao tác nhanh: Việc thêm phần tử vào cuối danh sách (enqueue) và lấy phần tử từ đầu danh sách (dequeue) có thể được thực hiện một cách hiệu quả với độ phức tạp thời gian là O(1)O(1)O(1) nếu sử dụng danh sách liên kết đôi (doubly linked list) hoặc đơn giản (singly linked list) với con trỏ đến phần tử cuối.

Cấu trúc hàng đợi sử dụng danh sách liên kết

Trong hàng đợi sử dụng danh sách liên kết, chúng ta thường cần duy trì hai con trỏ:

• front trỏ đến phần tử đầu tiên của hàng đợi.

• rear trỏ đến phần tử cuối cùng của hàng đợi.

Cài đặt hàng đợi bằng danh sách liên kết đơn giản trong Python

Dưới đây là một ví dụ cài đặt hàng đợi sử dụng danh sách liên kết đơn giản (singly linked list):

class Node:

    def __init__(self, data):

       self.data = data

       self.next = None

class Queue:

    def __init__(self):

       self.front = None

       self.rear = None

    def is_empty(self):

        return self.front is None

    def enqueue(self, item):

        new_node = Node(item)

        if self.rear is None:

           self.front = self.rear = new_node

           return

       self.rear.next = new_node

       self.rear = new_node

    def dequeue(self):

        if self.is_empty():

           print("Hàng đợi rỗng, không thể lấy phần tử")

           return None

        temp = self.front

       self.front = temp.next

        if self.front is None:

           self.rear = None

        return temp.data

    def peek(self):

        if self.is_empty():

           print("Hàng đợi rỗng, không thể lấy phần tử")

           return None

        return self.front.data

# Ví dụ sử dụng

queue = Queue()

queue.enqueue(10)

queue.enqueue(20)

queue.enqueue(30)

print("Phần tử đầu tiên:", queue.peek())  # Output: 10

print("Lấy phần tử ra khỏi hàng đợi:", queue.dequeue())  # Output: 10

print("Lấy phần tử ra khỏi hàng đợi:", queue.dequeue())  # Output: 20

queue.enqueue(40)

print("Phần tử đầu tiên:", queue.peek())  # Output: 30

Kết luận

Sử dụng danh sách liên kết để biểu diễn hàng đợi là một cách hiệu quả và linh hoạt, giúp thực hiện các thao tác thêm và lấy phần tử từ hàng đợi một cách nhanh chóng và tiện lợi.