The Stack Abstract Data Type
Promoting object oriented techniques and maintaining code for Last-In-First-Out (LIFO) or First-In-First-Out (FIFO) stacks.
Jun 2, 2006
Introduction
Abstract data types are ways in which a programmer can define a set of data types and operations in a way that is independent from their eventual use, in order to:
- Maximise re-use;
- Promote object oriented techniques;
- Make the code easier to maintain.
Part of the reason that using ADTs is a good idea is that it encapsulates the data representation and manipulation behind data structures and algorithms which are well understood. In order to create an actual instance of the abstract data type in a program, the real data that needs to be manipulated is added to it, but the ADT manipulation need not change.
In order to visualise this, the reader should imagine an empty warehouse. It fulfils a warehousing function intrinsically. Once we start to put things into it, it can become a shoe warehouse, a car warehouse, or even a fruit warehouse. These items are the data, and the warehouse is the abstract data type - by adding items into it, we make an instance of that kind of warehouse.
Types of Stack
In principle, there are two types of stack - Last-In-First-Out (LIFO) or First-In-First-Out (FIFO). A LIFO stack allows us to add data items to the top of the list, with the caveat that items can only be pulled off the top. On the other hand, items added to the top of a FIFO stack can only be pulled off the bottom.
It is not generally permitted to insert items into the stack, nor remove arbitrary items from within the stack. To use the warehouse metaphor again, we can (LIFO) put in items and take them out of the same door, or we can open a door at the back (FIFO). We cannot take off the roof, and reach in to select an item.
The Abstract Data Type
To create the data type, we need nodes capable of storing some kind of data (what kind, we need not know at this time), and some form of container and management system.
We need to decide whether each node is linked to the next, or whether a static or dynamic array is enough. A dynamic array, for example, will grow and shrink when items are added or removed, and is best for a FIFO stack.
To implement a LIFO stack, a linking system between nodes is most appropriate. If we plan to have a limited number of slots into which to put data, then a static array can be used, and references to the first and last items in the stack be maintained.
All of this is verging on being implementation specific, and the idea of the abstract part of the ADT is just to give the data model, and the operations we can do upon it.
Stack Methods
The first method we would like is to add items to the stack. We could call this method the Push. Then, for LIFO stacks, the traditional method name is Pop; popping the top item off the top of the stack.
For a FIFO stack, we could (in the interest of remaining abstract) retain the method name Pop, but perhaps Pull might be more appropriate. Either way, we might also need a way to determine whether the stack is FIFO or LIFO.
Apart from these methods, there is very little extra functionality that we would require.
Implementing Stacks
To implement the stack, a dynamic array, or linked list is probably the most appropriate. In essence we would like to create a list of items, with each pointing to the next:
The Push method of a LIFO stack would then modify the list (dynamic array):
Node3-Node2-Node1
When we Pop the item off the top of the stack, all we need to do is extract the value, and shrink the stack back down again.
The reason a list is a better choice for a FIFO stack is that it is not possible (without copying the whole list) to remove the first item from a dynamic array. Consequently, we would rather extract the value of Node1 (in this case), and then destroy it.
For those familiar with the C language, the pointers might look akin to:
Push : Node3-Node2-Node1-NULL
Pull (FIFO) : Node3-Node2-NULL
Of course, a list can also be used to implement a LIFO stack, and this exercise is left for the reader.
