CODEWITHSUNDEEP
pythonpython-3.x
Shri
Shri

Reputation: 75

Stack using priority Queue in Python3

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'

Upvotes: 0

Views: 219

Answers (2)

vlizana
vlizana

Reputation: 3232

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())

Upvotes: 1

JMAA
JMAA

Reputation: 2059

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.

Upvotes: 0

Related Questions