Software Engineers Handbook/Life Cycle/Design/Choosing a Data Structure

Overview of Data Structures

There are about a handful of standard data structures types.

• Stack
• Queue
• More to come...

These can be implemented in various ways, but the specific characteristics of each are always maintained.

Stack

In short a stack is a collection of data with the Last In First Out (LIFO) paradigm. This means that the last item put on the stack is the first one that would come off of it. Items beyond this item cannot be directly accessed or removed, short of clearing the stack entirely.

These are the general actions one can perform on a stack:

• push - push something onto the top of the stack
• pop - pop the top of the stack (the last thing put on)
• peek - look at the item on the top of the stack (the last thing put on)
• is_empty - check to see if the stack is empty
• is_full - check to see if the stack is full

Keep in mind that exactly how one implements a stack can be completely different and this could cause the methods available on a stack to differ as well. For example, if the stack is static (cannot grow) and has a size of N, having the is_full is handy to tell when the stack is full. However, if the stack is dynamic (it can grow, if necessary) the is_full isn't handy if the stack can not technically fill up. Though some might choose to have a dynamic stack with an upper limit, making the is_full useful again. Also, it depends on the style of the developer creating the stack. At a minium there will always be something like a push or pop, though they might have different names.

Some tangible examples of a stack:

• Think of the Pez Candy dispensers - the last candy you put in is the first one out.
• Here's another one - the plate dispensers in a buffet line. The plates are piled inside on a spring loaded platform and customers take them off the top, one by one.

Some computer related ones:

• a RPN (Reverse Polish Notation) calculator.

Links

National Institute of Standards and Technology Stack Page

Queue

A queue is a collection of data with the First In First Out (FIFO) paradigm. This means that the first data put into it is the first data returned from it. Items cannot be randomly access from within the queue, only the item in the "first" position can be accessed. If you want to think of it terms of time - the oldest item in the array is the first one returned and the only one accessible at any one time.

These are the general actions that can be performed by a queue:

• enqueue - put something on the end of the queue
• dequeue - remove the first thing from the queue (the oldest)
• is_full - check to see if the queue is full
• is_empty - check to see if the queue is empty

As with the stack, the is_full (and maybe the is_empty) may or may not be useful depending on the implementation (static array, dynamic array, linked list... etc). Which methods are available also depends on the style of the developer creating the queue. At a minimum there will always be enqueue and dequeue, though they might have different names.

Some tangible examples of a queue:

• a line for a ride at an amusement part - the people in front, who have been waiting the longest, go first (or next).
• a line at a bank, where people are waiting for the next available teller.

Links

National Institute of Standards and Technology Queue Page

Links

National Institute of Standards and Technology