Software Stacks
Implementation
In most high level languages, a stack can be easily
implemented either through an array or a linked list.
What identifies the data structure as a stack in either case is not the
implementation but the interface: the user is only allowed to pop or push items
onto the array or linked list, with few other helper operations. The following
will demonstrate both implementations, using C.
Array
The array implementation aims
to create an array where the first element (usually at the zero-offset) is the
bottom. That is,array[0] is the first element pushed onto
the stack and the last element popped off. The program must keep track of the
size, or the length of the stack. The stack itself can therefore be effectively
implemented as a two-element structure in C:
typedef struct {
size_t size;
int items[STACKSIZE];
} STACK;
The push() operation is used both to initialize the stack, and
to store values to it. It is responsible for inserting (copying) the value into
the ps->items[] array and for incrementing the
element counter (ps->size). In a responsible C implementation,
it is also necessary to check whether the array is already full to prevent an overrun.
void push(STACK *ps, int x)
{
if (ps->size == STACKSIZE) {
fputs("Error: stack
overflow\n", stderr);
abort();
} else
ps->items[ps->size++] =
x;
}
The pop() operation is responsible for removing a value from
the stack, and decrementing the value of ps->size. A responsible C implementation will also need to check
that the array is not already empty.
int pop(STACK *ps)
{
if (ps->size == 0){
fputs("Error: stack
underflow\n", stderr);
abort();
} else
return ps->items[--ps->size];
}
If we use a dynamic array,
then we can implement a stack that can grow or shrink as much as needed. The
size of the stack is simply the size of the dynamic array. A dynamic array is a
very efficient implementation of a stack, since adding items to or removing
items from the end of a dynamic array is amortized O(1) time.
Linked list
The linked-list implementation
is equally simple and straightforward. In fact, a simple singly linked list is sufficient to
implement a stack—it only requires that the head node or element can be
removed, or popped, and a node can only be inserted by becoming the new head
node.
Unlike the array implementation, our
structure typedef corresponds not to the entire stack structure, but to a
single node:
typedef struct stack {
int data;
struct stack *next;
} STACK;
Such a node is identical to a typical
singly linked list node, at least to those that are implemented in C.
The push() operation both initializes an empty stack, and adds
a new node to a non-empty one. It works by receiving a data value to push onto
the stack, along with a target stack, creating a new node by allocating memory
for it, and then inserting it into a linked list as the new head:
void push(STACK **head, int value)
{
STACK *node = malloc(sizeof(STACK)); /* create a new node */
if (node == NULL){
fputs("Error: no space
available for node\n", stderr);
abort();
} else { /*
initialize node */
node->data = value;
node->next = empty(*head) ?
NULL : *head; /* insert new head if any */
*head = node;
}
}
A pop() operation removes the head from the linked list,
and assigns the pointer to the head to the previous second node. It checks
whether the list is empty before popping from it:
int pop(STACK **head)
{
if (empty(*head)) { /* stack is empty
*/
fputs("Error: stack
underflow\n", stderr);
abort();
} else { /* pop
a node */
STACK *top = *head;
int value = top->data;
*head = top->next;
free(top);
return value;
}
}
Notes
continue in the next blog:
Hardware stacks (Abstract Data Type
(ADT))
J.W. PRODUCTION