Danh sách này là một trong những bộ sưu tập dữ liệu được sử dụng thường xuyên và quen thuộc nhất đối với bất kỳ ai thường xuyên viết mã bằng Python. Chúng là những cấu trúc dữ liệu tuyệt vời với nhiều chức năng hữu ích cho phép người dùng thêm, xóa và sắp xếp các mục. Không còn nghi ngờ gì nữa, danh sách này là lựa chọn phù hợp cho nhiều tình huống, nhưng Python cũng cung cấp các lựa chọn thay thế phù hợp hơn với các tình huống nhất định
Ví dụ: danh sách có thể không phải là cấu trúc dữ liệu tối ưu để triển khai các kiểu dữ liệu trừu tượng ngăn xếp hoặc hàng đợi. Điều này là do các danh sách không an toàn cho luồng, điều đó có nghĩa là mọi thứ có thể sai nếu nhiều luồng cố gắng truy cập và sửa đổi cùng một phần tử cùng một lúc. Điều này mang lại cho chúng tôi thông báo lỗi và dữ liệu không nhất quán
Kiểu dữ liệu trừu tượng hàng đợi là một trong những cấu trúc dữ liệu phổ biến nhất cho các vấn đề về dữ liệu nhập trước xuất trước [FIFO]. Một cách mà chúng ta có thể triển khai hàng đợi một cách hiệu quả là sử dụng danh sách liên kết kép. Đây là những lý tưởng cho các ứng dụng mà bạn cần truy cập nhanh vào cả phần tử đầu tiên và phần tử cuối cùng của hàng đợi
Trong bài đăng trên blog này, chúng ta sẽ xem xét hàng đợi Python [cấu trúc dữ liệu hàng đợi hai đầu được cung cấp cùng với thư viện chuẩn Python]. Chúng ta sẽ xem xét deque là gì và chúng ta sẽ đề cập đến cách sử dụng triển khai deque trong Python để tạo và thao tác cấu trúc dữ liệu
Deque trong Python là gì?
Deque, còn được gọi là hàng đợi hai đầu [phát âm là "bộ bài"], là một bộ sưu tập các mục được sắp xếp theo thứ tự nơi bạn có thể thêm các mục mới vào phía trước hoặc phía sau hàng đợi. Deques tương tự như danh sách, nhưng chúng hiệu quả hơn trong việc thêm hoặc xóa các mục từ đầu hoặc cuối danh sách
Deques thường được sử dụng như một hàng đợi, nhưng bạn cũng có thể sử dụng chúng như một ngăn xếp
Khi được sử dụng làm hàng đợi, chúng tôi thêm các mục vào một đầu của hàng đợi [thường là phía sau] và xóa chúng khỏi đầu kia [thường là phía trước]. Điều này thể hiện chất lượng xác định của hàng đợi trong đó các mục là Nhập trước xuất trước [FIFO]
Khi được sử dụng như một ngăn xếp, chúng tôi thêm các mục vào một đầu của hàng đợi [thường là phía sau] và loại bỏ chúng khỏi cùng một đầu [cũng thường là phía sau]. Điều này có nghĩa là hàng đợi có thể đại diện cho hành vi Nhập sau xuất trước [LIFO] của một ngăn xếp.
Python triển khai deque dưới dạng danh sách liên kết đôi. Mỗi nút trong danh sách có một tham chiếu đến nút trước đó và nút tiếp theo. Nút đầu có tham chiếu đến nút đuôi và nút đuôi có tham chiếu đến nút đầu
Tại sao nên sử dụng Python Deque?
Danh sách không tối ưu khi bạn cần thêm bớt một phần tử ở phía trước [chỉ số 0]. Trong những trường hợp này, toàn bộ danh sách phải được chuyển sang bên phải để tạo khoảng trống cho phần tử mới được thêm vào hoặc danh sách phải được chuyển sang bên trái để lấp đầy khoảng trống từ phần tử mới bị xóa. Trong cả hai trường hợp, thời gian dành cho việc này tăng tuyến tính với kích thước danh sách. Điều này có nghĩa là các hoạt động này có độ phức tạp thời gian là O[n] hoặc độ phức tạp thời gian tuyến tính
Tuy nhiên, nếu bạn sử dụng. append[] để thêm một phần tử vào cuối danh sách, thì đây sẽ là một thao tác rất nhanh với độ phức tạp về thời gian không đổi hoặc O[1]. Tương tự, nếu bạn xóa phần tử ngoài cùng bên phải bằng cách sử dụng. pop[], thì phương thức này cũng nhanh như vậy.
Vui lòng giải quyết các sự cố liên quan đến danh sách khi cố gắng truy cập các phần tử phía trước. Điều này là do deques được triển khai dưới dạng danh sách liên kết kép với các thao tác append và pop ổn định và nhanh như nhau. Điều này có nghĩa là deques có thể cung cấp cho chúng ta các phần bổ sung và bật lên an toàn cho luồng và tiết kiệm bộ nhớ từ hai bên của hàng đợi với độ phức tạp về thời gian xấp xỉ không đổi hoặc O[1]
Đặc điểm Deque của Python
Loại dữ liệu trừu tượng hàng đợi tuyến tính tổng quát yêu cầu việc chèn phải diễn ra ở một đầu [thường là mặt sau] và xóa ở đầu kia [thường là mặt trước]. Điều này thể hiện đặc tính FIFO của hàng đợi và nó có thể dẫn đến một số hạn chế đối với việc chèn và xóa phần tử.
Tuy nhiên, hàng đợi Python cho phép chúng ta truy cập vào cả hai đầu của hàng đợi để chèn và xóa
Sau đây là các đặc điểm của mã Python
- Deques cho phép nối và bật hiệu quả bộ nhớ và an toàn luồng từ hai bên của hàng đợi với độ phức tạp thời gian gần như không đổi ở hai đầu, đó là O[1]
- Deques có thể được triển khai hiệu quả với nhiều cấu trúc dữ liệu, bao gồm mảng, danh sách được liên kết và cây
- Deques có thể được sử dụng để thay thế cho các danh sách trong nhiều thuật toán và cấu trúc dữ liệu
- Deques có hiệu suất trường hợp xấu nhất có thể dự đoán được hơn so với danh sách
- Deques dễ sử dụng 'chính xác' hơn so với danh sách
- Danh sách linh hoạt hơn danh sách
- Deques hiệu quả hơn danh sách trong nhiều tình huống
- Deques có thể được xoay sang trái hoặc phải một cách hiệu quả, đây được gọi là "bộ đệm tuần hoàn"
- Deques là một lựa chọn tốt để theo dõi các phần tử đầu và đuôi của danh sách
- Deques có thể dễ dàng đảo ngược mà không cần tạo danh sách mới hoặc sao chép dữ liệu hiện có
- Deques tiêu thụ ít bộ nhớ hơn danh sách khi lưu trữ số lượng lớn phần tử
- Deques có thể được sử dụng làm hàng đợi FIFO hoặc ngăn xếp LIFO
- Deque là một hàng đợi hai đầu, có nghĩa là nó có thể được sử dụng như một ngăn xếp hoặc một hàng đợi
- Deque là cấu trúc dữ liệu tuyến tính hỗ trợ chèn và xóa nhanh ở cả hai đầu
- Một deque thường được triển khai dưới dạng một mảng động, có thể thay đổi kích thước khi cần
- Một deque có thể được sử dụng để triển khai các cấu trúc dữ liệu khác, bao gồm ngăn xếp, hàng đợi hoặc hàng đợi ưu tiên
Bây giờ chúng ta đã thấy các đặc điểm của deque, hãy xem các loại deque trong Python
Các loại Python Deque
Tùy thuộc vào cách mà hoạt động bị hạn chế, deques có thể là một trong hai loại
- Deque hạn chế đầu vào
- Deque giới hạn đầu ra
Deque hạn chế đầu vào
Một deque giới hạn đầu vào là một cấu trúc dữ liệu cho phép xóa các phần tử ở hai đầu của deque, nhưng chỉ cho phép chèn các phần tử ở một đầu của deque
Hàng đợi giới hạn đầu vào thường được sử dụng trong các ứng dụng mà chúng tôi yêu cầu hàng đợi, nhưng thứ tự của các phần tử không quan trọng. Ví dụ: chúng ta có thể sử dụng hàng đợi giới hạn đầu vào để lưu trữ các tác vụ CPU yêu cầu xử lý. CPU có thể loại bỏ và xử lý tác vụ đầu tiên từ phía trước hàng đợi mà không cần quan tâm đến thứ tự của các tác vụ còn lại trong hàng đợi
Các thiết bị giới hạn đầu vào cũng thường được sử dụng trong các ứng dụng có không gian hạn chế. Điều này là do chúng chỉ yêu cầu hai con trỏ [một cho mặt trước và một cho mặt sau của deque] và không yêu cầu bộ nhớ liền kề để lưu trữ các phần tử deque trong một mảng
Deque giới hạn đầu ra
Một deque giới hạn đầu ra là một cấu trúc dữ liệu cho phép chèn các phần tử từ hai phía của deque, nhưng chỉ cho phép xóa các phần tử từ một đầu của deque
Loại hàng đợi này có thể hữu ích trong các trường hợp bạn cần tính linh hoạt của hàng đợi FIFO, nhưng bạn cũng cần xóa các phần tử ở phía sau hàng đợi. Ví dụ: nếu bạn đã triển khai ngăn xếp LIFO bằng cách sử dụng hàng đợi giới hạn đầu ra, thì bạn có thể đẩy [chèn] và bật [xóa] các phần tử ở đầu ngăn xếp, là mặt sau của hàng đợi
Nhìn chung, cấu trúc dữ liệu giới hạn đầu ra là cấu trúc dữ liệu linh hoạt mà bạn có thể sử dụng trong nhiều tình huống khác nhau. Nếu bạn cần chức năng của hàng đợi nhưng cũng cần sự linh hoạt để xóa từ phía sau hàng đợi, thì loại hàng đợi này sẽ hợp lý.
Các tính năng của một Deque
Deques cho phép chúng tôi thực hiện một số loại hoạt động
- Thêm các mục
- mục nhạc pop
- Truy cập các mục
- Xoay các mục
Rõ ràng hơn, các đối tượng này hỗ trợ các phương thức Python sau
phương pháp
Sự miêu tả
nối thêm []
Thêm phần tử vào bên phải của bộ bài
appendleft[]
Thêm phần tử vào bên trái của bộ bài
thông thoáng[]
Xóa tất cả các phần tử khỏi bộ bài
sao chép[]
Tạo một bản sao của deque
đếm[]
Đếm số lần xuất hiện của một phần tử đã cho
gia hạn[]
Mở rộng phía bên phải của bộ bài bằng cách thêm các yếu tố
gia hạn trái[]
Mở rộng phía bên trái của bộ bài bằng cách thêm các yếu tố
mục lục[]
Trả về vị trí của một phần tử trong hàng đợi
chèn[]
Chèn một phần tử vào một vị trí nhất định
nhạc pop[]
Xóa và trả về một phần tử từ đầu bên phải của hàng đợi
popleft[]
Xóa và trả về một phần tử từ đầu bên trái của hàng đợi
gỡ bỏ[]
Xóa lần xuất hiện đầu tiên của giá trị đã cho
đảo ngược[]
Đảo ngược thứ tự các phần tử trong deque
quay[]
Xoay bộ bài dựa trên các đối số đã cho
maxlen[]
Trả về kích thước tối đa của hàng đợi
Bảng trên cho thấy các thao tác khác nhau mà chúng ta có thể thực hiện trên một đối tượng phù hợp. Trong phần tiếp theo, chúng ta sẽ tạo một đối tượng deque và thực hiện các thao tác này trong Python
Thao tác trên Python Deque
Có sẵn dưới dạng một lớp trong mô-đun bộ sưu tập của thư viện chuẩn Python. Chúng tôi có thể nhập Python deque từ mô-đun bộ sưu tập và chúng tôi có thể thực hiện các thao tác khác nhau trên một đối tượng deque. Trong phần tiếp theo, chúng ta sẽ khám phá một ví dụ về Python
Chèn các phần tử vào Python Deque
Đầu tiên, hãy tạo một hàng đợi trống và sau đó thực hiện một số thao tác
from collections import deque
seq = deque[] #create an empty deque
print[seq] #print the deque
seq.append[1] #use append[] to insert element at right end
print['The deque after appending right:',seq] #print the deque
seq.appendleft[2] #use appendleft[] to insert element at left end
print['The deque after appending left:', seq] #print the deque
seq.extend[[4,5]] #use extend[] to insert several elements at the right end
print['The deque after extending right:', seq] #print the deque
seq.extendleft[[6,7]] #use extendleft[] to insert elements at the left end
print['The deque after extending left:', seq] #print the deque
seq.insert[3,2] #use insert[] to insert the value 2 at 4th position
print['The deque after inserting element:', seq] #print the dequeĐoạn mã trên xuất ra như sau
deque[[]]
The deque after appending right: deque[[1]]
The deque after appending left: deque[[2, 1]]
The deque after extending right: deque[[2, 1, 4, 5]]
The deque after extending left: deque[[7, 6, 2, 1, 4, 5]]
The deque after inserting element: deque[[7, 6, 2, 2, 1, 4, 5]]Vậy chuyện gì đã xảy ra ở đây? . Trong bước thứ hai, chúng ta đã tạo một thể hiện mới của đối tượng deque không có giá trị, nghĩa là chúng ta đã tạo một deque trống.
Sau đó, chúng tôi đã sử dụng. append[] để thêm một phần tử vào phía bên phải của hàng đợi. Sau đó, chúng tôi đã sử dụng. appendleft[] để thêm phần tử '2' vào phía bên trái của hàng đợi.
Tương tự, chúng tôi đã sử dụng. expand[] để thêm các phần tử [4,5] vào phía bên phải của hàng đợi và chúng tôi đã sử dụng. phương thức expandleft[] để thêm các phần tử [7,6] vào phía bên trái của hàng đợi. Ở bước cuối cùng, chúng tôi đã sử dụng. phương thức insert[] để thêm phần tử '2' vào vị trí thứ tư [là chỉ số 3]
Bây giờ, hãy xem cách xóa các phần tử khỏi đối tượng deque.
Xóa các phần tử khỏi Python Deque
Bây giờ, chúng ta sẽ đề cập đến các phương pháp khác nhau để xóa các phần tử khỏi hàng đợi Python
from collections import deque
seq = deque[[1,2,3,4,5,6]] #create a new deque
print[seq] #print the deque
seq.pop[] #use pop[] to remove right most element
print[seq] #print the deque
seq.popleft[] #use popleft[] to remove leftmost element
print[seq] #print the deque
seq.remove[3] #use remove[] to remove the given element
print[seq] #print the deque
seq.clear[] #use clear[] to clear all elements in the deque
print[seq] #print the dequeĐoạn mã trên xuất ra như sau
deque[[1, 2, 3, 4, 5, 6]]
deque[[1, 2, 3, 4, 5]]
deque[[2, 3, 4, 5]]
deque[[2, 4, 5]]
deque[[]]Trong bước đầu tiên, chúng tôi đã nhập lớp deque từ mô-đun bộ sưu tập và sau đó xác định một đối tượng deque mới. Sau đó, chúng tôi đã sử dụng. pop[] để xóa phần tử ngoài cùng bên phải khỏi đối tượng hàng đợi. Chúng tôi cũng đã sử dụng. phương thức popleft[] để loại bỏ phần tử ngoài cùng bên trái. Sau đó, chúng tôi đã sử dụng. phương thức remove[] để xóa phần tử '3' bằng cách truyền đối số. Cuối cùng, chúng tôi đã sử dụng. clear[] để xóa tất cả các phần tử trong deque, để lại cho chúng ta một đối tượng deque trống.
Trong phần tiếp theo, chúng ta sẽ khám phá thêm các hoạt động mà Deque cung cấp
Các hoạt động khác trên Python Deque
Ngoài việc thêm bớt phần tử, chúng ta có thể thực hiện các thao tác khác như đếm phần tử, tìm chỉ số của phần tử, xoay đối tượng thích hợp, v.v. Đoạn mã sau đây cho thấy cách các hoạt động này hoạt động
from collections import deque
seq = deque[[1,1,2,3,4,5,6]] #create a new deque
print[seq] #print the deque
a = seq.count[1] #count the occurrence of 1
print['Count of 1 is:', a] #print the count of 1
b = seq.copy[] #copy the deque object using count[]
print[b] #print the deque
c = seq.index[2] #get the index of the element 2
print['The index of 2:', c] #print the index
seq.reverse[] #reverse the deque object using reverse[]
print[seq] #print the deque
seq.rotate[1] #rotate the deque object to the right
print[seq] #print the dequeĐoạn mã trên xuất ra như sau
deque[[1, 1, 2, 3, 4, 5, 6]]
Count of 1 is: 2
deque[[1, 1, 2, 3, 4, 5, 6]]
The index of 2: 2
deque[[6, 5, 4, 3, 2, 1, 1]]
deque[[1, 6, 5, 4, 3, 2, 1]]Trong bước đầu tiên, chúng tôi đã nhập lớp deque từ mô-đun bộ sưu tập và sau đó tạo một đối tượng deque. Tiếp theo, chúng tôi đã sử dụng. Count[] để đếm số lần xuất hiện của '1' trong hàng đợi và chúng tôi đã in kết quả. Sau đó chúng tôi đã sử dụng. copy[] để sao chép đối tượng hàng đợi vào một biến, 'b'. chúng tôi đã sử dụng. index[] để trả về chỉ mục của một phần tử ngẫu nhiên, '2'. Chúng tôi cũng đã sử dụng. reverse[] để đảo ngược đối tượng hàng đợi, và cuối cùng chúng ta xoay hàng đợi sang bên phải bằng lệnh. rotate[] phương pháp và một đối số của '1'
Đây là một số thao tác có thể thực hiện trên một đối tượng nha. Các phương thức khác mà chúng ta có thể sử dụng với triển khai Python bao gồm. tối đa[],. len[] và. đảo ngược[]
Phần kết luận
Mã Python là một cấu trúc dữ liệu quan trọng với nhiều ứng dụng. Trong bài viết này, chúng ta đã thảo luận deque là gì, cùng với các thao tác khác nhau mà chúng ta có thể thực hiện trên một đối tượng deque. Deques chủ yếu được sử dụng khi
- Chúng tôi cần độ phức tạp thời gian nhanh
- Chúng ta cần một dấu chân bộ nhớ nhỏ
- Chúng tôi muốn tạo ngăn xếp LIFO
- Chúng tôi muốn tạo hàng đợi FIFO
Để tìm hiểu thêm về cách trở thành chuyên gia Python, hãy xem bài viết Giới thiệu về viết mã trong Python của chúng tôi, cũng như Câu hỏi và trả lời phỏng vấn Python hàng đầu
Các câu hỏi thường gặp
1. Hàng đợi và hàng đợi trong Python là gì?
Hàng đợi là một kiểu dữ liệu trừu tượng đại diện cho một danh sách các phần tử có thứ tự FIFO. Hàng đợi là cấu trúc dữ liệu Python tích hợp đại diện cho hàng đợi hai đầu trong đó các phần tử có thể được thêm hoặc xóa ở một trong hai đầu
2. Nó có phải là Python Deque a List không?
Không, nó không phải là một danh sách. Hàng đợi là cấu trúc dữ liệu riêng của nó, tương tự như danh sách nhưng có thêm chức năng
3. Deque có tốt hơn hàng đợi trong Python không?
Không có câu trả lời dứt khoát cho câu hỏi này vì nó phụ thuộc vào nhu cầu cụ thể của chương trình. Tuy nhiên, nói chung, deque [hàng đợi hai đầu] có thể linh hoạt hơn hàng đợi thông thường vì nó cho phép thêm và xóa hiệu quả ở cả phía trước và phía sau hàng đợi
4. Tại sao chúng ta sử dụng Deque?
Hàng đợi được sử dụng khi bạn cần cấu trúc dữ liệu giống hàng đợi cho phép chèn và xóa nhanh ở cả mặt trước và mặt sau của cấu trúc dữ liệu
5. Làm cách nào để sử dụng Deque làm ngăn xếp trong Python?
Có hai cách để sử dụng một con trăn và sau đó là một ngăn xếp. Cách đầu tiên là sử dụng các phương thức append[] và pop[]. Cách thứ hai là sử dụng các phương thức appendleft[] và popleft[]