This book is new. If you'd like to go through it, then join the Learn Code Forum to get help while you attempt it. I'm also looking for feedback on the difficulty of the projects. If you don't like public forums, then email firstname.lastname@example.org to talk privately.
Exercise 15: Stacks and Queues
When working with data structures you'll oftentimes encounter a structure that is similar to another. A Stack is similar to a SingleLinkedList from Exercise 13, and a Queue is similar to a DoubleLinkedList from Exercise 14. The only difference is a Stack and a Queue restrict the possible operations to simplify how they are used. This helps reduce defects since you can't accidentally use the Stack like a Queue and cause problems. In a Stack, the nodes are "pushed" onto the "top" and then "popped" from the top as well. With a Queue, the nodes are shifted to the "tail" and then unshifted off the "head" of the structure. Both of these operations are simply simplifications of the SingleLinkedList and DoubleLinkedList where a Stack only allows push and pop while a Queue only allows shift and unshift.
When visualizing the Stack you should think of a stack of books on your floor. Think really heavy art books like the kind I have on my bookshelf that, if I stacked 20 of them, would probably weigh about 100 pounds. When you build this stack of books, you don't lift up the whole stack and put the books on the bottom, right? No, you put the books on the top of the stack. You drop them, but we can use the word "push" for this action too. If you wanted to get a book from the stack, you could probably lift some of them and grab one, but ultimately you'd probably have to take some from the top to get to the ones at the bottom. You would lift up each book from the top, or in our case we'd say "pop one off the top". This is how a Stack works, and if you think about it, that's just a linked list of books forced into a line by gravity.
Visualizing a Queue is easiest if you think of waiting in line at the bank with a "head" and "tail" on the line. Usually there's a rope maze that has an entrance at the end and an exit where the tellers are located. You enter the queue by entering the "tail" of this rope maze line, and we'll call that shift because that's a common programming word in the Queue data structure. Once you enter the bank line (queue), you can't just jump the line and leave or else people will get mad. So you wait, and as each person in front of you exits the line (unshift for you) you get closer to exiting from the "head". Once you reach the end then you can exit, and we'll call that unshift. A Queue is therefore similar to a DoubleLinkedList because you are working from both ends of the data structure.
Many times you can find real world examples of a data structure to help you visualize how they work. You should take the time now to draw these scenarios or actually get a stack of books and test out the operations. How many other real situations can you find that are similar to a Stack and a Queue?
I am now going to ween you off of code-based exercise challenges and have you implement data structures from descriptions of them. In this challenge you are first expected to implement a Stack data structure using the starter code here, and what you know about the SingleLinkedList from Exercise 13. Once you've done that, you're going to attempt to make the Queue data structure from nothing.
The StackNode node class is nearly identical to the SingleLinkedListNode, and in fact I just copied it over and changed the name:
1 2 3 4 5 6 7 8 9
The Stack control class is also very similar to the SingleLinkedList except I use top instead of first. That matches with the concept of a Stack.
Your challenge is to now implement the Stack and also write a test for it similar to the tests you did in Exercises 13. Make sure your test covers every operation in every way that you can. Remember, though, that push on the stack has to go on the top, so have a link to the top.
Once you have a working Stack you should implement the Queue but base it on the DoubleLinkedList. What you learned from the Stack should be that you can keep the same basic internal structure as a SingleLinkedList but just change the allowed functions. With a Queue it's the same thing. Take the time to diagram and visualize how a Queue works, then figure out how it restricts the DoubleLinkedList. Once you have that, create your Queue.
Breaking these data structures is simply a matter of not maintaining discipline. See what happens if one operation fails to use the correct end.
You may also have noticed that there's a constant risk of an "off by one" error. In my design, I set self.top = None for when the structure is empty. This means when you reach 0 elements, you have to do some juggling of self.top. An alternative is to make self.top always point at a StackNode (or any node) and to say the structure is empty when you have this last element. Try this out and see how that changes your implementation. Is that more or less error prone?
There are many operations for these data structures that are horribly inefficient. Go back through the code you've written for every data structure and try to guess which of those functions are slowest. Once you have an idea, try to explain why they might be very slow. Research what other people might say about these data structures as well. In Exercises 18 and 19 you'll learn to do some performance analysis of these data structures and tune them.
Finally, did you really need to implement a whole new data structure, or could you have simply "wrapped" the SingleLinkedList and DoubleLinkedList data structures? How does this change your design?