Warning

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 help@learncodethehardway.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`?

# Exercise Challenge

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 It

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?

# Further Study

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?