Deque in Python: Implementing efficient queues and stacks
WBOY
Release： 2023-04-12 21:46:06
forward
2459 people have browsed it
Deque in Python is a low-level, highly optimized double-ended queue, useful for implementing elegant and efficient Pythonic queues and stacks, which are the most common list-based data types in computing.
In this article, Mr. Yun Duo will learn the following together with you:
Start using deque
Effectively pop up and append elements
Access deque Any element in
Use deque to build an efficient queue
Start using Deque
The operation of appending elements to the right end of the Python list and popping elements is generally very efficient. If time complexity is expressed in Big O, then we can say that they are O(1). When Python needs to reallocate memory to increase the underlying list to accept new elements, these operations will slow down and the time complexity may become O(n).
In addition, the operations of appending and popping elements to the left end of the Python list are also very inefficient, with a time complexity of O(n).
Since lists provide .append() and .pop() operations, they can be used as stacks and queues. The performance issues of appending and popping operations on the left and right ends of the list will greatly affect the overall performance of the application.
Python’s deque was the first data type added to the collections module as early as Python 2.4. This data type is specifically designed to overcome the efficiency issues of .append() and .pop() in Python lists.
Deques are sequence-like data types designed as a generalization of stacks and queues. They support memory-efficient and fast append and pop operations on both ends of the data structure.
Append and pop operations on both ends of a deque object are stable and equally efficient because the deque is implemented as a doubly linked list. Additionally, append and pop operations on deque are also thread-safe and memory-efficient. These features make deque particularly useful for creating custom stacks and queues in Python.
If you need to save the last seen element list, you can also use deque, because the maximum length of deque can be limited. If we do this, then once the deque is full, it will automatically discard the elements at one end when we add new elements at the other end.
The following is a summary of the main features of deque:
Stores elements of any data type
Is a variable data type
Supports in The member operations of the operator
support indexing, such as a_deque[i]
does not support slicing, such as a_deque[0:2]
supports sequences and iterable objects. Built-in functions for operations, such as len(), sorted(), reversed(), etc.
Does not support inplace sorting
Supports normal iteration and reverse iteration
Supports the use of pickle
Ensure fast, memory efficient, and thread-safe pop and append operations on both ends
Creating a deque instance is relatively simple. Just import deque from the collection and call it with an optional iterator as argument.
If you instantiate deque without providing iterable as a parameter, you will get an empty deque. If an iterable is provided and entered, the deque initializes a new instance with its data. Initialization proceeds from left to right using deque.append().
Deque initializer requires the following two optional parameters.
iterable An iterator that provides initialization data.
maxlen is an integer specifying the maximum length of deque.
As mentioned before, if you don't provide an iterable, then you will get an empty deque. If you provide a value for maxlen, then your deque will only store the items up to maxlen.
Finally, you can also use unordered iterable objects, such as collections, to initialize deque. In these cases, there will be no predefined order of elements in the final deque.
Efficiently popping and appending elements
The most important difference between Deque and List is that the former can perform efficient appending and popping operations at both ends of the sequence. The Deque class implements specialized .popleft() and .appendleft() methods to directly operate on the left end of the sequence.
Here, use .popleft() and .appendleft() to pop up and increase the left end value of numbers respectively. These methods are designed for deque, and list has no such method.
Deque also provides .append() and .pop() methods like list to operate on the right end of the sequence. However, the behavior of .pop() is different.
>>> from collections import deque
>>> numbers = deque([1, 2, 3, 4])
>>> numbers.pop()
4
>>> numbers.pop(0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: pop() takes no arguments (1 given)
Copy after login
Here, .pop() removes and returns the last element in the deque container. This method does not accept an index as a parameter, so it cannot be used to remove arbitrary items from the deque. You can only use it to remove and return the rightmost item.
We think deque is a doubly linked list. Therefore, each item in a given deque container holds a reference (pointer) to the previous and next item in the sequence.
Double linked lists make the operation of adding and popping elements from both ends simple and efficient, because only the pointers need to be updated, therefore, the two operations have similar performance, both are O(1). They are also predictable in terms of performance because there is no need to reallocate memory and move existing items to accept new items.
>>> from collections import deque
>>> numbers = deque([1, 2, 3, 4, 5])
>>> numbers[1:3]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: sequence index must be integer, not 'slice'
Copy after login
Deque支持索引，却不支持分片。通常来说在一个链表上执行切片非常低效。
虽然 deque 与 list 非常相似，但 list 是基于数组的，而 deque 是基于双链表的。
The above is the detailed content of Deque in Python: Implementing efficient queues and stacks. For more information, please follow other related articles on the PHP Chinese website!
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
