Stacks – pushing and popping

A “stack” is a last-in, first-out storage system. You can use address arithmetic to add elements to a stack (pushing) or remove elements from the stack (popping). When programmers refer to “the stack”, they typically mean the structure that is used by the C compiler to store local variables declared inside a function. But, in fact, a stack is a generic type of data structure that you can create and use in your own code, which is what I discuss here.

The code below defines a very small stack: an array _stack of 2 integers. Remember, when testing, it is always better to use small numbers of items rather than large numbers. If your code contains errors, these will be easier to spot in an array of two items rather than in array of 100 items. I also declare a stack pointer _sp and set it to the base (the address) of the _stack array:

#define STACK_SIZE 2
static int _stack[STACK_SIZE];
static int* _sp = _stack;

I now define the push() function, which pushes an integer onto the stack, just as you might add a plate onto a stack of plates. It returns the new number of items on the stack, or -1 if the stack is full:

int push(int value) {
      int count;count = _sp - _stack;
      if (count >= STACK_SIZE) {
            count = -1;
      } else {
            *_sp++ = value;
            count += 1;
      }
      return count;
}

In order to get an item from the stack, I need a pop() function. Remember a stack is a last-in, first-out structure. If I have stacked up ten plates to be washed, I pull the first plate off the top of the stack (which was the last plate I put on the stack), wash it, and then take off the next plate (the last-but-one plate that I put on the stack) and so on. My pop() function does this with the elements stored in my_stack data structure. It returns the new number of items on the stack, or -1 if it is empty:

int pop(int* value) {
      int count; count = _sp - _stack;
      if (count == 0) {
            count = -1;
      } else {
            *value = *--_sp;
      count -= 1;
      }
      return count;
}

And here is some code showing how to push and pop items onto and off the stack:

void test_stack() {
      int i, r, v;
      for (i = 0; i < 4; i++) {
            v = i + 10;
            r = push(v);
            printf("push returned %d; v was %d\n", r, v);
      }
      for (i = 0; i < 4; i++) {
            v = 0;
            r = pop(&v);
            printf("pop returned %d; v was %d\n", r, v);
      }
}

Stacks are handy, temporary storage structures. It’s worth getting to know them!