Kiểu dữ liệu Python phù hợp nhất để triển khai hàng đợi
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 Show
Cách tạo ngăn xếp trong Python từ đầuTriển khai ngăn xếp trong Python mà không cần sử dụng bất kỳ thư viện nàocon 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 5 là phần tử cũ nhất của hàng đợi. Điều đó có nghĩa là nó đã được đưa vào đầu tiên. Đối với các đặc điểm của FIFO, 5 là đặc điểm cũng sẽ bị xóa trước tiênNhững điểm cần tập trung vào
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 9 và 0 của danh sách để triển khai hàng đợi. Theo mặc định, phương thức 9 sẽ chèn một phần tử từ cuối hàng đợi. Nhưng để xóa một phần tử khỏi giao diện người dùng, chúng ta phải chỉ định vị trí trong phương thức 0. Hãy tạo một lớp 3 sử dụng danh sách để tạo hàng đợiSau khi chúng tôi chạy mã, nó sẽ cho chúng tôi đầu ra sau Item 1 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ậnTrong 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 đợiTươ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 đợiViệ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áchDanh 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
Bướ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
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
Bướ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
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
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
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
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
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
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 0Chú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ậpNó đượ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
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 0Bạn sẽ nhận được một kết quả tương tự như đầu ra sau 1#3. Xếp hàng từ hàng đợiPython 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
Hãy triển khai hàng đợi với các phương thức trên 2Kiểm tra đầu ra của mã trên 3Có 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ậnTô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ó Cấu trúc dữ liệu tốt nhất để thực hiện hàng đợi là gì?Một hàng đợi có thể được triển khai bằng cách sử dụng Mảng, Danh sách liên kết, Con trỏ và Cấu trúc. Việc triển khai sử dụng mảng một chiều là phương pháp đơn giản nhất trong tất cả các phương pháp đã đề cập.
Loại bộ sưu tập Python tích hợp nào sẽ là lựa chọn tốt để biểu thị hàng đợi trong đó mục đầu tiên trong hàng đợi là mục đầu tiên ra khỏi hàng đợi?Lựa chọn mặc định tốt. bộ sưu tập.
deque là một lựa chọn mặc định tuyệt vời để triển khai cấu trúc dữ liệu hàng đợi FIFO trong Python.
Python có cấu trúc dữ liệu hàng đợi không?Hàng đợi trong Python là cấu trúc dữ liệu tuyến tính có phần sau và phần trước, tương tự như ngăn xếp . Nó lưu trữ các mục tuần tự theo cách FIFO (First In First Out). |