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?

1
2
3
4
5
6
7
8
9

class StackNode(object):

    def __init__(self, value, nxt):
        self.value = value
        self.next = nxt

    def __repr__(self):
        nval = self.next and self.next.value or None
        return f"[{self.value}:{repr(nval)}]"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Stack(object):

    def __init__(self):
        self._top = None

    def push(self, obj):
        """Pushes a new value to the top of the stack."""

    def pop(self):
        """Pops the value that is currently on the top of the stack."""

    def top(self):
        """Returns a *reference* to the first item, does not remove."""

    def count(self):
        """Counts the number of elements in the stack."""

    def dump(self, mark="----"):
        """Debugging function that dumps the contents of the stack."""