Stacks
From
| Line 6: | Line 6: | ||
isEmpty(). Sometimes there will be an operation called isFull(). | isEmpty(). Sometimes there will be an operation called isFull(). | ||
| + | ==Implementation of Stacks== | ||
One of the many uses of a stack is to reverse data. Consider a singly linked list of numbers | One of the many uses of a stack is to reverse data. Consider a singly linked list of numbers | ||
that is kept in order from smallest (at the head) to the largest (at the rear). What if I wanted | that is kept in order from smallest (at the head) to the largest (at the rear). What if I wanted | ||
| Line 11: | Line 12: | ||
Implementation. A stack is usually implemented in one of two ways: either using an array or | Implementation. A stack is usually implemented in one of two ways: either using an array or | ||
a linked list. | a linked list. | ||
| + | |||
With an array, we need an isFull() operation. There is normally an index called top, | With an array, we need an isFull() operation. There is normally an index called top, | ||
which is initialized to -1. Then, the push() operation is | which is initialized to -1. Then, the push() operation is | ||
| + | |||
if( not isFull() ) | if( not isFull() ) | ||
stack[ ++top ] = data | stack[ ++top ] = data | ||
| Line 22: | Line 25: | ||
And the isEmpty() operation is | And the isEmpty() operation is | ||
return( top == -1 ) | return( top == -1 ) | ||
| + | |||
When a stack is implemented as a linked list, we do not usually need the isFull() | When a stack is implemented as a linked list, we do not usually need the isFull() | ||
operations, but the isEmpty() operation is the same as that of the list. The normal way to | operations, but the isEmpty() operation is the same as that of the list. The normal way to | ||
implement the stack is to add and remove nodes from the head of the list. Note that if we do | implement the stack is to add and remove nodes from the head of the list. Note that if we do | ||
this, we do not need to use a rear pointer for the list. | this, we do not need to use a rear pointer for the list. | ||
| + | |||
Note also that a stack is an efficient data structure as all operations are constant. The array | Note also that a stack is an efficient data structure as all operations are constant. The array | ||
based stack wastes space that the linked list does not. | based stack wastes space that the linked list does not. | ||
Revision as of 20:02, 26 March 2009
The ADT Stack is a collection of homogeneous data that organizes its entries according to the order in which they were added. The organization is called LIFO or Last In, First Out (Sometimes called FILO). In the ADT Stack, there is one access point called the top of the stack, and only the item at the top, which is the most recently added item, is visible. The normal operations that can be performed on a stack are: push(), pop(), peek(), and isEmpty(). Sometimes there will be an operation called isFull().
Implementation of Stacks
One of the many uses of a stack is to reverse data. Consider a singly linked list of numbers that is kept in order from smallest (at the head) to the largest (at the rear). What if I wanted to print out the numbers in order from largest to smallest? Implementation. A stack is usually implemented in one of two ways: either using an array or a linked list.
With an array, we need an isFull() operation. There is normally an index called top, which is initialized to -1. Then, the push() operation is
if( not isFull() ) stack[ ++top ] = data The pop() operations can then be implemented with if( not isEmpty() ) return( stack[ top-- ] ) The isFull() operation is return( top == N – 1 ) And the isEmpty() operation is return( top == -1 )
When a stack is implemented as a linked list, we do not usually need the isFull() operations, but the isEmpty() operation is the same as that of the list. The normal way to implement the stack is to add and remove nodes from the head of the list. Note that if we do this, we do not need to use a rear pointer for the list.
Note also that a stack is an efficient data structure as all operations are constant. The array based stack wastes space that the linked list does not.
