.png)
Stack has a basic meaning in real world that is,
A structure in which a number of items are arranged in a pile(one above the other).
Whereas, In Computer Science it has a specific much similar meaning,
"Stack is an abstract data type that serves as a collection of elements"
To operate stack in data structure we have three operations which we can perform on a stack,
push - This operation is used to push(add) a new element in the stack.
pop - This operation is used to pop(remove) an element from the stack and return it's value.
peak - This operation is used to display the top most element of the stack without performing any changes in it.
Push and Pop operations in a stack are operated from the same end in a stack as stack follows Last In First Out (LIFO) procedure. The end at which these operations are performed is known as Top of the Stack.
Usually a stack is of bounded size pushing elements into it after a limit it shows up with a situation when no more elements can be pushed in, this condition is know as overflow condition of a stack.
There is one more such situation which exist in a stack is of underflow, It exists when the stack is empty, that is it doesn't have any elements to pop or peak.
Implementation
Stack can be implemented using either a linked list or an array.
However, In both cases we have similar operations that we can perform on it.
Either we use array or we use linked list the time complexity in both the cases are same.
Using Array:
An array can be used to implement a stack(bounded), as follows,
zero offset is the bottom resulting in array[0] being the first element pushed onto the stack and the last element popped off.
Here isFull and isEmpty functions are also used to figure out overflow and underflow conditions.
#include <stdio.h>
#define CAPACITY 10
#define STACKOVERFLOW -99
#define STACKUNDERFLOW -100
int s[CAPACITY];
int tos=-1;
//checks if the stack is empty or not
//if empty, then return 1 , else return 0
int isEmpty()
{
if(tos==-1)
return 1;
return 0;
}
//checks if the stack is full or not
//if full, then return 1 , else return 0
int isFull()
{
if(tos==CAPACITY-1)
return 1;
return 0;
}
int push(int element)
{
if(isFull())
return STACKOVERFLOW;
tos++;
s[tos]=element;
return 1;
}
int pop()
{
int result;
if(isEmpty())
return STACKUNDERFLOW;
result=s[tos];
tos--;
return result;
}
int peek()
{
if(isEmpty())
return STACKUNDERFLOW;
return s[tos];
}
int main()
{
int choice,ele;
do{
printf("\nEnter your choice : 1.Push 2.Pop 3.Peek 4.Exit");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter element");
scanf("%d",&ele);
int r=push(ele);
if(r==1)
printf("\nPush Successful");
else
printf("\nStack Overflow");
break;
case 2:
r=pop();
if(r==STACKUNDERFLOW)
printf("\nStack underflow");
else
printf("\n%d popped ",r);
break;
case 3:
r=peek();
if(r==STACKUNDERFLOW)
printf("\nStack underflow");
else
printf("\nTop of stack element=%d",r);
break;
case 4:
exit(0);
}
}while(1);
return 0;
}Using Linked List:
Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically.
However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory.
Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;
void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;
}
printf("Item pushed");
}
}
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}Follow Programmers Door for more.
Commentaires