Stack using priority Queue in Python3

Question

I have come up with the below code but somehow its not working as expected. What could be the reason of this. Idea is to make a pair of count and item to be pushed to the priority queue and then just pop.But how to implement this in python3?

import heapq

class Stack:

    def __init__(self):
        self.dict ={}
        self.cnt = 0
        self.hq = []

    def push(self, item):
        self.cnt += 1
        self.heappush(hq, {self.cnt:item})

    def pop(self):
        self.cnt -= 1
        return self.heappop(hq)

if __name__ == '__main__':
    s = Stack()
    s.push(10)
    s.push(20)
    s.push(30)
    print(s.pop())

I am receiving the below error.

Traceback (most recent call last):
  File "/home/shrivatsa/Documents/E/Learning-Path/Python/Algorithms and Datastructure/stackpriorityqueue.py", line 19, in <module>
    s.push(10)
  File "/home/shrivatsa/Documents/E/Learning-Path/Python/Algorithms and Datastructure/stackpriorityqueue.py", line 11, in push
    self.heappush(hq, {self.cnt:item})
AttributeError: 'Stack' object has no attribute 'heappush'

"somehow its not working as expected" - how did you expect it to work? How does it work instead? Give a minimal reproducible example. — jonrsharpe
– jonrsharpe, Commented Jul 29, 2018 at 16:56
the above code should work like a stack. i.e when I print(s.pop()) it should output me 30. — Shri
– Shri, Commented Jul 29, 2018 at 16:58
I am getting the error as : Traceback (most recent call last): File "/home/shrivatsa/Documents/E/Learning-Path/Python/Algorithms and Datastructure/stackpriorityqueue.py", line 19, in <module> s.push(10) File "/home/shrivatsa/Documents/E/Learning-Path/Python/Algorithms and Datastructure/stackpriorityqueue.py", line 11, in push self.heappush(hq, {self.cnt:item}) AttributeError: 'Stack' object has no attribute 'heappush' — Shri
– Shri, Commented Jul 29, 2018 at 17:00
Again, edit the question. That's unreadable in a comment. — jonrsharpe
– jonrsharpe, Commented Jul 29, 2018 at 17:00

vlizana · Accepted Answer · 2018-07-29 17:27:03Z

1

The self keyword is used to reference the object, this way we can specify we're referring to attributes or methods defined within the class. heappush and heappop are not defined in the Stack class but in the heapq library so you should call them heapq.heappush and heapq.heappop instead.

Another issue to take into account is that dictionaries do not have an ordering defined, and thus they can't be pushed into a heap. If you want to save these pairs you should use tuples instead.

Example:

import heapq

class Stack:

    def __init__(self):
        self.cnt = 0
        self.hq = []

    def push(self, item):
        self.cnt += 1
        heapq.heappush(self.hq, (self.cnt, item))

    def pop(self):
        self.cnt -= 1
        return heapq.heappop(self.hq)

if __name__ == '__main__':
    s = Stack()
    s.push(10)
    s.push(20)
    s.push(30)
    print(s.pop())

answered Jul 29, 2018 at 17:27

vlizana

3,2821 gold badge20 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Shri Over a year ago

But using this I am getting output as 10 instead of 30. For the stack it should have output 30.

vlizana Over a year ago

Is there any reason you're using the heapq library? maybe you could use just the builtin pop method of the lists ( this is replacing heapq.heappush(self.hq, (self.cnt, item)) for self.hq.append((self.cnt, item)) and heapq.heappop(self.hq) for self.hq.pop() )

Shri Over a year ago

The reason is question itself is asking to use the priority Queue build the stack..

vlizana Over a year ago

The heapq library provides heap queues, the documentation of heapq.heappop states it "Pop and return the smallest item from the heap". Maybe what you're looking for is the PriorityQueue from the queue library.

JMAA · Accepted Answer · 2018-07-29 17:20:35Z

0

heappush and heappop are functions in the heapq library. When you write self.heappush(...), for example, you're saying "call a function in this class called heappush, using the data from this instance)". But your class Stack doesn't have a function called heappush, hence the error.

To call the functions from the heapq library, use heapq.heappush(...) and heapq.heappop(...) instead.

answered Jul 29, 2018 at 17:20

JMAA

2,10616 silver badges28 bronze badges

Collectives™ on Stack Overflow

Stack using priority Queue in Python3

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related