Hàng đợi là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Nhập trước xuất trước [FIFO]. Điều đó có nghĩa là phần tử đầu tiên được thêm vào hàng đợi là phần tử đầu tiên bị xóa. Nó có điểm tương đồng với ngăn xếp. Hàng đợi và ngăn xếp thường được nghiên cứu cùng nhau. Nhưng để mọi thứ đơn giản và ngắn gọn, tôi quyết định viết hai bài riêng về chúng. Đây là bài viết của tôi về cách tạo ngăn xếp trong Python
Cách tạo ngăn xếp trong Python từ đầu
Triển khai ngăn xếp trong Python mà không cần sử dụng bất kỳ thư viện nào
con trăn. tiếng Anh đơn giản. io
Nhưng trong bài viết này, chúng ta sẽ tìm hiểu cách tạo hàng đợi. Bắt đầu nào
Cấu trúc dữ liệu hàng đợiMột ví dụ điển hình về hàng đợi là một hàng hành khách đang đợi xe buýt. Người đầu tiên trong hàng sẽ lên xe buýt trước. Đây chính xác là cách một hàng đợi hoạt động. Phần tử đầu tiên của hàng đợi sẽ bị xóa trước. Đó là đặc điểm FIFO của hàng đợi. Nó cũng là một cấu trúc dữ liệu động. Điều đó có nghĩa là hàng đợi có khả năng mở rộng hoặc thu nhỏ kích thước của nó. Hãy cố gắng hiểu một hàng đợi một cách trực quan
Cấu trúc dữ liệu hàng đợi. Hình ảnh của tác giả
Đây
class Queue:
passclass Queue:
pass- Chèn và xóa trên hàng đợi xảy ra ở các đầu khác nhau. Vì vậy, chúng tôi cần theo dõi Giao diện người dùng và Giao diện người dùng phía sau của hàng đợi
- Mặc dù hàng đợi có khả năng mở rộng kích thước của nó, nhưng hàng đợi cũng có thể có kích thước tối đa. Nếu chúng ta cố gắng chèn một phần tử vượt quá dung lượng tối đa của nó, nó sẽ gây tràn
- Nếu chúng ta cố gắng loại bỏ một phần tử khỏi hàng đợi trống, nó sẽ dẫn đến tràn
- Thao tác enqueue sẽ chèn một phần tử vào hàng đợi. Độ phức tạp về thời gian của phép toán
7 là O[1]class Queue: pass - Thao tác dequeue sẽ xóa một phần tử khỏi hàng đợi. Độ phức tạp về thời gian của phép toán
8 cũng là O[1]class Queue: pass
Chúng ta có thể sử dụng danh sách Python để tạo hàng đợi. Chúng tôi sẽ sử dụng phương thức
class Queue:
passclass Queue:
def __init__[self]:
self.elements = []class Queue:
passclass Queue:
def __init__[self]:
self.elements = []class Queue:
def __init__[self]:
self.elements = []Sau khi chúng tôi chạy mã, nó sẽ cho chúng tôi đầu ra sau
Item 1
Item 2
Item 3
Item 4
Item 5
Queue is empty. Underflow!Chèn và xóa trong hàng đợi đang diễn ra theo thứ tự FIFO. Hãy trực quan hóa các hoạt động để hiểu rõ hơn
hoạt động enqueue[] và dequeue[] trong hàng đợi. Hình ảnh của tác giảKết luận
Trong bài viết này, mình đã chia sẻ cách đơn giản nhất để tạo hàng đợi trong Python. Sử dụng danh sách để tạo hàng đợi có thể không phải là cách hiệu quả nhất, nhưng nó sẽ giúp chúng tôi hiểu các nguyên tắc cơ bản của cấu trúc dữ liệu này. Ngoài ra còn có các tùy chọn khác để tạo hàng đợi trong Python
Cấu trúc dữ liệu đóng một vai trò quan trọng trong thế giới lập trình. Chúng giúp chúng tôi tổ chức dữ liệu của mình theo cách có thể được sử dụng hiệu quả. Hàng đợi là một trong những cấu trúc dữ liệu đơn giản nhất hiện có
Trong bài viết này, chúng ta sẽ tìm hiểu về Hàng đợi và cách triển khai nó trong Python
Hàng đợi là gì?
Hàng đợi là cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Nhập trước/Xuất trước [FIFO]. Nó ngược lại với cấu trúc dữ liệu Stack
Chúng ta có thể so sánh hàng đợi với hàng đợi ngoài đời thực tại quầy vé rạp chiếu phim. Hãy xem hình minh họa của một hàng đợi như sau
Nếu bạn quan sát hàng đợi tại quầy, người thứ hai chỉ có thể vào quầy sau khi người thứ nhất hoàn thành công việc của mình. Ở đây người đầu tiên đến quầy và sau đó là người thứ hai. Vì vậy, ở đây mọi người đang tuân theo nguyên tắc FIFO[Nhập trước/Xuất trước] . Ai đến trước thì hoàn thành công việc trước. Chúng ta có thể thấy một kiểu xếp hàng tương tự trong cuộc sống hàng ngày của chúng ta
Cấu trúc dữ liệu Hàng đợi cũng tuân theo nguyên tắc tương tự. Bây giờ, bạn đã biết hàng đợi là gì và nguyên tắc của nó. Hãy xem các thao tác có thể được thực hiện trên cấu trúc dữ liệu hàng đợi
Hoạt động trong hàng đợi
Tương tự như ngăn xếp, chúng ta sẽ tìm thấy hai thao tác chính trong cấu trúc dữ liệu hàng đợi
hàng đợi [dữ liệu]
Thêm dữ liệu mới vào hàng đợi ở cuối. Bên được gọi là phía sau
dequeue[]
Loại bỏ dữ liệu từ phía trước của hàng đợi. Mặt bên được gọi là mặt trước
Cùng xem minh họa thao tác hàng đợi để hiểu rõ hơn. Một bức tranh nói lên ngàn lời nói
Chúng ta có thể viết một số hàm trợ giúp để có thêm thông tin về hàng đợi. Không có giới hạn về số lượng chức năng trợ giúp bạn sẽ có. Bây giờ hãy tập trung vào điều quan trọng nhất từng được đề cập bên dưới
ở phía sau[]
Trả về phần tử đầu tiên từ cuối hàng đợi
đổi diện[]
Trả về phần tử đầu tiên từ đầu hàng đợi
is_empty[]
Trả về hàng đợi có rỗng hay không
Nó không nhàm chán cho bạn?
Đối với tôi Vâng
Nhưng, chúng ta không thể làm bất cứ điều gì mà không biết các khái niệm. Chúng tôi phải hoàn thành biết nó trước khi thực hiện. Đừng lo lắng, đã đến lúc làm bẩn tay chúng ta với một số mã
Tôi cho rằng bạn đã cài đặt python trên PC của mình, nếu không, bạn cũng có thể dùng thử trình biên dịch trực tuyến
Thực hiện hàng đợi
Việc triển khai một hàng đợi sẽ không mất hơn 15 phút đối với một lập trình viên. Học xong sẽ nói. Có lẽ bạn có thể thực hiện nó trong vòng vài phút sau hướng dẫn này
Có nhiều cách để triển khai hàng đợi trong Python. Hãy xem từng bước triển khai hàng đợi khác nhau
#1. Danh sách
Danh sách là một kiểu dữ liệu có sẵn trong Python. Chúng ta sẽ sử dụng kiểu dữ liệu danh sách để triển khai hàng đợi trong một lớp. Chúng tôi sẽ hướng dẫn bạn các bước khác nhau để triển khai cấu trúc dữ liệu hàng đợi từ đầu mà không cần bất kỳ mô-đun nào. Hãy nhảy vào nó
Bước 1.
Viết một lớp có tên Hàng đợi
class Queue:
passBước 2
Phải có một số biến để lưu trữ dữ liệu của hàng đợi trong lớp. Hãy đặt tên cho nó các phần tử. Và đó là một danh sách tất nhiên
class Queue:
def __init__[self]:
self.elements = []Bước 3
Để chèn dữ liệu vào hàng đợi, chúng ta cần một phương thức trong lớp. Phương pháp này được gọi là enqueue như chúng ta đã thảo luận trong phần trước của hướng dẫn
Phương thức lấy một số dữ liệu và thêm nó vào hàng đợi [phần tử]. Chúng ta có thể sử dụng phương thức append của kiểu dữ liệu danh sách để thêm dữ liệu vào cuối hàng đợi
class Queue:
# ...
def enqueue[self, data]:
self.elements.append[data]
return dataBước 4.
Hàng đợi cần phải có một lối ra. Và đó được gọi là dequeue. Tôi nghĩ bạn đã đoán được rằng chúng ta sẽ sử dụng phương thức pop của kiểu dữ liệu danh sách. Nếu bạn đoán hay không, chúc mừng
Phương thức pop của kiểu dữ liệu danh sách xóa một phần tử khỏi danh sách của chỉ mục đã cho. Nếu chúng tôi không đưa ra bất kỳ chỉ mục nào, thì nó sẽ xóa phần tử cuối cùng của danh sách
Ở đây, chúng ta cần xóa phần tử đầu tiên của danh sách. Vì vậy, chúng ta phải chuyển chỉ số 0 cho phương thức pop
class Queue:
# ...
def dequeue[self]:
return self.elements.pop[0]
Thế là đủ cho một hàng đợi. Tuy nhiên, chúng ta cần các hàm trợ giúp để kiểm tra xem các hoạt động của hàng đợi có hoạt động bình thường hay không. Hãy viết cả các hàm trợ giúp
Bước5.
Phương thức rear[] dùng để lấy phần tử cuối cùng của hàng đợi. Lập chỉ mục phủ định trong kiểu dữ liệu danh sách giúp chúng tôi lấy phần tử cuối cùng của hàng đợi
class Queue:
# ...
def rear[self]:
return self.elements[-1]
Bước 6.
Phương thức front[] được sử dụng để lấy phần tử đầu tiên của hàng đợi. Chúng ta có thể lấy phần tử đầu tiên của hàng đợi bằng chỉ mục danh sách
class Queue:
# ...
def front[self]:
return self.elements[0]
Bước7.
Phương thức is_empty[] dùng để kiểm tra xem hàng đợi có trống hay không. Chúng ta có thể kiểm tra độ dài của danh sách
class Queue:
# ...
def is_empty[self]:
return len[self.elements] == 0
Phù. đã hoàn thành phần triển khai của cấu trúc dữ liệu hàng đợi. Chúng ta cần tạo một đối tượng để lớp Queue sử dụng
Hãy làm nó
________số 8Bây giờ, chúng ta có một đối tượng Hàng đợi. Hãy kiểm tra nó với một số hoạt động
- Kiểm tra xem hàng đợi có trống hay không bằng phương thức is_empty. Nó sẽ trả về True
- Thêm các số 1, 2, 3, 4, 5 vào hàng đợi bằng phương thức enqueue
- Phương thức is_empty sẽ trả về Sai. Kiểm tra nó
- In các phần tử phía trước và phía sau bằng các phương pháp phía trước và phía sau tương ứng
- Xóa phần tử khỏi hàng đợi bằng phương thức dequeue
- Kiểm tra phần tử phía trước. Nó sẽ trả về phần tử 2
- Bây giờ, xóa tất cả các phần tử khỏi hàng đợi
- Phương thức is_empty sẽ trả về True. Kiểm tra nó
Tôi nghĩ thế là đủ để kiểm tra việc triển khai hàng đợi của chúng tôi. Viết mã cho từng bước được đề cập ở trên để kiểm tra hàng đợi
Bạn đã viết mã?
Không, đừng lo lắng
Kiểm tra mã dưới đây
class Queue:
def __init__[self]:
self.elements = []
def enqueue[self, data]:
self.elements.append[data]
return data
def dequeue[self]:
return self.elements.pop[0]
def rear[self]:
return self.elements[-1]
def front[self]:
return self.elements[0]
def is_empty[self]:
return len[self.elements] == 0
if __name__ == '__main__':
queue = Queue[]
## checking is_empty method -> True
print[queue.is_empty[]]
## adding the elements
queue.enqueue[1]
queue.enqueue[2]
queue.enqueue[3]
queue.enqueue[4]
queue.enqueue[5]
## again checking is_empty method -> False
print[queue.is_empty[]]
## printing the front and rear elements using front and rear methods respectively -> 1, 5
print[queue.front[], end=' ']
print[queue.rear[]]
## removing the element -> 1
queue.dequeue[]
## checking the front and rear elements using front and rear methods respectively -> 2 5
print[queue.front[], end=' ']
print[queue.rear[]]
## removing all the elements
queue.dequeue[]
queue.dequeue[]
queue.dequeue[]
queue.dequeue[]
## checking the is_empty method for the last time -> True
print[queue.is_empty[]]Tôi nghĩ rằng bạn chạy chương trình trên. Bạn có thể nhận được một đầu ra tương tự như kết quả sau
class Queue:
passChúng ta có thể trực tiếp sử dụng kiểu dữ liệu danh sách làm cấu trúc dữ liệu hàng đợi. Việc triển khai hàng đợi trên giúp bạn hiểu rõ hơn về việc triển khai hàng đợi trong các ngôn ngữ lập trình khác
Bạn cũng có thể sử dụng cách triển khai hàng đợi ở lớp trên trong một chương trình khác của dự án bằng cách tạo đối tượng như chúng ta đã làm trước đó
Chúng tôi đã triển khai hàng đợi từ đầu bằng cách sử dụng loại dữ liệu danh sách. Có bất kỳ mô-đun tích hợp nào cho hàng đợi không? . chúng tôi có triển khai hàng đợi tích hợp. Hãy xem chúng
#2. deque từ bộ sưu tập
Nó được triển khai dưới dạng hàng đợi hai đầu. Vì nó hỗ trợ thêm và bớt phần tử từ cả hai đầu nên chúng ta có thể sử dụng nó như một ngăn xếp và hàng đợi. Hãy xem triển khai hàng đợi bằng cách sử dụng dequeue
Nó được triển khai bằng cách sử dụng các cấu trúc dữ liệu khác được gọi là danh sách liên kết kép. Vì vậy, hiệu suất của việc chèn và xóa các phần tử là nhất quán. Việc truy cập các phần tử từ danh sách liên kết ở giữa mất O[n] thời gian. Chúng ta có thể sử dụng nó như một hàng đợi vì không cần truy cập các phần tử ở giữa từ hàng đợi
Hãy kiểm tra các phương thức khác nhau mà dequeue cung cấp cho chúng ta
- append[data] – được sử dụng để thêm dữ liệu vào hàng đợi
- popleft[] – được sử dụng để xóa phần tử đầu tiên khỏi hàng đợi
Không có phương pháp thay thế nào cho phía trước, phía sau và is_empty. Chúng tôi có thể in toàn bộ hàng đợi thay cho các phương thức phía trước và phía sau. Tiếp theo, chúng ta có thể sử dụng phương thức len để kiểm tra xem hàng đợi có trống hay không
Chúng tôi đã làm theo một loạt các bước để kiểm tra việc triển khai hàng đợi trong phần trước. Hãy làm theo cùng một loạt các bước ở đây
class Queue:
def __init__[self]:
self.elements = []Bạn sẽ nhận được một kết quả tương tự như đầu ra sau
class Queue:
def __init__[self]:
self.elements = []#3. Xếp hàng từ hàng đợi
Python có một mô-đun tích hợp có tên là hàng đợi phục vụ một lớp có tên là Hàng đợi để triển khai hàng đợi. Nó tương tự như cái chúng tôi đã triển khai trước đây
Trước tiên, hãy kiểm tra các phương thức khác nhau của lớp Hàng đợi
- put[data] – thêm hoặc đẩy dữ liệu vào hàng đợi
- get[] – xóa phần tử đầu tiên khỏi hàng đợi và trả về phần tử đó
- empty[] – trả về ngăn xếp có rỗng hay không
- qsize[] – trả về độ dài của hàng đợi
Hãy triển khai hàng đợi với các phương thức trên
class Queue:
def __init__[self]:
self.elements = []Kiểm tra đầu ra của mã trên
class Queue:
def __init__[self]:
self.elements = []Có một số phương thức khác trong lớp Hàng đợi. Bạn có thể khám phá chúng bằng cách sử dụng chức năng tích hợp sẵn dir
Sự kết luận
Tôi hy vọng bạn đã học về cấu trúc dữ liệu hàng đợi và cách triển khai nó. Đó là nó cho hàng đợi. Bạn có thể sử dụng hàng đợi ở những nơi khác nhau cần được xử lý theo thứ tự FIFO[Nhập trước/Xuất trước]. Sử dụng hàng đợi trong giải quyết vấn đề bất cứ khi nào bạn có trường hợp sử dụng nó