Contents

Stacks

Lists are not the only kind of ADT. Another really useful ADT is the Stack. Stacks represent, well, stacks of data, and exhibit similar characteristics. The most important characteristic being that items added to the stack follow a first in, last out (FILO) pattern. (This is also called the last in, first out, or LIFO, pattern. We'll stick to the former in class.)

Here's an example of FILO in the physical world. Let's say you and your family have just finished dinner. Each person brings his or her plate to the sink. The first person to reach the sink puts his or her dish first, then the second person puts his or her dish on top of the first one, etc. Then you volunteer to do the dishes. You start by taking the plate on top—that is the plate put down by the last person. You wash that dish, then take the next one, which was placed there by the second to last person. When you finally reach the last plate, it the one that was set there by the first person to reach the sink after dinner. So, the first plate added to the stack was the last plate taken from the stack to wash.

We also see stacks in the digital world. When you browse the web, each page you visit is placed in your browsing history. If you press the back button, the last page you visited is popped off the top of the history. Each click of the back button will pop off the next most recent web page. Eventually you will reach the first page you visited. If you visit a new page, that will be pushed into the history, etc., etc.

Since Stack is an ADT, we can define its behavior just like we did with the List ADT. Before considering the behavior, envision a stack as a vertical list of items (just like our plates example). The top of the stack refers to the most recent item added, and the bottom of the stack refers to the least recent item added:

With that setup in mind, here are the usual methods that a Stack should have.

Operation name	Description
isEmpty()	Return whether or not the stack is empty
size()	Return the number of items in the stack
top()	Return the item at the top of the stack
pop()	Remove and then return the item at the top of the stack
push(item)	Add item to the top of the stack

Notice that there is only one way to add an item, and that is with the push method. If you push three items 1, 2, and 3 onto a stack in that order, then the stack size will be three with 1 being at the bottom and 3 being at the top. To get data out, you can only access the top of the stack. You have two choices of methods: top will tell you what is on top of the stack, but will not remove it; and pop will tell you what is on top of the stack, and will also remove it for you. So if we invoked top on our stack of three items, we would get 3, and the stack size would still be three. If we invoked pop, then we would get 3 back, but the stack size would change to two, and 2 would be at the top.

As with any ADT, we can implement Stack many different ways. For instances, we can create an implementation that uses: arrays, vectors, or singly/doubly linked lists. It turns out, however, that singly linked lists are extremely convenient for this kind of ADT. Think about why that may be.

(Back to top)

Queues

Queues define a set of behaviors that follow a "first come, first serve" policy, just like a checkout line (a queue is what our British cousins and their kin call a line). In computer science jargon, we call this FIFO (first-in, first-out) or LILO (last-in, last-out). We'll use the former as it matches with the "first come, first serve" phrase.

Queues are used all over the place, both in the physical and digital worlds. We've already mentioned check out lines. Any line is essentially a FIFO. In the digital world, we have digital lines: buying tickets on line, signing up for classes, processing packets on a router, and buffering, such as in music and video streaming. They are all around us.

We usually illustrate a queue horizontally (that way it looks more like a line), with a front and a back. Items are added to the back and taken from the front. Therefore, the oldest thing added will be at the front of the queue and the newest thing at the back. Here's and example:

The behavior of Queues can be defined as follows:

Operation name	Description
isEmpty()	Return whether or not the queue is empty
size()	Return the number of items in the queue
front()	Return the item at the front of the queue
dequeue()	Remove and then return the item at the front of the queue
enqueue(item)	Add item to the back of the queue

As with a Stack, there's only one way to add items, and that's through enqueue, which places the item at the back of the queue. If we enqueue three items 1, 2, and 3, then the size of the queue is three, with 1 at the front (it was the first item added) and 3 at the back (it was the last item added). Calling front will tell us the item at the front, in this case 1, but the queue will remained unchanged. To get the item at the front and remove it, we use the dequeue method. Doing so will remove 1 form the queue, moving 2 to the new front and 3 remains at the back.

Just like with Stack, we can implement this a number a ways: arrays, vectors, and linked lists. It turns out that a singly linked list is a great choice. Can you think of why?

(Back to top)