Stacks and Queues

Introduction

A stack is a kind of list where items are always added to the front and removed from the front. Thus, a stack is a First In, Last Out (FILO) structure. A stack can be thought of a structure that resembles a stack of trays. Each time a new piece of data is added to the stack, it is placed on the top. Each time a piece of data is removed it also must be removed from the top. Typically only the top item is visible. You cannot remove something from the middle.

Queues like stacks are a special kind of list. In the case of a queue, items are added to the back and removed from the front. In other words a queue is a First In First Out (FIFO) structure. A queue is essentially a line up.

The idea of front, back, and top in stacks and queues have absolutely nothing to do with their positions within the data structures used to implement them. It is up to the implementer to make that decision on where to put the frontmost, topmost and backmost items and maintain order.

Operations

Typically stacks and queues have the ability to do the following:

• add an item

• remove an item

• access the "next" item to be removed

There are various names that we attribute to these operations for these:

Operation	Stack	Queue
add an item	push	enqueue
remove an item	pop	dequeue
access the "next" item to be removed	top	front

The most important thing to remember about stacks and queues is that its all about the ordering. This absolutely must be tracked and maintained. When you add an item it must be positioned as the newest item. When you remove an item the one you remove is always the newest item for stacks or the oldest item for queues. You can't put something into the middle of a stack or queue. When you remove there is only one item that you can remove. Access is typically only granted to the item that is at the top/front of the stack/queue.

Stacks and Queues are NOT for general storage. They are used to track ordering. Any other features other than the 3 above must be secondary.

Applications

Applications of stacks and queues typically involve tracking the ordering of a set of values. The question is whether the application is interested in the data in the same order as it was received or reverse. Note that this is not as straight forward as it may seem. We are not talking about encountering all the data in one go. It will typically involve continuous adding and removing of data to the Stack or Queue.

Some examples:

• bracket checking (stack)

• breadthfirst tree traversals (queue)

• infix to postfix expression (stack)

• postfix expression calculation (stack)