Hàng đợi theo thuật ngữ lập trình là Kiểu dữ liệu trừu tượng lưu trữ thứ tự các mục được thêm vào cấu trúc nhưng nó chỉ cho phép thêm vào cuối hàng đợi trong khi chỉ cho phép xóa khỏi đầu hàng đợi. Khi làm như vậy, điều này tuân theo cấu trúc dữ liệu First-In First-Out [FIFO]. Về cơ bản, điều này hoạt động giống như bạn mong đợi một hàng đợi hoạt động trong thực tế, chẳng hạn như khi xếp hàng để vào một cửa hàng, những người đến đó trước sẽ đến đó trước. Tuy nhiên, không giống như đời thực, chúng tôi xây dựng điều này theo cách để đảm bảo rằng không có tình trạng nhảy hàng đợi
GIF từ GiphyChúng có thể được sử dụng khi chúng ta muốn lưu trữ các kết quả đầu ra trong một cấu trúc giữ nguyên thứ tự của chúng và sau đó thực hiện các hành động theo thứ tự đã cho. Các ví dụ phổ biến về điều này trong lập trình bao gồm lập lịch công việc cho CPU máy tính của bạn, xếp hàng công việc cho máy in để đảm bảo rằng những công việc được gửi trước đã được thực hiện, xử lý đơn đặt hàng cho một doanh nghiệp hoặc xử lý thư
Với suy nghĩ này, khi biết chúng ta muốn Cấu trúc dữ liệu làm gì và cách chúng ta muốn tương tác với nó, thì chúng ta có thể bắt đầu suy nghĩ về cách triển khai điều này trong Cấu trúc dữ liệu thực tế trong Python. Các phương pháp chính thường được liên kết với điều này bao gồm
- hàng đợi [mục]. Thêm một mục vào cuối hàng đợi
- dequeue[]. Xóa và trả lại mục ở phía trước hàng đợi
- nhìn lén[]. Trả lại vật phẩm ở phía trước hàng đợi mà không lấy nó ra
- is_empty[]. Trả về True nếu hàng đợi rỗng
- kích thước[]. Trả về có bao nhiêu mục trong hàng đợi
Điều này có nghĩa là chúng ta cần xây dựng cái này bằng cách sử dụng Kiểu dữ liệu Python có thể thay đổi và có thể được sử dụng để lưu trữ một bộ sưu tập các mục được sắp xếp theo thứ tự. Điều đầu tiên chúng ta có thể tự hỏi mình là liệu có Kiểu dữ liệu nào đã được triển khai trong Python có thể làm điều này cho chúng ta không?
GIF từ GiphyMột danh sách. Chúng ta có thể sử dụng một danh sách
Chúng tôi biết rằng một danh sách có thể thay đổi, nó có thể được thay đổi và chúng tôi chỉ cần thêm và xóa các mục từ đầu và cuối bằng cách sử dụng chức năng đã có sẵn của danh sách để triển khai Hàng đợi
Khi sử dụng danh sách, chúng ta phải định nghĩa một lớp sử dụng danh sách này nhưng chỉ có chức năng cụ thể cho phép người dùng tương tác với nó theo cách chúng ta muốn. Đối với điều này, chúng ta có thể sử dụng cấu trúc lớp của Python để có thể xác định thông tin mà cấu trúc dữ liệu sẽ chứa và cả các phương thức chúng ta muốn sử dụng
Điều đầu tiên cần làm sau đó là đặt tên lớp là
def enqueue[self, item]:6 và tạo phương thức khởi tạo cho lớp mới này. Những gì chúng tôi muốn là khi một thể hiện mới của đối tượng được tạo là khởi tạo một danh sách trống có thể được truy cập bằng thuộc tính
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:7. Mã cho điều này có thể như sau
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
class Queue: #create the constructor
def __init__[self]: #create an empty list as the items attribute
self.items = []
Điều này có nghĩa là khi chúng ta tạo một thể hiện của lớp
def enqueue[self, item]:6 thì thuộc tính
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:0 sẽ đại diện cho một danh sách rỗng
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
Sau đó, chúng ta có thể bắt đầu thêm chức năng chính vào lớp
def enqueue[self, item]:6. Điều đầu tiên chúng tôi muốn có thể làm là thêm một mục vào
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:6 của chúng tôi. Tại thời điểm này, điều quan trọng là có thể xác định đầu cuối nào là đầu hàng đợi nơi chúng tôi lấy dữ liệu và đầu cuối nào là cuối hàng đợi mà chúng tôi có thể thêm các mục vào
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
Điều này có ý nghĩa đối với mỗi quá trình sẽ mất bao lâu khi thay đổi những thứ ở đầu danh sách dẫn đến độ phức tạp về thời gian là O[n] vì sau đó chúng ta phải thay đổi tất cả các chỉ số của các mục tiếp theo trong danh sách để dịch chuyển mọi thứ sang bên phải. Tuy nhiên, nếu chúng ta thao tác với những thứ ở cuối danh sách thì điều này có độ phức tạp về thời gian là O[1] vì chúng ta chỉ thay đổi chỉ mục ở cuối danh sách khi chúng ta xóa hoặc thêm một mục
GIF từ GiphyTuy nhiên, điều này không thực sự quá quan trọng vì bạn chọn thêm hoặc bớt bên nào từ chức năng kia sẽ vẫn có độ phức tạp về thời gian khác. Vì vậy, với ý nghĩ đó, chúng ta có thể triển khai phương thức
def enqueue[self, item]:3 để thêm một mục vào Hàng đợi của mình
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
Điều này sẽ chỉ thêm một mục vào cuối [bên trái] hàng đợi của chúng tôi. Trong trường hợp này, chúng tôi không quan tâm quá nhiều đến những gì chúng tôi thêm vào hàng đợi, chỉ cần chúng tôi có thể thêm nó. Tất nhiên, bạn có thể thêm nhiều chức năng hơn cho việc này, nhưng hiện tại điều này vẫn ổn
Điều này có nghĩa là khi chúng tôi muốn xóa các mục khỏi cuối bên phải của danh sách trong lớp Queue của chúng tôi. Khi làm như vậy, chúng ta cần lưu ý đến một trường hợp cạnh khá đơn giản là Hàng đợi của chúng ta có trống hay không. Trong trường hợp này, nếu Hàng đợi trống, chúng ta có thể chỉ cần trả về
def enqueue[self, item]:4 để chúng ta vẫn đang trả về thứ gì đó và chương trình sẽ không ném và báo lỗi, nhưng nếu nó không trống thì chúng ta có thể trả về mục “đầu tiên” trong hàng đợi và . Vì chúng tôi đang sử dụng lớp danh sách sẵn có của Python, nên chúng tôi chỉ cần sử dụng phương thức
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:5 trong Python 3. 6+ xóa mục ist khỏi danh sách và trả lại. Điều này chạy trong thời gian không đổi O[1] vì chúng tôi chỉ xóa mục danh sách và không ảnh hưởng đến bất kỳ chỉ mục nào khác. Vì vậy, điều này có thể được thực hiện như
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def dequeue[self]:
"""
Removes the first item from the queue and removes it Runs in constant time O[1] because we are index to
the end of the list.
""" #check to see whether there are any items in the queue
#if so then we can pop the final item
if self.items:
return self.items.pop[] #else then we return None
else: return None
Vì vậy, chúng tôi đã triển khai chức năng chính của Hàng đợi, đảm bảo rằng chúng tôi chỉ thêm các mục vào một đầu của hàng đợi và xóa các mục khỏi đầu kia của Hàng đợi. Điều này sẽ duy trì thứ tự của các mục trong Hàng đợi và đảm bảo rằng sau đó chúng tôi sử dụng các mục này theo cùng thứ tự mà chúng đã được thêm vào đó
Sau đó, chúng ta có thể nghĩ về các phương pháp bổ sung khác sẽ hỗ trợ việc sử dụng Cấu trúc dữ liệu hàng đợi trong các chương trình thực tế. Chức năng bổ sung đầu tiên mà chúng tôi có thể thêm sau đó là cho phép người dùng xem xét mục tiếp theo sẽ bị xóa khỏi Hàng đợi mà nó không thực sự bị xóa. Việc triển khai điều này sẽ tuân theo cấu trúc tương tự như phương pháp
def enqueue[self, item]:6 nhưng thay vì sử dụng
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:5, chúng ta có thể ngụ ý truy cập mục có mục cuối cùng trong danh sách. Điều này có nghĩa là chúng tôi có độ phức tạp về thời gian là O[1] khi chúng tôi sử dụng chỉ mục để truy cập vào mục, làm cho nó đẹp và đơn giản
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def peek[self]:
"""
Returns the final item in the Queue without removal
Runs in constant time O[1] as we are only using the index
""" #if there are items in the Queue
if self.items:
#then return the first item
return self.items
#else then return none
else:
return Non
Chúng tôi cũng có thể cung cấp phương pháp kiểm tra xem Hàng đợi có trống hay không. Điều này sẽ chỉ trả về một giá trị Boolean là
def enqueue[self, item]:8 nếu Hàng đợi thực sự trống và
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:9 nếu không. Điều này cũng chạy trong thời gian cố định vì nó chỉ đơn giản là kiểm tra xem danh sách trong
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:6 có tồn tại hay không
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def enqueue[self, item]:2
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
Chúng ta có thể tạo một phương thức trả về kích thước của Hàng đợi. Điều này có thể cho biết sử dụng kích thước của Hàng đợi, giống như đối với một danh sách và cho chúng tôi biết có bao nhiêu mục đã được thêm vào hoặc có bao nhiêu mục còn lại trong Hàng đợi
def enqueue[self, item]:3
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
Cuối cùng, chúng tôi muốn đảm bảo rằng chúng tôi cố gắng in ra một thể hiện của lớp
def enqueue[self, item]:6, nó thực sự có thể đọc được để mọi người thấy rằng đó là Hàng đợi và Hàng đợi đó chứa gì. Đối với điều này, chúng tôi sử dụng phương pháp dunder
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
def dequeue[self]:2 đặc biệt của lớp để cho trình thông dịch biết cách chúng tôi muốn in ra một thể hiện của lớp. Trong trường hợp này, chúng tôi chỉ muốn trả về toàn bộ danh sách có trong ngăn xếp có thể được triển khai dưới dạng
"""
Removes the first item from the queue and removes it Runs in constant time O[1] because we are index to
the end of the list.
""" #check to see whether there are any items in the queue
#if so then we can pop the final item
if self.items:
return self.items.pop[] #else then we return None
else: return None
def enqueue[self, item]:5
"""
Add item to the left of the list, returns Nothing Runs in linear time O[n] as we change all indices
as we add to the left of the list
""" #use the insert method to insert at index 0
self.items.insert[0, item]
Phù. Vậy còn việc kết hợp tất cả những thứ này lại với nhau thì sao?
Tại thời điểm này, bạn có thể nghĩ tại sao tôi cần phải biết điều này?
- Lập kế hoạch công việc trong CPU
- Thuật toán duyệt đồ thị
- Xử lý đơn hàng
- hàng đợi máy in
Bạn nên biết khi xây dựng các chương trình này để biết Cấu trúc dữ liệu này trông như thế nào trong Python và cung cấp cho bạn chức năng để có thể giải quyết những thách thức này
Điều này cũng có thể xuất hiện trong các cuộc Phỏng vấn về Khoa học Dữ liệu hoặc Kỹ sư Phần mềm, chẳng hạn như yêu cầu bạn xây dựng một máy in sử dụng hàng đợi hoặc trong việc tạo các thuật toán Traversal Graph chẳng hạn như Tìm kiếm theo chiều sâu
Vậy là xong, bạn đã biết cách triển khai Hàng đợi trong Python và cả một số cách sử dụng nó nữa
Đây là bài viết thứ bảy trong loạt bài khám phá Cấu trúc dữ liệu, cách sử dụng và triển khai chúng trong Python. Nếu bạn bỏ lỡ ba phần trước về Danh sách được liên kết, Ngăn xếp và Từ điển trong Python, bạn có thể tìm thấy chúng tại các liên kết sau
Hướng dẫn đầy đủ về danh sách liên kết trong Python
Danh sách được liên kết là gì và cách triển khai chúng trong Python
hướng tới khoa học dữ liệu. com
Hướng dẫn đầy đủ về Stacks trong Python
Xây dựng và sử dụng cấu trúc dữ liệu ngăn xếp trong Python
hướng tới khoa học dữ liệu. com
Hướng dẫn đầy đủ về từ điển trong Python
Từ điển là gì, tạo ra chúng, truy cập chúng, cập nhật chúng và các phương pháp đặc biệt
hướng tới khoa học dữ liệu. com
Các bài viết trong tương lai của loạt bài này sẽ đề cập đến Danh sách được liên kết, Hàng đợi và Đồ thị. Để đảm bảo bạn không bỏ lỡ bất kỳ điều gì, hãy đăng ký để nhận thông báo qua email khi chúng được xuất bản
Nhận email bất cứ khi nào Philip Wilkinson xuất bản
Nhận email bất cứ khi nào Philip Wilkinson xuất bản. Bằng cách đăng ký, bạn sẽ tạo một tài khoản Medium nếu bạn chưa có…
philip-wilkinson. Trung bình. com
Và nếu bạn thích những gì bạn đọc nhưng chưa phải là thành viên Phương tiện, thì hãy cân nhắc hỗ trợ cả tôi và các tác giả tuyệt vời khác trên nền tảng này bằng cách đăng ký bằng mã giới thiệu của tôi bên dưới