Stack Data Structure in C Programming – Data Structures Part 2

Last Updated on: October 28th, 2023

This article is a continuation of the  Series on Data Structures and carries the discussion on different types of data structures and their implementation. The aim of this series is to provide easy and practical examples that anyone can understand. In our previous article, we discussed what is a Data structure and why we need that. In this article, we will see Stack Data Structure in C Programming – Data Structures Part 2.

Stack Data Structure in C Programming

What is a Stack Data Structure?

A stack is a linear data structure. The stack follows the Last In First Out(LIFO) principle, which means the last element inserted inside the stack is removed first. We cannot remove the element from the middle or bottom. So, data insertion and deletion can happen only at one end of the stack. We cannot insert/delete data from another end. The stack is an abstract data type and the stack size is predetermined so we cannot alter the memory size later on.

The below image can help you understand it in a better way.

In the above image, If you want to add more scoop to this cone, you have to add it from the top. You cannot add it from the middle or bottom. And also you have to eat the ice cream which has been added recently. You cannot eat the bottom one first. And, if you want to eat the bottom ice cream, you must first eat all the ice cream on top. This is exactly how the stack data structure works. You can add it from one end and remove it from the same end. That’s why it follows the Last In First Out principle.

Stack Operations

The following are some common operations implemented on the stack:

• push
• pop
• isEmpty
• isFull
• peek

push

Let’s take the example. Now We have a stack whose size is 2 bytes.

1. Initially, the stack is empty.
2. Then we are adding number 4. After this only one byte is free.
3. Now we are adding the number 10.

This adding (to top) process is called push in the stack data structure.

pop

1. Now the stack is full ( 2 elements are there).
2. We are removing the number 10. After this only one byte is free.
3. Now we are removing the number 4.
4. After removing all, the stack is empty now.

This removing element from the top is called a pop operation.

isEmpty

This operation is used to check whether the stack is empty or not. Why do we need this? We have discussed that here.

isFull

This operation is used to check whether the stack is full or not. Why do we need this? We have discussed that here.

peek

This operation is used to get the value of the top element without removing it.

Problems in Stack

While performing stack operation there are 2 conditions that can happen,

• Stack Overflow
• Stack Underflow

Stack Overflow

Stack Overflow happens when we try to push more elements into the stack beyond the stack capacity. So before inserting a new element into the stack we need to check the stack status, by using the isFull() function.

Why do we have to worry about stack overflow?

if your stack size is 10 bytes, and you are trying to add more than 10 bytes, then it will overwrite the adjacent locations which are not part of the stack. It will corrupt the other memory regions.

Stack Underflow

Stack Underflow happens when we try to pop an element from an empty stack. To avoid this condition we can use isEmpty() function.

Stack Data Structure Implementation

We can implement a stack using 2 ways,

• Linear Allocation – In Linear allocation stack is implemented using an Array.
• Linked Allocation – In Linked Allocation stack is implemented using a Linked list.

Linear Allocation

In this post, we will implement the stack using an array (Linear allocation). For the array-based implementation of a stack, the push and pop operations take constant time, i.e. O(1).

Stack Data Structure Programming

Before writing a code, you should keep the below points in your mind.

• A pointer called top is used to keep track of the top element in the stack. So, initialize it with -1. If the value of the top is -1, then the stack is empty. If the value of the top is MAX, then the stack is full.
• Whenever you push the element to the stack, you have to check whether the stack is full or not. If it is full, then you should not push the elements as the stack will overflow. If it is not full, then push the element and increment the top.
• When you want to pop the element from the stack, you have to check whether the stack is empty or not. If it is empty, you should not pop the element as the stack is an underflow. You can pop it if the stack is not empty. Decrement the value of the top when you pop the element.

Source Code

#include<stdio.h>
#include<stdbool.h>

#define MAX 3       // Stack's maximum size

//Function declaration
void push(void);
void pop(void);
void display(void);
void peek();

int stack[MAX];
int top=-1;

int main()
{
  int choice;
  printf("*** Stack  Implementation using Array***");
  
  while(1)
  {
    printf("\n1. Push\n");
    printf("2. Pop\n");
    printf("3. Display Elements\n");
    printf("4. Peek Top element\n");
    printf("Enter the Choice: ");
    scanf("%d",&choice);
    
    switch(choice)
    {
      case 1:
      {
        //Pushing(Inserting) the element into the stack
        push();  
        break;
      }
      case 2:
      {
        //Popping(Removing) the element into the stack
        pop();
        break;
      }
      case 3:
      {
        //Displaying all the elements in  the stack
        display();
        break;
      }
      case 4:
      {
        //Displaying the last element which is pushed into the stack
        peek();
        break;
      }
      default:
      {
        printf ("\nPlease Enter a Valid Choice: ");
        break;
      }
    }
  }
}

bool isFull()
{
  bool isStackFull = false;
  
  if(top >= (MAX-1))
  {
    printf("\nStack overflow\n");
    isStackFull = true;
  }
  
  return (isStackFull);
}

bool isEmpty()
{
  bool isStackEmpty = false;
  
  if(top <= -1)
  {
    printf("\nStack underflow\n");
    isStackEmpty = true;
  }
  
  return (isStackEmpty);
}
    
void push()
{
  if( isFull() == false )
  {
    int value;
    printf("\nEnter a value to be pushed: ");
    scanf("%d",&value);
    top++;
    stack[top]=value;
  }
}

void pop()
{
  if( isEmpty() == false )
  {
    printf("\nThe popped elements is: %d\n",stack[top]);
    top--;
  }
}

void display()
{
  if(top > -1)
  {
    int i;
    printf("\nThe elements in the stack are:\n");
    for(i=0; (i < top); i++)
    {
        printf("\n%d",stack[i]);
    }  
  }
  else
  {
    printf("\nThe Stack is empty\n");
  }
}

void peek()
{
  if(top > -1)
  {
    printf("\nThe top element is:%d\n",stack[top]);
  }
  else
  {
    printf("\nThe Stack is empty\n");
  }
}

Output

*** Stack  Implementation using Array***
1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 2
Stack underflow

1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 4
The Stack is empty

1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 3
The Stack is empty

1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 1
Enter a value to be pushed: 23
1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 4
The top element is:23

1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 1
Enter a value to be pushed: 123
1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 1
Enter a value to be pushed: 456
1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice: 1
Stack overflow

1. Push
2. Pop
3. Display Elements
4. Peek Top element
Enter the Choice:

I hope, now you are familiar with Stack and its operations.

Real-Life Applications of Stack

• Back/Forward on various browsers are done using the stacks approach.
• Tower of Hanoi
• Used for function calls as stack follows A LIFO approach
• Arithmetic expression conversion
• The stack is also used for evaluating an expression
• Convert Infix to Postfix
• Stack is used for DFS (Depth First Search)
• For recursion support.
• Reverse the string

In our next tutorial, we will see how to implement a stack using the Linked List.

You can also read the below tutorials.

Linux Device Driver Tutorials	C Programming Tutorials
FreeRTOS Tutorials	NuttX RTOS Tutorials
RTX RTOS Tutorials	Interrupts Basics
I2C Protocol – Part 1 (Basics)	I2C Protocol – Part 2 (Advanced Topics)
STM32 Tutorials	LPC2148 (ARM7) Tutorials
PIC16F877A Tutorials	8051 Tutorials
Unit Testing in C Tutorials	ESP32-IDF Tutorials
Raspberry Pi Tutorials	Embedded Interview Topics
Reset Sequence in ARM Cortex-M4	BLE Basics
VIC and NVIC in ARM	SPI – Serial Peripheral Interface Protocol
STM32F7 Bootloader Tutorials	Raspberry PI Pico Tutorials
STM32F103 Bootloader Tutorials	RT-Thread RTOS Tutorials
Zephyr RTOS Tutorials - STM32	Zephyr RTOS Tutorials - ESP32
AUTOSAR Tutorials	UDS Protocol Tutorials
Product Reviews	STM32 MikroC Bootloader Tutorial
VHDL Tutorials