Nếu bạn sử dụng Python, có lẽ bạn đã quen thuộc với các danh sách và có lẽ bạn cũng sử dụng chúng rất nhiều. Chúng là những cấu trúc dữ liệu tuyệt vời với nhiều phương pháp hữu ích cho phép người dùng sửa đổi danh sách bằng cách thêm, xóa và sắp xếp các mục. Tuy nhiên, có một số trường hợp sử dụng khi một danh sách có vẻ như là một lựa chọn tuyệt vời, nhưng thực tế không phải vậy.
Trong bài viết này, chúng tôi sẽ đề cập đến cách hàm
stack = ['plate_1', 'plate_2', 'plate_6']
0 từ mô-đun stack = ['plate_1', 'plate_2', 'plate_6']
1 có thể là lựa chọn tốt hơn nhiều khi bạn cần triển khai hàng đợi và ngăn xếp trong PythonĐể theo dõi bài viết này, chúng tôi giả định rằng bạn đã có một số kinh nghiệm về lập trình Python, sử dụng danh sách và các phương thức của nó, vì hầu hết chúng có thể được ngoại suy để sử dụng
stack = ['plate_1', 'plate_2', 'plate_6']
2Hàng đợi và ngăn xếp
điều đầu tiên đầu tiên. hãy hiểu các khái niệm về hàng đợi và ngăn xếp trước khi chúng ta bắt đầu mô-đun
stack = ['plate_1', 'plate_2', 'plate_6']
1hàng đợi
Hàng đợi là cấu trúc dữ liệu lưu trữ các mục theo cách Nhập trước xuất trước [FIFO]. Nghĩa là, mục đầu tiên được thêm vào hàng đợi sẽ là mục đầu tiên bị xóa khỏi hàng đợi.
Ví dụ: giả sử bạn đang thêm các bài hát vào hàng đợi trong trình phát nhạc yêu thích của mình. Bạn chưa bắt đầu, vì vậy hàng đợi của bạn trống. Sau đó, bạn thêm ba bài hát.
stack = ['plate_1', 'plate_2', 'plate_6']
4, stack = ['plate_1', 'plate_2', 'plate_6']
5, và stack = ['plate_1', 'plate_2', 'plate_6']
6, theo thứ tự này. Bây giờ hàng đợi của bạn trông như thế nàyqueue = ['song_1', 'song_2', 'song_3']
Sau đó, bạn bắt đầu phát bài hát trong hàng đợi. Người chơi đầu tiên và chuyển ra khỏi hàng đợi là người đầu tiên được thêm vào.
stack = ['plate_1', 'plate_2', 'plate_6']
4— do đó, nhập trước, xuất trước. Theo quy tắc này, nếu bạn phát một vài bài hát và sau đó thêm ba bài nữa, đây sẽ là hàng đợi của bạnqueue = ['song_3', 'song_4', 'song_5', 'song_6']
ngăn xếp
Ngăn xếp là cấu trúc dữ liệu lưu trữ các mục theo cách Nhập trước xuất trước [LIFO]. Nghĩa là, phần tử cuối cùng được thêm vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra khỏi ngăn xếp
Một ví dụ cổ điển về ngăn xếp là một đống đĩa. Giả sử bạn có một vài người bạn đến ăn tối và dùng năm đĩa. Sau bữa tối, bạn chất năm chiếc đĩa đó vào bồn rửa. Vì vậy, bạn sẽ có ngăn xếp này
stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
Khi bạn bắt đầu rửa bát đĩa, bạn bắt đầu từ đầu đống,
stack = ['plate_1', 'plate_2', 'plate_6']
8, có nghĩa là vào sau, ra trước. Vì vậy, sau khi bạn rửa ba chiếc đĩa, một người bạn sẽ mang một chiếc khác mà cô ấy dùng để tráng miệng và đặt nó lên trên cùng. Ngăn xếp của bạn bây giờ trông như thế nàystack = ['plate_1', 'plate_2', 'plate_6']
Điều này có nghĩa là
stack = ['plate_1', 'plate_2', 'plate_6']
9 sẽ là người tiếp theo được giặtTại sao không phải Danh sách?
Bây giờ chúng ta đã hiểu các khái niệm về hàng đợi và ngăn xếp, có vẻ như các danh sách sẽ phù hợp để triển khai các cấu trúc này trong Python. Rốt cuộc, chúng được sử dụng để đại diện cho hàng đợi các bài hát và chồng đĩa ở trên, phải không?
Danh sách không phải là cấu trúc dữ liệu tốt nhất cho hàng đợi hoặc ngăn xếp trong Python vì một số lý do. Đầu tiên, danh sách không an toàn theo luồng, điều đó có nghĩa là nếu một danh sách đang được truy cập và sửa đổi bởi nhiều luồng đồng thời, mọi thứ có thể không suôn sẻ và có thể bạn sẽ nhận được dữ liệu không nhất quán hoặc thông báo lỗi
Ngoài ra, danh sách không hiệu quả khi bạn cần chèn hoặc xóa một phần tử từ đầu bên trái của nó. Nếu bạn sử dụng
from collections import deque
queue = deque[]
print[queue]
0 để chèn một phần tử vào cuối bên phải hoặc from collections import deque
queue = deque[]
print[queue]
1 để xóa phần tử ngoài cùng bên phải, danh sách sẽ hoạt động bình thường. Tuy nhiên, khi bạn cố gắng thực hiện các thao tác này ở đầu bên trái, danh sách cần chuyển tất cả các phần tử khác sang bên phải, điều đó có nghĩa là kích thước của danh sách ảnh hưởng đến thời gian cần thiết để thực hiện các thao tác đó, dẫn đến hiệu suất kémSử dụng stack = ['plate_1', 'plate_2', 'plate_6']
2
stack = ['plate_1', 'plate_2', 'plate_6']
Đối tượng
from collections import deque
queue = deque[]
print[queue]
3 từ stack = ['plate_1', 'plate_2', 'plate_6']
1 là một đối tượng giống như danh sách hỗ trợ nối nhanh và bật lên từ cả hai phía. Nó cũng hỗ trợ các hoạt động an toàn theo luồng, tiết kiệm bộ nhớ và được thiết kế đặc biệt để hiệu quả hơn danh sách khi được sử dụng làm hàng đợi và ngăn xếpTên deque là viết tắt của double-end queue và nó được phát âm giống như "boong tàu". "
Tạo một đối tượng from collections import deque
queue = deque[]
print[queue]
3
from collections import deque
queue = deque[]
print[queue]
from collections import deque
queue = deque[]
print[queue]
3 lấy một đối số có thể lặp lại sẽ trở thành một đối tượng from collections import deque
queue = deque[]
print[queue]
3. Nếu không có gì được thông qua, nó sẽ trốngfrom collections import deque
queue = deque[]
print[queue]
deque[[]]
Nhưng chúng ta cũng có thể chuyển bất kỳ iterable nào tới
from collections import deque
queue = deque[]
print[queue]
3. Dưới đây, chúng ta có thể xem cách chuyển đổi danh sách, bộ dữ liệu, bộ, khóa và giá trị từ từ điển thành đối tượng from collections import deque
queue = deque[]
print[queue]
3songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ['song_1', 'song_2', 'song_3']
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}
deque_from_list = deque[songs_list]
deque_from_tuple = deque[songs_tuple]
deque_from_set = deque[songs_set]
deque_from_dict_keys = deque[songs_dict.keys[]]
deque_from_dict_values = deque[songs_dict.values[]]
print[deque_from_list]
print[deque_from_tuple]
print[deque_from_set]
print[deque_from_dict_keys]
print[deque_from_dict_values]
deque[['song_1', 'song_2', 'song_3']]
deque[['song_1', 'song_2', 'song_3']]
deque[['song_3', 'song_1', 'song_2']]
deque[['1', '2', '3']]
deque[['song_1', 'song_2', 'song_3']]
Vì vậy, bây giờ chúng ta đã khởi tạo đối tượng
from collections import deque
queue = deque[]
print[queue]
3, chúng ta có thể sử dụng các phương thức append và pop để chèn và xóa các mục từ đầu bên phảiqueue = deque[songs_list]
print[queue]
queue.append['song_4']
print[queue]
queue.pop[]
print[queue]
deque[['song_1', 'song_2', 'song_3']]
deque[['song_1', 'song_2', 'song_3', 'song_4']]
deque[['song_1', 'song_2', 'song_3']]
Lưu ý rằng
deque[[]]
1đã được chèn ở vị trí ngoài cùng bên phải và sau đó bị xóaThêm và xóa từ bên trái
Một trong những lợi thế lớn nhất của
from collections import deque
queue = deque[]
print[queue]
3 so với danh sách là khả năng nối thêm và xóa các mục từ đầu bên tráiTrong khi trong một danh sách, chúng tôi sử dụng phương pháp
deque[[]]
3, với một from collections import deque
queue = deque[]
print[queue]
3, chúng tôi có thể sử dụng phương pháp deque[[]]
5. Đây là cách mỗi cái hoạt độngqueue = ['song_3', 'song_4', 'song_5', 'song_6']
0_______9_______1Điều tương tự cũng xảy ra với việc xóa các mục ở đầu bên trái. Trong một danh sách, chúng tôi sử dụng phương thức
deque[[]]
6 với chỉ số 0 làm đối số, cho biết rằng mục đầu tiên sẽ bị xóa. Trong một from collections import deque
queue = deque[]
print[queue]
3, chúng ta có phương pháp deque[[]]
8 để thực hiện nhiệm vụ nàyqueue = ['song_3', 'song_4', 'song_5', 'song_6']
2queue = ['song_3', 'song_4', 'song_5', 'song_6']
3Như đã đề cập trước đó, một đối tượng
from collections import deque
queue = deque[]
print[queue]
3 hiệu quả hơn nhiều đối với các hoạt động này ở đầu bên trái, đặc biệt là khi kích thước của hàng đợi tăng lênTheo các khái niệm về hàng đợi và ngăn xếp, chúng tôi sử dụng phương pháp
deque[[]]
8 để xóa mục được chèn đầu tiên khỏi danh sách. Chúng tôi nối từ bên phải và xóa từ bên trái. đến trước về trướcTuy nhiên, cả hai phương pháp
deque[[]]
6 và deque[[]]
8 sẽ phát sinh lỗi nếu hàng đợi trống. Đó là một cách thực hành tốt để có các phương pháp này bên trong các mệnh đề songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ['song_1', 'song_2', 'song_3']
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}
deque_from_list = deque[songs_list]
deque_from_tuple = deque[songs_tuple]
deque_from_set = deque[songs_set]
deque_from_dict_keys = deque[songs_dict.keys[]]
deque_from_dict_values = deque[songs_dict.values[]]
print[deque_from_list]
print[deque_from_tuple]
print[deque_from_set]
print[deque_from_dict_keys]
print[deque_from_dict_values]
3 và songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ['song_1', 'song_2', 'song_3']
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}
deque_from_list = deque[songs_list]
deque_from_tuple = deque[songs_tuple]
deque_from_set = deque[songs_set]
deque_from_dict_keys = deque[songs_dict.keys[]]
deque_from_dict_values = deque[songs_dict.values[]]
print[deque_from_list]
print[deque_from_tuple]
print[deque_from_set]
print[deque_from_dict_keys]
print[deque_from_dict_values]
4 để ngăn ngừa lỗi. Chúng ta sẽ thấy một ví dụ sau trong bài viết nàyCuối cùng, chúng ta cũng có thể sử dụng phương thức
songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ['song_1', 'song_2', 'song_3']
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}
deque_from_list = deque[songs_list]
deque_from_tuple = deque[songs_tuple]
deque_from_set = deque[songs_set]
deque_from_dict_keys = deque[songs_dict.keys[]]
deque_from_dict_values = deque[songs_dict.values[]]
print[deque_from_list]
print[deque_from_tuple]
print[deque_from_set]
print[deque_from_dict_keys]
print[deque_from_dict_values]
5 để chèn nhiều phần tử vào hàng đợi. Phương pháp này có thể lặp lại. Đây là một ví dụqueue = ['song_3', 'song_4', 'song_5', 'song_6']
4queue = ['song_3', 'song_4', 'song_5', 'song_6']
5Các chức năng và phép lặp tích hợp trên hàng đợi
Cũng giống như danh sách, bộ dữ liệu và bộ, đối tượng
from collections import deque
queue = deque[]
print[queue]
3 cũng hỗ trợ các hàm dựng sẵn của PythonVí dụ: chúng ta có thể sử dụng
songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ['song_1', 'song_2', 'song_3']
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}
deque_from_list = deque[songs_list]
deque_from_tuple = deque[songs_tuple]
deque_from_set = deque[songs_set]
deque_from_dict_keys = deque[songs_dict.keys[]]
deque_from_dict_values = deque[songs_dict.values[]]
print[deque_from_list]
print[deque_from_tuple]
print[deque_from_set]
print[deque_from_dict_keys]
print[deque_from_dict_values]
7 để kiểm tra kích thước của một dequequeue = ['song_3', 'song_4', 'song_5', 'song_6']
6queue = ['song_3', 'song_4', 'song_5', 'song_6']
7Chúng ta có thể sử dụng hàm
songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ['song_1', 'song_2', 'song_3']
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}
deque_from_list = deque[songs_list]
deque_from_tuple = deque[songs_tuple]
deque_from_set = deque[songs_set]
deque_from_dict_keys = deque[songs_dict.keys[]]
deque_from_dict_values = deque[songs_dict.values[]]
print[deque_from_list]
print[deque_from_tuple]
print[deque_from_set]
print[deque_from_dict_keys]
print[deque_from_dict_values]
8 để sắp xếp một dequequeue = ['song_3', 'song_4', 'song_5', 'song_6']
8queue = ['song_3', 'song_4', 'song_5', 'song_6']
9Và chúng ta sử dụng hàm
songs_list = ['song_1', 'song_2', 'song_3']
songs_tuple = ['song_1', 'song_2', 'song_3']
songs_set = {'song_1', 'song_2', 'song_3'}
songs_dict = {'1': 'song_1', '2': 'song_2', '3': 'song_3'}
deque_from_list = deque[songs_list]
deque_from_tuple = deque[songs_tuple]
deque_from_set = deque[songs_set]
deque_from_dict_keys = deque[songs_dict.keys[]]
deque_from_dict_values = deque[songs_dict.values[]]
print[deque_from_list]
print[deque_from_tuple]
print[deque_from_set]
print[deque_from_dict_keys]
print[deque_from_dict_values]
9 để đảo ngược thứ tự của các mục bên trong một đối tượng from collections import deque
queue = deque[]
print[queue]
3stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
0stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
1Các hàm
deque[['song_1', 'song_2', 'song_3']]
deque[['song_1', 'song_2', 'song_3']]
deque[['song_3', 'song_1', 'song_2']]
deque[['1', '2', '3']]
deque[['song_1', 'song_2', 'song_3']]
1 và deque[['song_1', 'song_2', 'song_3']]
deque[['song_1', 'song_2', 'song_3']]
deque[['song_3', 'song_1', 'song_2']]
deque[['1', '2', '3']]
deque[['song_1', 'song_2', 'song_3']]
2 cũng được hỗ trợstack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
2_______10_______3Tất nhiên, chúng ta có thể lặp qua hàng đợi
stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
4stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
5Triển khai Hàng đợi
Bây giờ, hãy áp dụng phiên bản hàng đợi đơn giản hóa vào thực tế. Chúng tôi sẽ tiếp tục sử dụng ví dụ về hàng đợi các bài hát, có nghĩa là hàng đợi của chúng tôi sẽ tiếp tục nhận các bài hát mới khi nó phát các bài hát cũ nhất trong dòng và sau đó loại bỏ chúng. Mặc dù chúng tôi đang triển khai hàng đợi, nhưng chúng tôi có thể sử dụng các khái niệm tương tự để triển khai ngăn xếp theo cách rất giống nhau
Đầu tiên, chúng ta sẽ viết một hàm nhận đối tượng
from collections import deque
queue = deque[]
print[queue]
3 làm hàng đợi và danh sách các bài hát. Sau đó, chức năng chọn một bài hát ngẫu nhiên và thêm nó vào hàng đợi. Chức năng này cũng in bài hát nào đã được thêm cũng như hàng đợi hiện tại. Quá trình này sẽ diễn ra vô tậnstack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
6Bây giờ chúng tôi cần một chức năng để xóa các bài hát khi chúng được phát. Chức năng này sẽ không thực sự phát một bài hát vì mục tiêu chỉ là tạo ra một biểu diễn hoạt động của hàng đợi trong Python. Thay vào đó, hàm này nhận một hàng đợi, xóa phần tử ngoài cùng bên trái và in mục đã xóa và hàng đợi hiện tại. Nếu hàng đợi trống, hàm sẽ in ra
stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
7Tiếp theo, chúng ta sẽ tạo một danh sách các bài hát và khởi tạo một đối tượng
from collections import deque
queue = deque[]
print[queue]
3. Cuối cùng, chúng tôi sẽ sử dụng mô-đun deque[['song_1', 'song_2', 'song_3']]
deque[['song_1', 'song_2', 'song_3']]
deque[['song_3', 'song_1', 'song_2']]
deque[['1', '2', '3']]
deque[['song_1', 'song_2', 'song_3']]
5 của Python để chạy đồng thời cả hai chức năng. Đây là mã cuối cùngstack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
8Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ có một đầu ra như sau
stack = ['plate_1', 'plate_2', 'plate_3', 'plate_4', 'plate_5']
9Lưu ý rằng mã thêm các bài hát ở đầu bên phải của hàng đợi và xóa chúng ở đầu bên trái, tôn trọng thứ tự các bài hát do người dùng xác định. Ngoài ra, vì
from collections import deque
queue = deque[]
print[queue]
3 hỗ trợ đa luồng, chúng tôi không gặp vấn đề gì với hai chức năng truy cập và sửa đổi cùng một đối tượng đồng thờiPhần kết luận
Trong bài viết này, chúng tôi đã đề cập đến cách đối tượng
from collections import deque
queue = deque[]
print[queue]
3 từ stack = ['plate_1', 'plate_2', 'plate_6']
1 có thể là lựa chọn tuyệt vời để triển khai hàng đợi và ngăn xếp trong Python. Chúng tôi cũng đề cập đến những điều sau đâyCác khái niệm về hàng đợi và ngăn xếp
Tại sao danh sách không phải là lựa chọn tốt nhất trong trường hợp này
Cách sử dụng đối tượng
3from collections import deque queue = deque[] print[queue]
Triển khai phiên bản đơn giản hóa của hàng đợi hoạt động trong sản xuất
hướng dẫn python
Thông tin về các Tác giả
Otávio Simões Silveira
Otávio là một nhà kinh tế và nhà khoa học dữ liệu đến từ Brazil. Khi rảnh rỗi, anh ấy viết về Python và Khoa học dữ liệu trên internet. Bạn có thể tìm thấy anh ấy tại LinkedIn