Stack implementation using C
Tags: c, programming, datastructure, stack
Published: 2021-08-14 16:57:38

## 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.**
![StackIntro](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rh4hnltgqq9gxiyhmpon.png)
## 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.
![StackStructure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nra83aafm5ufxlh7lqev.png)
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

```c
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](https://en.wikipedia.org/wiki/Information_hiding#:~:text=A%20software%20module%20hides%20information,subset%20of%20the%20total%20program.).
```c
// 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`.
![TopPointer](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4h5t176d2kczpe9i518b.png)
```c
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.

```c
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

```c
_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

```c
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.

```c
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.

```c
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`.

```c
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).

```c
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.
![TraverseStack](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hen3xgrc2yx9rl866p7u.png)
```c
// 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)`.

```c
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.

```c
#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);
}

```