The Stack

Background

A stack is a little harder to define than a queue, since there isn't a common term that will relate how a stack works. It is definitely a linear collection of similar items. Stacks have access rules too, but the rules are different than the rules for queues.

You have been exposed to the idea of a stack before. When you go to a cafeteria to get lunch you take a tray from the stack of trays. You must always take the tray that is on the top of the stack. The cafeteria personnel put clean trays on the stack. The clean trays are always added to the top of the stack, so the tray that's on top is the last one that was added.

A stack is refered to as a LIFO data structure: Last In, First Out.

The Stack ADT

The definition

A stack is a linear collection of similar items, where an item to be added to the stack must be placed on top of the stack and items that are removed from the stack must be removed from the top. The top of the stack is known as the top. The term push means to add an item to the stack, and the term pop means to remove an item from the stack.

The operations

There are actually very few operations on a stack.