To simulate stack storage in a C program, you need to emulate the four basic parts of a stack:

1. The stack storage
2. A stack pointer
3. A function to push a value onto the stack
4. A function to pop a value from the stack

Further, you need to implement controls that prevent a stack overflow or underflow. And you can get real fancy, but those four items are the basics.

In my code, I assign an array as stack storage. Unlike a processor stack, which is just a chunk of memory, in C an array must be typed, such as an integer array. The stack pointer variable must match the array type. And you don’t need to use a pointer; you could use an index into the array, but I’m using a pointer because, well, it’s called a stack “pointer,” isn’t it?

The two functions are traditionally named push() and pop(). The push() function requires an argument, the value to push onto the stack. The pop() function returns a value.

It’s easiest to code the stack emulation with the stack array and pointer as global variables. Otherwise, the stack array and pointer are required as arguments for both push() and pop() functions. For simplicity’s sake, I use global variables in my examples.

Here is how I’d declare the stack array and stack pointer as global variables:

#define STACK_SIZE 16

int stack[STACK_SIZE];
int *sp;

Array stack[] represents 16 int values. Integer pointer variable *sp references the “top” of the stack.

The push() function sends a value to the top of the stack. Further, it tests to ensure that a stack overflow doesn’t occur:

void push(int v)
{
    if(sp == stack+STACK_SIZE)
    {
        puts("Stack Overflow");
    }
    else
    {
        sp++;
        *sp = v;
    }
}

In this function, value v is pushed to the top of the stack. Before that, however, an if statement tests to ensure that the stack isn’t full. If so, the Stack Overflow message is displayed and the function returns. In the real world, the program would terminate at this point; memory overflows are serious business. In fact, you may have already coded programs that crash with a “Stack Overflow” message (especially when you do recursion).

The else statements in the push() function increment the sp (stack pointer) variable and set value v to that memory location.

In the push() function, variable sp always points at the top the stack. It does not point to the location of the next value. This is exactly how the esp register works in the processor.

To fetch a value from the stack, the pop() function is used. It requires no arguments in my example, because the stack[] array and sp pointer are global:

int pop(void)
{
    int s;

    s = *sp;
    if( sp == stack)
    {
        puts("Stack Empty");
    }
    else
    {
        sp--;
    }
    return(s);
}

The value at the top of the stack is saved in variable s. (It doesn’t have to be, but I wrote the function to be more readable.) The if comparison confirms whether the stack isn’t empty. If it is, an underflow message is displayed and the function returns. Otherwise, the sp variable is decremented and the value saved in variable s is returned.

Without variable s, the pop() function looks like this:

int pop(void)
{
    if( sp == stack)
    {
        puts("Stack Empty");
        return(0);
    }
    else
    {
        return(*sp--);
    }
}

Both if and else need return statements because the pop() is an int function. I return 0 on the stack empty condition, though in a real program you might just use exit(); it’s dangerous to assume that 0 would be on the stack when the stack is empty.

The *sp-- thing in the second return statement first fetches the value from the stack, then it decrements the sp pointer.

In next week’s Lesson, I demonstrate how to use these four elements in a program to simulate stack storage.