# Sample Video Frame

# 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`

?

## Register for Learn More Python the Hard Way

Register today for the course and get the all currently available videos and lessons, plus all future modules for no extra charge.