What are priority queue and deque in Python?
In this type of queue, elements are associated with priorities and execute according to priority. If there are two same priorities, then they will be executed according to the value associated with the priority.
Priority queue applications
Priority queue applications are used when balancing the load in Operating systems, in Dijkstra’s algorithm, etc.
In queues the first element will be removed first. Here it is based on higher priority
Priority queue with arrays/Lists
Adding an element to the priority queue
- Checks whether or not the queue is full. If it is full, it prints “Queue is full”.
- Else it increments the rear element to empty space.
- Adds the new elements associated with priority to empty space.
- Returns array/list.
Deleting elements
- Checks whether or not a queue is empty. If it is empty, it gets exited.
- Else it removes the elements with the highest priority.
- Returns array/list.
Rear - Gets the last item from queue.
Front - Gets the first item from queue.
Size - returns the length of the queue.
Implementation of priority queue
- Here, we see the implementation of priority queue using Array/List.
- We use
append()for enqueue andremove()for dequeue. - Here, we additionally have priorities and max method if priority is not given.
def element(a):return a[0]pqueue = [(1,34),(2,21),(5,11),(3,39),(5,35),(1,36)] #(priority,value)def deletinghighestpriority(x):a = sorted(pqueue,key=element)m = max(a)pqueue.remove(m)return pqueueprint("front of the queue = ",pqueue[0])print("rear of the queue = ",pqueue[-1])print("deleted highest priority queue=",deletinghighestpriority(pqueue))
Double ended queue
The double ended queue is under a linear data structure where both ends of the queue can be used for insertion and deletion.
Properties of dequeue
It is used as a stack as well as a queue, where
both ends are used for insertion and
deletion.
- It shifts between stack and queue according to the given condition.
Methods for adding element
append() - adds element to right end.
appendleft() - adds element to left end.
insert(index,value) - adds at given position.
extend(list) - adds multiple elements to right end.
extendleft(list) - adds multiple elements to left end.
Methods for deletion
pop() - removes element from right end.
popleft() - removes element from left end.
remove(value) - deletes first occurrence of value.
Other methods
count(value) - returns number of occurrences of that value.
index(e,start,end) - searches index of ‘e’ from given start to end.
reverse() - prints the elements in reverse order.
import collectionsde = collections.deque([1,25,3,34,2,25])print("The deque after after deleteing the element:")de.remove(3)print(de)de.extend([1,2,3])print("New deque extend right=",de)de.extendleft([1,2,3])print("New deque extend left=",de)de.popleft()print("New deque left deletion=",de)de.append(100)print("New deque add right=",de)
