Implementation of Stack Queue and Priority Queue in Python

Preface

Stacks, queues, and priority queues are all very basic data structures. Python, as a "coding efficient" language, has a good implementation of these basic data structures. In the process of business requirements development, you should not build wheels repeatedly. Today, let's take a look at the implementations of some data structures.

0x00 Stack (Stack)

Stack is a kind of LIFO (last in first out) data structure, which has two operations: stack entry (push) and stack exit (pop), and can only operate the top element of stack.
In Python, there are many data structures that can implement stacks.

1. list

list is a built-in list data structure of Python, which supports stack characteristics, including stack-in and stack-out operations. However, the stack performance with list is not particularly good.

Because list is internally implemented by a dynamically expanded array. Expansion operations may be triggered when elements are added or subtracted. If you add or subtract elements at the head of list, the whole list will also be moved.

If you want to use list to implement a stack, you can use append () (on stack) and pop () (off stack) methods of list.

>>> s = []
>>> s.append('one')
>>> s.append('two')
>>> s.append(3)
>>> s
['one', 'two', 3]
>>> s.pop()
3
>>> s.pop()
'two'
>>> s.pop()
'one'
>>> s.pop()
IndexError: pop from empty list

2. collections. deque

The deque class is a two-ended queue. In Python, it is a bidirectional list, which can add and delete elements at both ends in common time, which is very efficient, so it can implement both stack and queue.

If you want to implement 1 stack on Python, you should prefer deque over list.

deque's stack-in and stack-out methods are also append () and pop (), respectively.

>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')
>>> s
deque(['eat', 'sleep', 'code'])
>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'
>>> s.pop()
IndexError: pop from an empty deque

3. queue. LifoQueue

As the name implies, this is a stack. However, it is thread-safe, and if you want to use it in a concurrent environment, you can choose to use LifoQueue.

It uses put () and get (), where get () blocks when LifoQueue is empty.

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')
>>> s
<queue.LifoQueue object at 0x109dcfe48>
>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'
>>> s.get()
#  Blocking union 1 Wait until the stack is not empty 

0x01 queue (Queue)

Queue is an FIFO (first in, first out) data structure. It has two operations: queuing (enqueue) and queuing (dequeue), and it is also a constant time operation.
What data structures can be used to implement a queue in Python?

1. list

list can realize one queue, but its queuing and queuing operations are not very efficient. Because list is a dynamic list, the entire element is moved when the queue head is dequeued.

When using list to implement a queue, append () is used to queue in, and pop (0) method is used to queue out at the head of the queue. Since the operation is performed on the first element of list, subsequent elements are moved forward by 1 bit. Therefore, it is not recommended to implement queues with list.

>>> q = []
>>> q.append('1')
>>> q.append('2')
>>> q.append('three')

>>> q.pop(0)
'1'
>>> q.pop(0)
'2'
>>> q.pop(0)
'three'
>>> q.pop(0)
IndexError: pop from empty list

2. collections. deque

From the above, we already know that deque is a bidirectional list, which can be added and deleted at both ends of the list for a constant time. Therefore, it is very efficient to implement one queue with deque.

The deque queue-in operation uses the append () method, and the queue-out operation uses the popleft () method.

>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')
>>> q
deque(['eat', 'sleep', 'code'])
#  Use popleft Out of the team 
>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'
>>> q.popleft()
IndexError: pop from an empty deque

3. queue. Queue

Similarly, if you want to use queues in a concurrent environment, choose thread-safe queue. Queue.

Similar to LifoQueue, queuing and queuing operations are put () and get () methods, respectively, and get () blocks until an element is queued when the queue is empty.

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<queue.Queue object at 0x110564780>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
#  Do not wait when the queue is empty 
>>> q.get_nowait()
_queue.Empty
>>> q.put('111')
>>> q.get_nowait()
'111'
>>> q.get()
#  When the queue is empty, the 1 Block straight until the queue is not empty 

4. multiprocessing. Queue

Queue of multi-process version. If you want to use queues in a multi-process environment, you should choose multiprocessing. Queue.

Similarly, its queuing and queuing operations are put () and get (), respectively. The get () method is empty in the queue and blocks until the queue is not empty.

>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<multiprocessing.queues.Queue object at 0x110567ef0>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
>>> q.get_nowait()
_queue.Empty
>>> q.get()
#  When the queue is empty, the 1 Block straight until the queue is not empty 

0x02 Priority Queue (PriorityQueue)

Priority queue can be used in a nearly sorted sequence, which can efficiently obtain the largest or smallest elements.

Priority queues are often used in scheduling problem scenarios. It mainly includes the operation of obtaining the maximum or minimum value and queuing operation.

1. list

One priority queue can be implemented with list, but it is not efficient. Because you need to sort when you want to get the maximum value, and then get the maximum value. 1 Once new elements are added, when the maximum value is obtained again, it is necessary to reorder. Therefore, it is recommended to use.

2. heapq

1 Generally speaking, priority queues are implemented by using the data structure of heap. heapq is the implementation of heap in Python standard library. heapq implements a minimum heap by default.

heappush () is used for queue entry and heappop () is used for queue exit.

>>> import heapq
>>> q = []
>>> heapq.heappush(q, (2, 'code'))
>>> heapq.heappush(q, (1, 'eat'))
>>> heapq.heappush(q, (3, 'sleep'))
>>> q
[(1, 'eat'), (2, 'code'), (3, 'sleep')]
>>> while q:
	next_item = heapq.heappop(q)
	print(next_item)

	
(1, 'eat')
(2, 'code')
(3, 'sleep')

3. queue.PriorityQueue

queue. PriorityQueue encapsulates heapq internally, except that it is thread safe. You should choose to use PriorityQueue in a concurrent environment.

>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((2, 'code'))
>>> q.put((1, 'eat'))
>>> q.put((3, 'sleep'))
>>> while not q.empty():
	next_item = q.get()
	print(next_item)

(1, 'eat')
(2, 'code')
(3, 'sleep')

0x03 Summary 1

Many of the basic data structures are already implemented in Python, and we should not duplicate the wheels; We should choose these data structures to meet the business requirements.
collections. deque is a bi-linked list, which can be used to implement Stack and Queue in the case of single thread. The heapq module can help us realize efficient priority queue.

If you want to use Stack, Queue, and PriorityQueue with multiple concurrency, you should choose the following class of queue module:

queue. LifoQueue for Stack queue. Queue or multiprocessing. Queue that implements Queue queue. PriorityQueue for PriorityQueue These classes all 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