Stack implemented as a linked list

Prerequisites

Read about linked lists first.

Introduction

A stack is perhaps the simplest abstract data type to implement. In this section, we use a linked list to implement a stack. Remember that a linked list is not in itself an abstract data type, but rather an implementation type.

What is a stack

A stack is also known as a LIFO, which stands for last in first out. It is a container with only four operations: push, pop, top, and empty.

Conceptually, a stack contains elements that are inserted by the push operation, and deleted by the pop operation in the opposite order that they were inserted. In other words, the first element to be deleted is the last one inserted. The top operation returns the last element inserted without affecting the contents of the stack. Finally, the empty operation is a predicate to test whether the stack has zero elements.

Implementing the stack

Let us first see how we can implement a stack without being concerned with header objects. For the purpose of this section, we assume that we have a linked list contained in a variable named l with the elements of the stack (if you do not appreciate the choice of such a short name, read the section on naming conventions). We also assume that we implement the operations as side effects on the variable l. For the implementation of push we further assume that a variable element contains the element to push onto the stack. We can take advantage of the operation cons that we defined in the section on linked lists, which gives the following code:
  l = cons(element, l);
The implementation of empty is particularly simple:
  return l == NULL;
or simply:
  return !l;
For the implementation of pop we need to check that the stack is not empty before attempting to remove the top element. Here is the code:
  assert(!empty(l));
  {
    list temp = l;
    l = l -> next;
    free(temp);
  }
If we have a garbage collector, we can do even better, like this:
  assert(!empty(l));
  l = l -> next;
Finally, for the top operation, we also need to check whether the stack is empty before attempting the operation:
  assert(!empty(l));
  return l -> element;

Turning it into a module

Now that we got our programming idioms done, let us look at how to turn these functions into a module. Recall that we divide a module into two distinct files, the header file (or the .h file) and the implementation file (or the .c file). Let us call our module stack and use that as a prefix for the operations.

Here is the header file:

  #ifndef STACK_H
  #define STACK_H

  struct stack;
  typedef struct stack *stack;

  /* create a new, empty stack */
  extern stack stack_create(void);

  /* push a new element on top of the stack */
  extern void stack_push(stack s, void *element);
 
  /* pop the top element from the stack.  The stack must not be
     empty. */
  extern void stack_pop(stack s);

  /* return the top element of the stack */
  extern void *stack_top(stack s);

  /* return a true value if and only if the stack is empty */
  extern int stack_empty(stack s);

  #endif
We have added comments describing briefly what the module does, and describing what each interface function does. The phrases must be and must not be mean that a program that does not respect what these phrases say, is a program with errors in it. This module is therefore free to do whatever it thinks reasonable (including nothing at all) when such a condition is violated. In our implementation, we will call assert and abort the execution of the program.

For the implementation, we use a header object:

  #include "stack.h"
  #include "list.h"
  #include < assert.h>
  #include < stdlib.h>
  
  typedef struct stack *stack;

  struct stack
  {
    list elements;
  };

  stack
  stack_create(void)
  {
    stack temp = malloc(sizeof(struct stack));
    temp -> elements = NULL;
    return temp;
  }

  void
  stack_push(stack s, void *element)
  {
    s -> elements = cons(element, s -> elements);
  }

  int
  stack_empty(stack s)
  {
    return s -> elements == NULL;
  }

  void
  stack_pop(stack s)
  {
    assert(!empty(s));
    s -> elements = cdr_and_free(s -> elements);
  }

  void *
  stack_top(stack s)
  {
    assert(!empty(s));
    return s -> elements -> element;
  }