Hàng đợi DSA
Hàng đợi
Hàng đợi là một cấu trúc dữ liệu có thể chứa nhiều phần tử.
{{ resultText }}: {{currVal }}
Hãy tưởng tượng hàng đợi giống như mọi người đang xếp hàng trong siêu thị.
Người đầu tiên đứng xếp hàng cũng là người đầu tiên có thể thanh toán và rời khỏi siêu thị. Cách tổ chức các phần tử này được gọi là FIFO: First In First Out.
Các thao tác cơ bản chúng ta có thể thực hiện trên hàng đợi là:
- Enqueue: Thêm một phần tử mới vào hàng đợi.
- Dequeue: Loại bỏ và trả về phần tử đầu tiên (phía trước) khỏi hàng đợi.
- Peek: Trả về phần tử đầu tiên trong hàng đợi.
- isEmpty: Kiểm tra xem hàng đợi có trống không.
- Kích thước: Tìm số phần tử trong hàng đợi.
Hãy thử nghiệm các thao tác cơ bản này trong hoạt ảnh hàng đợi ở trên.
Hàng đợi có thể được thực hiện bằng cách sử dụng mảng hoặc danh sách liên kết.
Hàng đợi có thể được sử dụng để thực hiện lập lịch công việc cho máy in văn phòng, xử lý đơn hàng cho vé điện tử hoặc để tạo thuật toán tìm kiếm theo chiều rộng trong biểu đồ.
Hàng đợi thường được đề cập cùng với Ngăn xếp, đây là cấu trúc dữ liệu tương tự được mô tả ở trang trước .
Triển khai hàng đợi bằng cách sử dụng mảng
Để hiểu rõ hơn về lợi ích của việc sử dụng mảng hoặc danh sách liên kết để triển khai hàng đợi, bạn nên xem trang này để giải thích cách lưu trữ mảng và danh sách liên kết trong bộ nhớ.
Đây là giao diện khi chúng ta sử dụng một mảng làm hàng đợi:
{{ resultText }}: {{currVal }}
Lý do nên triển khai hàng đợi bằng mảng:
- Bộ nhớ hiệu quả: Các phần tử mảng không giữ địa chỉ các phần tử tiếp theo giống như các nút danh sách liên kết.
- Dễ triển khai và dễ hiểu hơn: Việc sử dụng mảng để triển khai hàng đợi yêu cầu ít mã hơn so với sử dụng danh sách liên kết và vì lý do này, việc sử dụng mảng thường dễ hiểu hơn.
Lý do không sử dụng mảng để triển khai hàng đợi:
- Kích thước cố định: Một mảng chiếm một phần cố định của bộ nhớ. Điều này có nghĩa là nó có thể chiếm nhiều bộ nhớ hơn mức cần thiết hoặc nếu mảng đầy, nó không thể chứa nhiều phần tử hơn. Và việc thay đổi kích thước một mảng có thể tốn kém.
- Chi phí dịch chuyển: Dequeue khiến phần tử đầu tiên trong hàng đợi bị xóa và các phần tử khác phải được dịch chuyển để thế chỗ các phần tử đã bị xóa. Điều này không hiệu quả và có thể gây ra vấn đề, đặc biệt nếu hàng đợi dài.
- Các lựa chọn thay thế: Một số ngôn ngữ lập trình có cấu trúc dữ liệu tích hợp được tối ưu hóa cho các hoạt động xếp hàng tốt hơn so với việc sử dụng mảng.
Lưu ý: Khi sử dụng mảng trong Python cho hướng dẫn này, chúng tôi thực sự đang sử dụng kiểu dữ liệu 'danh sách' Python, nhưng trong phạm vi của hướng dẫn này, kiểu dữ liệu 'danh sách' có thể được sử dụng giống như một mảng. Tìm hiểu thêm về danh sách Python tại đây .
Vì danh sách Python hỗ trợ tốt cho chức năng cần thiết để triển khai hàng đợi, nên chúng tôi bắt đầu bằng việc tạo hàng đợi và thực hiện các thao tác với hàng đợi chỉ bằng một vài dòng:
Ví dụ
Trăn:
queue = []
# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue: ", queue)
# Dequeue
element = queue.pop(0)
print("Dequeue: ", element)
# Peek
frontElement = queue[0]
print("Peek: ", frontElement)
# isEmpty
isEmpty = not bool(queue)
print("isEmpty: ", isEmpty)
# Size
print("Size: ", len(queue))
Chạy Ví dụ »Nhưng để tạo một cấu trúc dữ liệu cho hàng đợi một cách rõ ràng, với các thao tác cơ bản, thay vào đó chúng ta nên tạo một lớp hàng đợi. Cách tạo hàng đợi trong Python này cũng giống với cách tạo hàng đợi trong các ngôn ngữ lập trình khác như C và Java.
Ví dụ
Trăn:
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, element):
self.queue.append(element)
def dequeue(self):
if self.isEmpty():
return "Queue is empty"
return self.queue.pop(0)
def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.queue[0]
def isEmpty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# Create a queue
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", myQueue.queue)
print("Dequeue: ", myQueue.dequeue())
print("Peek: ", myQueue.peek())
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())
Chạy Ví dụ »Triển khai hàng đợi bằng danh sách liên kết
Lý do sử dụng danh sách liên kết để triển khai hàng đợi:
- Kích thước động: Hàng đợi có thể tăng và giảm linh hoạt, không giống như mảng.
- Không dịch chuyển: Phần tử phía trước của hàng đợi có thể bị xóa (enqueue) mà không cần phải dịch chuyển các phần tử khác trong bộ nhớ.
Lý do không sử dụng danh sách liên kết để triển khai hàng đợi:
- Bộ nhớ bổ sung: Mỗi phần tử hàng đợi phải chứa địa chỉ của phần tử tiếp theo (nút danh sách liên kết tiếp theo).
- Khả năng đọc: Mã có thể khó đọc và viết hơn đối với một số người vì nó dài hơn và phức tạp hơn.
Đây là cách có thể triển khai hàng đợi bằng danh sách liên kết.
Ví dụ
Trăn:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
self.length = 0
def enqueue(self, element):
new_node = Node(element)
if self.rear is None:
self.front = self.rear = new_node
self.length += 1
return
self.rear.next = new_node
self.rear = new_node
self.length += 1
def dequeue(self):
if self.isEmpty():
return "Queue is empty"
temp = self.front
self.front = temp.next
self.length -= 1
if self.front is None:
self.rear = None
return temp.data
def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.front.data
def isEmpty(self):
return self.length == 0
def size(self):
return self.length
def printQueue(self):
temp = self.front
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
# Create a queue
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", end="")
myQueue.printQueue()
print("Dequeue: ", myQueue.dequeue())
print("Peek: ", myQueue.peek())
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())
Chạy Ví dụ »