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