Build a queue class in Python - Python Tutorial

- We are now going to implement a queue class in Python. This is chapter five two so I'm going to open that folder. You would want to work on the start version of that folder. and then I'm going to open up q_ll.py. Now the reason we've called it that rather than just q.py, is because there's an existing module in Python called queue, and quite a common and hard to debug error that you might come across is if you name your own module. The same as something that already exists, then you would actually override that module and all the methods you expect to find won't work. Okay so one way to avoid that is to, just rename it to something a little bit different from the existing module. So here q_llq intel learning. So that's the folder were in so let's make a start. Now it is possible to use a list for a queue just as we did for our stack. However lists are not very efficient for this purpose. While appends and pops from the end of the list are fast doing inserts or pops from the beginning of a list is slow, because all the other elements have to be shifted by one. So what I'm going to do to avoid this problem is I'm going to use an existing data structure within Python called call the deque, now a deque stands for a double-ended queue, and it's a data structure that's optimized for insertions and deletions at either end, basically like a list with that optimization that if you want to insert or delete from either end it'll be fast. Which obviously doesn't matter if you have a very short list but if you have a massive list then it really does make a difference in terms of performance. So that's why I'm introducing this new data structure. So instead of a list we're going to use a deque, that's the only conceptual difference really in a deque is like a list but it's optimized. So let's go, inside of our queue class we have the Constructor as usual, because it's the class So def double underscore init. And then python fills in self and here were going to do self.items is equal to a deque okay. So this is the Constructor for the deque so it's an object within an object, but then so would a list be. So when you create a list that is actually an object as well, it's just not obvious that that's the case because we're so used to it working with lists. So on line 12 we are creating self.items and setting it equal to an an empty deque or an empty double ended queue. Then very similar to the stack def is empty return not self.items and again if that's confusing, the reason that works is because an empty deque returns false, but if that's confusing for you, you can return len of self.items whether or not that is equal to zero. So that's an alternative way of doing that, but I'm going to go with the first one. Then enqueue, so this is another very good reason for wrapping this method in a class is we can actually choose how we want to refer to our methods and enqueue is the traditional naming convention for working with a queue so we can enforce that, by having that particular method. So en queue self and it takes item 'cause that's what we're going to add. So we do self.items.append fairly straightforward. That's being added to the right hand side of our deque, and then we have de-queue and then return. So we don't just pop the item we also return it. Okay so here this is a method of the deque class where we do pop left. If this was just a list were we do pop zero, and that would pop the item that was at the zeroth index which would be on the left but this pop life method is from the deque class. Behaves exactly the same way just faster and then couple more methods so we have def size and then we return len of self.items and it's still useful to have peek so we can see what sort of runs. So def peek so that here we return self.items and in this case it's the one on at the left hand side so that's zero. So this is different to a stack, with a stack we want on the right hand end. But here in our queue we want the front, which is the left hand side of our data structure. Now we also need a string representation so we do def double underscore str sometimes it's called dunder, which is why I kind of said both at the same time there def dunder string, self return str of self.items. Okay and that's our class definition. So then we can start testing it by doing if name is equal to double underscore main then we can start doing stuff and again the reason for doing this, is if we ever wanted to import this class into a different file we could do so without with this code after my if double underscore main on line 33 being run, that keeps it modular. So then so then let's create a queue so q is equal to queue with a capital Q and we'll just print that just to see that everything's working as it should be and there is this, idea that we should have a certain amount of spaces in different situations the reason this is underlined in yellow is I don't have the right number of spaces. But rather than think about that too much. In Python, I just go to code reformat my code and it does it for me, it's a very useful feature. Let's run that see what happens, okay so it's working and you can see down in the terminal here that was getting displayed when we printed a queue now is this empty deque, object. And just again to remind you how this plunder struck method works, if I come into that now and do the same thing and then you can see you get this main queue object, which doesn't give us much information. So that's why we add these extra methods to return a human-readable representation of our objects, okay so that's that. Continuing we have print queue.is empty, okay that's just to check if that method works, and it is empty which makes sense 'cause we haven't enqueued anything. So now let's add some items to our queue so we're going to do some enqueueing so we do queue.enqueue and I'm going to do a letter this time A, and if I do control D a couple of times that duplicates the line very useful shortcut. So enqueue two more letters and just have a think about what the state of the queue is now at this point. So if I were to print(q) think about if we start with an empty list or an empty deque, I might as well just call it a list 'cause the concept is the same. And then we enqueue that means we add from the right hand side so that means A would have been up front and then D gets added and then F added. So if I run it you can see that the order is A, D, F okay. Now let's do some dequeueing so if I do print (q.dequeue()). Now the reason I can do this is because dequeue returns it does two things it removes the item from the queue and also it returns it. That means when I print, the result of that function call all gets an output, I'll do that twice. Okay so the first time I dequeued I got A and then I got D. And then if I were to print my q on a new line print q, now what would you expect to see at this point. You would expect to see just an F left on the queue because we had three items we removed two of 'em and then let's just test the other methods that we wrote so print q.size, notice it's a method rather than just a property that's why I made that brackets. And we'll print q.peek that'll show us what's at the head of our to queue, also a method and then finally print our q again just to see what we got left after all of that. Okay so q.size was one 'cause there's one item left. That item there at the front of the queue is F as we expected and again finally I printed the q and it's still what it was, because neither of those last two methods actually modified the queue that we have. So now you have a queue class which you can use in your own programs whenever you need preserve the F.I.F.O, First In First Out, order of your data. Next up we will see how powerful the simple structure can be in the context of the prep first search algorithm.