Stack implementation using C

Stack

What is a stack?

A stack is a data structure in which the insertion or deletion of an element is done only to its topmost element called the top.

A good analogy for stacks is a stack of cafeteria trays in which trays are stacked on top of each other, and because the last tray is at the top of this stack it's going to be the first one to be removed from the stack.

This type of data structure is called Last In First Out (LIFO).

The act of add or inserting an item to a stack is called Pushing, and the act of removing an item is called Popping.

Specifications of a stack

(These are only the specifications and by no means an algorithm of implementation)

The first step we must perform in working with any stack is to create it.

Initialization

• Precondition: None
• Post-condition: Created and initialized an empty stack. We initialized our stack to be empty as we don't want to work with a stack filled with garbage values from whatever values existed at that address before we reclaimed it to ourselves.
• In other words, we are initializing the value of top to be 0.

Status

• We want to always check the status of our stack as we don't want to push an item to a full stack and similarly we don't want to pop from an empty stack.
• StackFull
  • Precondition: The stack has been created and initialized.
  • Post-condition: Returns True if the stack is full and False otherwise.
• StackEmpty
  • Precondition: The stack has been created and initialized.
  • Post-condition: Returns True if the stack is empty, and False otherwise.

Basic operations on the stack

• The two basic operations done on any type of a stack are pushing or pulling an item, so let's define those.
• Push
  • Precondition: The stack should be created and not Full.
  • Post-condition: The item that we want to add (Argument passed to Push) is added to the top of the stack, thus the top of the stack has increased.
• Pull
  • Precondition: The stack should be created and not empty.
  • Post-condition: The top of the stack is removed and returned to us, thus decreasing the top of the stack.

Other operations

• Other operations could be performed on a stack but they are not essential for its operation, nevertheless, they are useful.

Clearing the stack

• Precondition: The stack exists and is initialized.
• Postcondition: The stack is empty.

Determining the stack size

• Precondition: The stack exists and is initialized.
• Postcondition: Returns the number of entries (items) in the stack.

Determining the top item on the stack

• Precondition: The stack exists and is not empty.
• Postcondition: The top item on the stack is returned, but not removed.

Implementation of the stack using arrays (in C)

There are two types of implementation of an array Contiguous and Linked, we are going to focus for now on the first type.

If we wanted our stack to be represented as an array, what do we need to accomplish this?

We will need an array of type "whatever elements" we are going to store them in it, and we are going to need a pointer to keep track of the topmost element in our array (stack).

So basically a stack is just an array and a pointer to the top element, let's start with those.

We will create a structure of those two, and call it Stack.

Since they are of different types (Top of type int, and an array of whatever we are going to store) that we want to combine into one form, we will use a structure.

Definition of our stack

typedef struct stack {
int top;
char entry[10];
}Stack;

This code contains a lot of constants, that if we wanted to change the type of the item we want to store, or for example wanted more than 10 elements, we will have to change the core definition of the stack, and this contradicts with the principle of information hiding.

// If we wanted to change the type or the number of elements we could do it from here and leave
// the core definition of the stack alone.
#define MAXSTACK 10
typedef char StackEntry;

typedef struct stack {
int top;
StackEntry entry[MAXSTACK];
}Stack;

So that's it for our initial definition of the stack, pretty ain't :P.
Now let's implement the basic operations.

Notice that, for the basic operations to operate there is a pre-condition that must be fulfilled, and that is checking the status of the stack, so we have to implement those too.

Pushing

To push an item to the stack, what do we need?

We need the item that we are going to push item and the struct we just defined.

When specifying any data type, we use call-by-reference when a subprogram (function) may change the parameter.

That is why we passed the address of structure Stack to the pointer S, and to access any element we want in the Stack we use the -> arrow operator.

Bringing into focus that the value of top indicates how many items there are in our stack meaning that before assigning our item the value of top will be pointing to the position to be filled.

For clarification, since the array starts from 0, the value of Top will indicate the number of elements that exists until we reach the end of the array, this means that by the end of filling our stack the value of Top will be the value of MAXSTACK .

Don't try to print the content of the array at MAXSTACK as it's an uninitialized memory location and will contain whatever garbage value there is in that location.

As you can see in the diagram below when there exist two items the Top is of value 2.

push(StackEntry item, Stack *s)
{
    if (StackFull(s))
        ERROR("Stack is full");
    else
        s->entry[s->top++] = item;
}

Now let's analyze our code, as stated to push an item we first need to perform our stack status check, so we call our function StackFull() which we will implement later, if the stack is full, it prevents us from pushing our item, and prints an error message stating that our stack is full, else it allows us to push it.

So what we codded is "Access the array that is called entry at index top and add the item to the array, then increment the value of top, to point to the next value to be filled"

We want to increment the value of top after we have pushed our element, to point on the next location to fill, that is why we used the postfix increment top++.

Popping

Similarly, we implement the pop function by tweaking some differences, that is instead of writing to the Stack we are going to read from it and write the value stored there to a variable called item outside the function (We will pass that value's address) as it is outside the pop function's scope, but before reading remember that Top is pointing to an empty location and that's if the stack was not full, and it could be pointing to a garbage value and that's if it was full, so first we have to decrement it and then read the value, that why we use the pre-decrement operator.

pop(StackEntry *item, Stack *s)
{
    if (StackEmpty(s))
        ERROR("Stack is empty");
    else
        *item = s->entry[--s->top];
}

Note that the expression s->top is evaluated to top that resides in the Stack, so --s->top is similar to --top if and only if we are within the scope of the Stack. In other words s->--top is a syntax error.

Other operations

Checking if the stack is empty and if the stack is full

This implementation is rather simple all we have to do is writing a simple if condition, and return a non-zero value if the stack is empty and full.

Stack is empty

_Bool StackEmpy(Stack *s)
{
    return (s->top <= 0);
}

The return of this function will always be either 1 if the condition applies and 0 if the condition doesn't apply.

Stack is full

Bool StackFull(Stack *S)
{
    return (s->top > MAXSTACK);
}

Note that we used a pointer to the stack (Call by reference) even though we are not changing anything in the stack and only reading, and the reason for this is efficiency as if we passed by the value we would have copied the whole stack into both functions. i.e. It could be Bool StackFull(Stack s), meaning we pass the whole stack (Pass by value), but as stated it is a waste of memory space and time.

Initialization of the stack

Initialization of the stack means moving the top back to the zero position and not clearing the values of the stack.

This is a critical function as without it the top will have a garbage value.

void CreateStack (Stack *s)
{
    s->top = 0;
}

Getting the topmost element

So what we want to do is to print out the topmost item of our stack, in other words, we want to pop it, but at the same time, we don't want to change our stack so we will have to re-pop it again.

void StackTop(StackEntry *item, Stack *s)
{
    *item = s->entry[s->top-1];
}

Remember that top is pointing to an empty location if the stack is not full and a garbage value it's full.

Finding the stack size

To find the size of the stack we just print out the value of top.

int StackSize(Stack *s)
{
    return s->top;
}

Clearing the stack

Clearing the stack is just re-pointing the top to 0.

You are going to say that we have already implemented this in a function called CreateStack()and that's correct but we will reimplement just for the sake of the concept of information hiding (abstraction).

In the case of our current implementation (using an array) the elements are not destroyed, they still exist in the memory, it's just the value of top that changed, but in the other implementation (using linked stack) the elements are going to be destroyed (kind of).

void ClearStack(Stack *s)
{
    s->top = 0;
}

Traverse Stack

What we want to accomplish is to pass on every element of the stack and display it to the user but we have a little problem here, we want to accomplish this using abstraction concept, the problem lies in that the user has a piece of information that is hidden from us and that is the type of the element stored in the array, similarly the user doesn't know how the stack is implemented, he only uses the function that we have provided so to overcome this problem the user is going to define a function that displays only one element, then we are going to take this function and pass on every element thus displaying all the elements of the stack.

// User implemented function
void Display(StackEntry item)
{
    printf("The stack item is: %d\\n", item); // The data type is known only by the user.
}

Now notice that we are going to pass the address of the Display() function.

So the traverse function will take first the address of the stack and then the address of the Display()function. i.e. TraverseStack(&s, &Display).

void TraverseStack(Stack *s, void (*pDisplay) (StackEntry))
{
    for(int i = s->top; i>0; i--)
        (*pDisplay)(*s->entry[i-1]);
}

To pass a function as a parameter to another function we need to know its address in memory, its return type, and the type of argument it takes. So basically what we have codded is: The parameter pDispalay will be a pointer to a function that has a void return type and which takes a single StackEntry parameter.

User level implementation

An example of how a user will use our implementation of the Stack.

#include<stdio.h>
#include"StackImplement.h"

void Display(StackEntry item) {

    {
      printf("  ----- \\n");
      printf("|   %d   |\\n", item);
    }
}
void main(void) {
    Stack myStack;
    int item = 0;
    StackCreate(&myStack);

  for (int count = 0; count < MAXSTACK; count++)
    {
      printf("Please enter the value you want to enter in the stack:");
      scanf("%d", &item);
      Push(item, &myStack);
    }
  TraverseStack(&myStack, &Display);
}