Stack In Data Structure Using Array

Ok, so assume a pile of plates in a cafeteria is a good example of a Stack. The plates are added to the stack as they are cleaned and they are placed on the top. when a plate, is required it is taken from the top. The first plate placed on the stack is the last one to be used.

Now, here we discussed the stack in detail.

What is Stack?

A stack is a linear data structure in which insertion and deletion are done at one end, called top. The last element inserted is the first one to be deleted. Hence, it is called Last in First out(LIFO) or First in Last out(FILO).

Basic Operations of Stack:

1. Push(): Inserts element to the top of a stack.
2. Pop(): Remove an element from the top of a stack.

3. Peek()/top(): Get the value of the top element without removing it.

4. Is Empty(): Check if the stack is empty.

5. Is Full(): Check if the stack is full.

NOTE:

Stack Overflow: Trying to push an element in a full stack is called stack overflow.

Stack underflow: Trying to pop out an element from a empty stack is called stack underflow.

The steps involved in the PUSH operation:

1. Before inserting an element in a stack , we have to check whether the stack is full or not .
2. If we try to insert an element in a full stack then the Overflow condition occurs.
3. When we initialize a stack ,we set the value of top as -1 {top=-1}, to check that the stack is empty.
4. When we pushed a new element in a stack ,first, the value of top gets incremented top=top+1 .And the element will placed at the new position of top.

5. The elements will be inserted until we reach the maximum size of the stack.

The steps involved in the POP operation:

1. Before deleting element from the stack , we have to check the stack is empty or not.
2. If we try to delete an element form the empty stack , then the Underflow condition occurs.
3. If the stack in not empty , we first access the element which is pointed by the top.

4. Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Stack implementation:

1. Simple Array based .
2. Dynamic Array based.
3. Using Linked list .

Stack Implementation Using Array in “c”:

#include<stdio.h>
int stack[5]; //declaring globally
int top=-1;
void display() // function for display
{
 int i;
 printf(“\n********* stack status*********\n”);
 for(i=top;i>=0;i — )
 {
 printf(“%d\n”,stack[i]);
 }
 
}
void push() //function for inserting 
{
 int element;
 printf(“Enter the element: “);
 scanf(“%d”,&element);
 
 if(top==5–1)
 {
 printf(“Stack Overflow”); //if stack is full
 display();
 }
 
 else
 {
 top++;
 stack[top]=element; //insert element in the stack
 display();
 }
}
void pop() //function for deletion
{
 int temp;
 if(top==-1)
 {
 printf(“Stack underflow”); //if stack is empty
 display();
 }
 else
 {
 temp=stack[top];
 top — ;
 printf(“The popped item is %d”,temp);
 display();
 }
}
void peek() //value of the top element
{
 if(top==-1)
 {
 printf(“stack empty”);
 display();
 }
 else
 {
 printf(“\n%d\n”,stack[top]);
 display();
 }
}
int main()
{
 int choice=0 ;
printf(“Enter 1 for push\n”); //for push
 printf(“Enter 2 for pop\n”); //for pop
 printf(“Enter 3 for peek\n”); //for peek
 printf(“Enter 4 for break\n”); //for break
 
 while(1)
 {
 printf(“Enter your choice “);
 scanf(“%d”,&choice);
 
 if(choice==1)
 {
 push();
 }
 else if(choice==2)
 {
 pop();
 }
 else if(choice==3)
 {
 peek();
 }
 if(choice==4)
 {
 break;
 }
 
 }
}

Applications of Stack:

1. String reversal: Stack is also used for reversing a string.
2. UNDO/REDO: It can also be used for performing UNDO/REDO operations.

3. DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.

4. Page visited history in a Web browser.

Time Complexity:

1. push() = O(1)
2. pop()=O(1)
3. peek()=O(1)

space complexity:

Let, n be the number of elements in the stack .

here, space complexity = O(n)