preamble
Stacks, queues, and priority queues are very basic data structures, and Python, as a "coding efficient" language, has a good implementation of these basic data structures. In the business requirements development process, should not be repeated to create the wheel, today to look at some of the data structures have what to implement.
0x00 Stack
Stack is a LIFO (last in first out) data structure, there are into the stack (push), out of the stack (pop) two operations, and can only operate on the top element of the stack.
There are various data structures in Python that can be implemented as stacks.
1、list
A list is a built-in Python list data structure that supports the characteristics of a stack, with in-stack and out-stack operations. It's just that implementing stacks with lists doesn't work particularly well.
This is because the list is internally implemented as a dynamically expanding array. Expansion may be triggered when elements are added or subtracted. If you add or remove elements from the head of the list, it will also move the entire list.
If you want to use a list to implement a stack, you can use the list's append() (into the stack), pop() (out of the stack) method.
>>> s = []
>>> ('one')
>>> ('two')
>>> (3)
>>> s
['one', 'two', 3]
>>> ()
3
>>> ()
'two'
>>> ()
'one'
>>> ()
IndexError: pop from empty list
2、
The deque class is a two-ended queue. In Python it is a bi-directional list that can perform operations to add and remove elements at both ends at common times, which is very efficient, so it implements both stacks and queues.
If a stack is to be implemented in Python, then deque should be preferred over list.
The in-stack and out-stack methods of deque are also append() and pop() respectively.
>>> from collections import deque
>>> s = deque()
>>> ('eat')
>>> ('sleep')
>>> ('code')
>>> s
deque(['eat', 'sleep', 'code'])
>>> ()
'code'
>>> ()
'sleep'
>>> ()
'eat'
>>> ()
IndexError: pop from an empty deque
3、
As the name suggests, this is a stack. However, it is thread-safe, so if you want to use it in a concurrent environment, then you can choose to use LifoQueue.
It enters and exits the stack using put() and get(), where get() blocks when the LifoQueue is empty.
>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> ('eat')
>>> ('sleep')
>>> ('code')
>>> s
< object at 0x109dcfe48>
>>> ()
'code'
>>> ()
'sleep'
>>> ()
'eat'
>>> ()
# Blocking and waiting until the stack is not empty
0x01 Queue (Queue)
A queue is a FIFO (first in first out) data structure. It has two operations: in queue (enqueue) and out queue (dequeue), and it is also a constant time operation.
What data structures can be used to implement a queue in Python?
1、list
A list can implement a queue, but its queue-in and queue-out operations are not very efficient. Because a list is a dynamic list, when you perform an out operation at the head of the queue, the entire element is moved.
When using a list to implement a queue, append() is used to perform the in operation and the pop(0) method is used to perform the out operation at the head of the queue. Since the operation is performed on the first element of the list, all subsequent elements are shifted forward one bit. Therefore, using a list to implement a queue is not recommended.
>>> q = []
>>> ('1')
>>> ('2')
>>> ('three')
>>> (0)
'1'
>>> (0)
'2'
>>> (0)
'three'
>>> (0)
IndexError: pop from empty list
2、
From the above we already know that a deque is a two-way list that can add and delete operations at both ends of the list in constant time. So using deque to implement a queue is very efficient.
The deque in operation uses the append() method and the out operation uses the popleft() method.
>>> from collections import deque
>>> q = deque()
>>> ('eat')
>>> ('sleep')
>>> ('code')
>>> q
deque(['eat', 'sleep', 'code'])
# Use popleft to get out of line
>>> ()
'eat'
>>> ()
'sleep'
>>> ()
'code'
>>> ()
IndexError: pop from an empty deque
3、
Similarly, if you want to use a queue in a concurrent environment, then choose thread-safe.
Similar to LifoQueue, the queue in and queue out operations are put () and get () methods, get () in the queue will be empty will continue to block until an element into the queue.
>>> from queue import Queue
>>> q = Queue()
>>> ('eat')
>>> ('sleep')
>>> ('code')
>>> q
< object at 0x110564780>
>>> ()
'eat'
>>> ()
'sleep'
>>> ()
'code'
# Queue is empty do not execute wait
>>> q.get_nowait()
_queue.Empty
>>> ('111')
>>> q.get_nowait()
'111'
>>> ()
# when the queue is empty，It blocks until the queue is not empty.
4、
Multi-process version of the queue. If the queue is to be used in a multi-process environment, then it should be selected.
Similarly, its in-queue and out-queue operations are put() and get(). get() method in the queue is empty, will keep blocking until the queue is not empty.
>>> from multiprocessing import Queue
>>> q = Queue()
>>> ('eat')
>>> ('sleep')
>>> ('code')
>>> q
< object at 0x110567ef0>
>>> ()
'eat'
>>> ()
'sleep'
>>> ()
'code'
>>> q.get_nowait()
_queue.Empty
>>> ()
# when the queue is empty，It blocks until the queue is not empty.
0x02 PriorityQueue
A nearly sorted sequence can use a data structure such as a priority queue, which efficiently acquires the largest or smallest element.
Priority queues are often used in scheduling problem scenarios. It mainly has operations to get the maximum or minimum value and queue entry operations.
1、list
A priority queue can be implemented using a list, but it is not efficient. This is because you need to sort the list when you want to get the most value, and then get the most value again. Once a new element is added, it has to be sorted again to get the most value. So it is not recommended.
2、heapq
In general, priority queues are implemented using a data structure called a heap. And heapq is the implementation of heap in Python standard library. heapq implements minimal heap by default.
The in-queue operation uses heappush() and the out-queue operation uses heappop().
>>> import heapq >>> q = [] >>> (q, (2, 'code')) >>> (q, (1, 'eat')) >>> (q, (3, 'sleep')) >>> q [(1, 'eat'), (2, 'code'), (3, 'sleep')] >>> while q: next_item = (q) print(next_item) (1, 'eat') (2, 'code') (3, 'sleep')
3、
internally encapsulates the heapq, the difference being that it is thread-safe. You should choose to use PriorityQueue in a concurrent environment.
>>> from queue import PriorityQueue >>> q = PriorityQueue() >>> ((2, 'code')) >>> ((1, 'eat')) >>> ((3, 'sleep')) >>> while not (): next_item = () print(next_item) (1, 'eat') (2, 'code') (3, 'sleep')
0x03 To summarize
Many of the basic data structures that are already implemented in Python should not be duplicated to build wheels, but should be chosen to fulfill business needs.
It is a bidirectional linked table, which can be used to implement Stack and Queue in a single-threaded scenario. and the heapq module helps us to implement an efficient priority queue.
If you want to use Stack, Queue and PriorityQueue in the case of multiple concurrency, then you should use the queue module class:
- Implementing Stack's
- Implementing Queue's or
- PriorityQueue implementation
- All these classes above have put() and get() methods and get() blocks when the stack/queue is empty.
0x04 Learning Materials
Python Tricks: A Buffet of Awesome Python Features
——Dan Bader
Well, the above is the entire content of this article, I hope that the content of this article on your learning or work has a certain reference learning value, thank you for my support.