Stack Data Structure in C Programming – Data Structures Part 2

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 have discussed what is a Data structure and why do 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 is following 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.

Stack Data Structure
Image source – miro.medium.com/max/1400/0*bbTnCsiT0klMbi3q.png

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 creams 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

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.

Stack PUSH operationpop

  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.

Stack POPisEmpty

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 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 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 TutorialsC Programming Tutorials
FreeRTOS TutorialsNuttX RTOS Tutorials
RTX RTOS TutorialsInterrupts Basics
I2C Protocol – Part 1 (Basics)I2C Protocol – Part 2 (Advanced Topics)
STM32 TutorialsLPC2148 (ARM7) Tutorials
PIC16F877A Tutorials8051 Tutorials
Unit Testing in C TutorialsESP32-IDF Tutorials
Raspberry Pi TutorialsEmbedded Interview Topics
Reset Sequence in ARM Cortex-M4BLE Basics
VIC and NVIC in ARMSPI – Serial Peripheral Interface Protocol
Bootloader TutorialsRaspberry PI Pico Tutorials
Zephyr RTOS Tutorials - STM32Zephyr RTOS Tutorials - ESP32
VHDL TutorialsUDS Protocol Tutorials
Product Reviews
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments