Stacks in C explained

Today I am writing this blog after a long time and this time it’s different. It isn’t about space. I have decided to document my journey to becoming a computer engineer here in this blog. Today we shall see the stack implementation in the C programming language here. You can try the program by running it in the online GDB compiler.

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example, a deck of cards or a pile of plates.

A real-world stack allows operations at one end only. For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.

This feature makes it a LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation, and removal operation is called POP operation.

Stack Representation

Basic Operations

Stack operations may involve initializing the stack, using it, and then de-initializing it. Apart from this basic stuff, a stack is used for the following two primary operations −

• push() − Pushing (storing) an element on the stack.
• pop() − Removing (accessing) an element from the stack.

When data is PUSHed onto the stack.

To use a stack efficiently, we need to check the status of the stack as well. For the same purpose, the following functionality is added to stacks −

• peek() − get the top data element of the stack, without removing it.
• isFull() − check if stack is full.
• isEmpty() − check if stack is empty.

At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides the top value of the stack without actually removing it.

Push Operation

The process of putting a new data element onto a stack is known as a Push Operation. Push operation involves a series of steps −

• Step 1 − Check if the stack is full.
• Step 2 − If the stack is full, produces an error and exits.
• Step 3 − If the stack is not full, increments top to point next empty space.
• Step 4 − Adds data element to the stack location, where the top is pointing.
• Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.

Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of the pop() operation, the data element is not removed, instead, top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() removes data elements and deallocates memory space.

A Pop operation may involve the following steps −

• Step 1 − Check if the stack is empty.
• Step 2 − If the stack is empty, produces an error and exits.
• Step 3 − If the stack is not empty, accesses the data element at which the top is pointing.
• Step 4 − Decreases the value of the top by 1.
• Step 5 − Returns success.

Implementation in C

#include <stdio.h>
#include <string.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
int isempty() {
    if (top == -1) {
        return 1;
    
    }
    else {
        return 0;
    }
    
}
int isfull() {
    if (top == MAXSIZE) {
        return 1;
    }
    else {
        return 0;
    }
}
int peek() {
    return stack[top];
}
int pop() {
    int data;
    
    if(!isempty()) {
        data = stack[top];
        top = top -1;
        return data;
    }
    else {
        printf("Could not retrieve data, Stack is empty.\n");
    }
}
int push(int data) {
    if(!isfull()) {
        top = top+1;
        stack[top] = data;
    }
    else {
        printf("Could not insert data, Stack is full.\n");
    }
}
int main()
{
   // push items on to the stack 
   push(3);
   push(5);
   push(9);
   push(1);
   push(12);
   push(15);
printf("Element at top of the stack: %d\n" ,peek());
   printf("Elements: \n");
// print stack data 
   while(!isempty()) {
      int data = pop();
      printf("%d\n",data);
   }
printf("Stack full: %s\n" , isfull()?"true":"false");
   printf("Stack empty: %s\n" , isempty()?"true":"false");
   
   return 0;
}

If we compile and run the above program, it will produce the following result:

Output

Element at top of the stack: 15
Elements:
15
12
1 
9 
5 
3 
Stack full: false
Stack empty: true