What is Stack Structure in C?
A stack is a linear data structure which follows LIFO (last in first out) or FILO (first in last out) approach to perform a series of basic operation, ie. Push, Pop, atTop, Traverse, Quit, etc. A stack can be implemented using an array and linked list.
Stack Operations in C
There are two basic operations performed in stack:
1) Push: Adds an element in the stack.
2) Pop: Removes an element from the stack.
- Note: The elements always popped and pushed in the opposite order.
Some Other Important Stack Operations are
- isEmpty: checks whether the stack is empty or not
- atTop: It returns the top element present in the stack
- Traverse: This operation process all the elements present in stack exactly once.
- Quit: Quit the stack
Stack Overflow and Underflow
- Stack Overflow: It is a condition that happens when we try to push more elements into the already saturated stack
- Stack Underflow: It is a condition that happens when we try to pop an element from an empty stack
How does Stack Works?
A stack is a limited access data structure because push (addition) and pop (deletion) occur only at one end of the structure known as the top of the stack. Push adds an item to the top of the stack, pop removes the item from the top.
Stack works on LIFO/FILO approach that means the element pushed first in the stack will be popped last will acquire top position in the stack and will pop first.
For example, a stack is the pile of dinner plates in your Kitchen: When you take out a plate from the pile, you take the plate on the top of the pile. But this is precisely the plate that was added most recently on top of the pile; therefore LIFO approach is applied here as the plate inserted at last is taken out first. Similarly, If you need to take out the plate at the bottom of the pile, you must remove all the plates on top of it to reach it; therefore, FILO approach will be applied here as the plate inserted first will be taken out at last.
Real-Life Applications of Stack
- Back/Forward on various browsers are done using stacks approach.
- Used for function calls as stack follows A LIFO approach
- The stack is also used for evaluating an expression
- Convert Infix to Postfix
- Stack is used for DFS (Depth First Search)
- For recursion support.
Examples of Stack in C
A stack can be implemented in C language using:
- Array
- Linked List
1. Stack Program in C using Array
/*Stack implementation using static array*/
#include<stdio.h>
//Pre-processor macro
#define stackCapacity 5
int stack[stackCapacity], top=-1;
void push(int);
int pop(void);
int isFull(void);
int isEmpty(void);
void traverse(void);
void atTop(void);
//Main function of the program
void main(void)
{
int choice, stackItem;
//Always true While loop for continue iteration
while(1){
//Instructions to the user
printf("Stack Operation n");
printf("Enter `1` for Push Operation n");
printf("Enter `2` for Pop Operation n");
printf("Enter `3` for atTop Operation n");
printf("Enter `4` for Traverse Operation n");
printf("Enter `5` for Quit Operation n");
printf("Enter your choice : ");
scanf("%d",&choice);
//Switch Case to do the user specified task
switch(choice){
case 1:
printf("Enter a integer value : ");
scanf("%d",&stackItem);
push(stackItem);
break;
case 2:
stackItem = pop();
if(stackItem == 0){
printf("Your stack is underflow");
}else{
printf("Last popped item : %dn", stackItem);
}
break;
case 3:
atTop();
break;
case 4:
traverse();
break;
case 5:
return;
break;
default: printf("Please enter correct choice : ");
}
}
}
//Push Function to insert element into the stack
void push(int stackElement)
{
if(isFull()){
printf("Stack is full.It can't be overflowed. n");
}else{
top++;
stack[top] = stackElement;
printf("%d has been pushed n", stackElement);
}
}
//Function to check, Is stack full?
int isFull(){
if(top == stackCapacity-1){
return 1;
}else{
return 0;
}
}
//Function to check, Is stack empty?
int isEmpty(){
if(top == -1){
return 1;
}else{
return 0;
}
}
//Function to pop last element of the stack
int pop(){
if(isEmpty()){
return 0;
}else{
return stack[top--];
}
}
//function to check, Which element on the top?
void atTop()
{
if(isEmpty())
{
printf("Your Stack is empty n");
}else{
printf("Element at top is : %d n", stack[top]);
}
}
//Function to display the all the characters elements of stack
void traverse(){
if(isEmpty())
{
printf("Your Stack is empty n");
}else{
int i;
printf("Stack Elements are : n");
for(i=0; i <= top; i++){
printf("%d n", stack[i]);
}
}
}
Output
Stack Operation
Enter `1` for Push Operation
Enter `2` for Pop Operation
Enter `3` for atTop Operation
Enter `4` for Traverse Operation
Enter `5` for Quit Operation
Enter your choice : 2
Your stack is underflowStack Operation
Enter `1` for Push Operation
Enter `2` for Pop Operation
Enter `3` for atTop Operation
Enter `4` for Traverse Operation
Enter `5` for Quit Operation
Enter your choice : 1
Enter a integer value : 5678
5678 has been pushed
Stack Operation
Enter `1` for Push Operation
Enter `2` for Pop Operation
Enter `3` for atTop Operation
Enter `4` for Traverse Operation
Enter `5` for Quit Operation
Enter your choice : 2
Last popped item : 5678
Stack Operation
Enter `1` for Push Operation
Enter `2` for Pop Operation
Enter `3` for atTop Operation
Enter `4` for Traverse Operation
Enter `5` for Quit Operation
Enter your choice : 5
2. Stack Program in C using Linked List
#include<stdio.h>
#include<stdlib.h>
void push();
void pop();
void display();
void getValue();
struct node{
int data;
struct node * prev;
};
struct node * top = NULL;
void main(){
getValue();
}
void getValue(){
int n;
printf("nAvailable operations on stack : nEnter 1 for PushnEnter 2 for pop nEnter 3 for displaynEnter 4 for exit");
printf("nPlease enter your operation index : ");
scanf("%d",&n);
switch(n){
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:exit(0);
break;
default:printf("Error! Invalid Inputsn");
}
}
void push(){
struct node * temp;
temp = (struct node *) malloc(sizeof(struct node));
printf("Enter the node value : n");
scanf("%d",&temp->data);
temp->prev = top;
top = temp;
getValue();
}
void pop(){
if(top == NULL){
printf("Stack is Underflow n");
getValue();
}else{
printf("Element %d is deletedn",top->data);
top = top->prev;
getValue();
}
}
void display(){
struct node * temp;
if(top == NULL){
printf("No element available in the stackn");
getValue();
}else{
temp = top;
while(temp != NULL){
printf("%d-->",temp->data);
temp = temp->prev;
}
getValue();
}
}
Output
Available operations on stack :
Enter 1 for Push
Enter 2 for pop
Enter 3 for display
Enter 4 for exit
Please enter your operation index : 1
Enter the node value : 43
Available operations on stack :
Enter 1 for Push
Enter 2 for pop
Enter 3 for display
Enter 4 for exit
Please enter your operation index : 2
Element 43 is deleted
Available operations on stack :
Enter 1 for Push
Enter 2 for pop
Enter 3 for display
Enter 4 for exit
Please enter your operation index : 3
No element available in the stack
Available operations on stack :
Enter 1 for Push
Enter 2 for pop
Enter 3 for display
Enter 4 for exit
Please enter your operation index : 4