Search code examples
pythondata-structurespriority-queue

Is there a "Lifo" type priority queue in python in case of multiple elements with the same priority?

I have two tuples with the same rank in a priority queue in python. The get method will take the first element inserted. If two elements have the same priority in the queue, I would like to get the last element inserted returned first :

#python 3.7
import queue
q= queue.PriorityQueue()
q.put((1, 'first_in'))
q.put((1, 'last_in'))
q.put((2, 'not_to_be_returned'))

for i in range(q.qsize()):
    print(q.get(i))

#Returns
(1, 'first_in')
(1, 'last_in')
(2, 'not_to_be_returned')

#looking for : 
(1, 'last_in') # in case of same rank return the last inserted
(1, 'first_in') 
(2, 'not_to_be_returned')

#Merci
Solution

  • If you really need this ordering, the simplest way to solve it is to add a new 2nd element to your tuples that will be used to break ties when the 1st elements in two tuples are the same.

    For LIFO ordering you use a counter that you decrement every time you insert. Your elements then become:

    q.put((1, 0, 'first_in'))
q.put((1, -1, 'last_in'))
q.put((2, -2, 'not_to_be_returned'))