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.
Table of Contents
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
Let’s take the example. Now We have a stack whose size is 2 bytes.
- Initially, the stack is empty.
- Then we are adding number 4. After this only one byte is free.
- Now we are adding the number 10.
This adding (to top) process is called push in the stack data structure.
pop
- Now the stack is full ( 2 elements are there).
- We are removing the number 10. After this only one byte is free.
- Now we are removing the number 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 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
topis used to keep track of the top element in the stack. So, initialize it with -1. If the value of thetopis -1, then the stack is empty. If the value of thetopisMAX, 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
topwhen 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.
Embedded Software Developer who is passionate about Embedded Systems.
