Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data
structure
queue
python
communitycreator

What are priority queue and deque in Python?

Musthyala-Rohan

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.

1 of 5

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

  1. Checks whether or not the queue is full. If it is full, it prints “Queue is full”.
  2. Else it increments the rear element to empty space.
  3. Adds the new elements associated with priority to empty space.
  4. Returns array/list.

Deleting elements

  1. Checks whether or not a queue is empty. If it is empty, it gets exited.
  2. Else it removes the elements with the highest priority.
  3. 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 and remove() 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 pqueue

print("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 collections
de = 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)

RELATED TAGS

data
structure
queue
python
communitycreator
RELATED COURSES

View all Courses

Keep Exploring