Stack implementation in C

Stack implementation in C

Stack stores the data in a particular order. It is a linear data structure that follows the principle of the Last In First Out (LIFO) technique where the elements added at the end will be the first ones to eliminate while the elements added in the beginning will be the last ones to be eliminated.

Two particular operations can be performed on the stack concept, such as Push operation and pop operation. The push operation performed will do the following: inserts an element into the stack.

On the other hand, the pop operation pops or removes the element from the inserted stack. Two other critical undesirable conditions will be occurred at times, like when the stack is complete. Yet, the programmer tries to insert another element, and then the stack overflow happens as the memory space will not be available. On the contrary, if the stack is empty but the developer tries to pop the operation, then it results in the stack underflow.

Using a stack in C requires no extra memory for storing the pointers. But the stack size will be pre-determined, and it is not possible to increase or decrease the size of the stack.

Implementation of the stack:

The essential functions that are allowed in the stack are:

• Push: the push operation will add or insert an element on the top of the stack.
• Pop: the pop operation will remove the element in a mannered way
• Top: the top function displays the element which is present at the top of the stack.
• isEmpty: this function checks whether the stack is empty or not.
• isFull: this function checks whether the stack is complete or not.

E.g.:

 #include<stdio.h>
 #include<stdlib.h>
 #define MAX 5 //Maximum number of elements that can be stored
 int top=-1,stack[MAX];
 void push();
 void pop();
 void display();
 void main()
 {
 int ch;
 while(1) //infinite loop, will end when the choice will be 4
 {
 printf("\n*** Stack Menu ***");
 printf("\n\n1.Push\n2.Pop\n3.Display\n4.Exit");
 printf("\n\nEnter your choice(1-4):");
 scanf("%d",&ch);
 switch(ch)
 {
 case 1: push();
 break;
 case 2: pop();
 break;
 case 3: display();
 break;
 case 4: exit(0);
 default: printf("\nWrong Choice!!");
 }
 }
 }
 void push()
 {
 int val;
 if(top==MAX-1)
 {
 printf("\nStack is full!!");
 }
 else
 {
 printf("\nEnter element to push:");
 scanf("%d",&val);
 top=top+1;
 stack[top]=val;
 }
 }
 void pop()
 {
 if(top==-1)
 {
 printf("\nStack is empty!!");
 }
 else
 {
 printf("\nDeleted element is %d",stack[top]);
 top=top-1;
 }
 }
 void display()
 {
 int i;
 if(top==-1)
 {
 printf("\nStack is empty!!");
 }
 else
 {
 printf("\nStack is...\n");
 for(i=top;i>=0;--i)
 printf("%d\n",stack[i]);
 }
 } 

Output:

 *** Stack Menu ***
 1.Push
 2.Pop
 3.Display
 4.Exit
 Enter your choice(1-4):1
 Enter element to push: 3
 *** Stack Menu ***
 1.Push
 2.Pop
 3.Display
 4.Exit
 Enter your choice(1-4): 1
 Enter element to push: 6
 *** Stack Menu ***
 1.Push
 2.Pop
 3.Display
 4.Exit
 Enter your choice(1-4): 1
 Stack is...
 6  3
 *** Stack Menu ***
 1.Push
 2.Pop
 3.Display
 4.Exit
 Enter your choice(1-4): 2
 Deleted element is 6
 *** Stack Menu ***
 1.Push
 2.Pop
 3.Display
 4.Exit
 Enter your choice(1-4): 5
 Wrong choice
 *** Stack Menu ***
 1.Push
 2.Pop
 3.Display
 4.Exit
 Enter your choice(1-4): 4 

There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate which is at the top is the first to be removed, i.e., the plate placed at the bottommost position remains in the stack for the most extended period of time. So, it can be simply seen to follow the LIFO/FILO order.

Time complexity:

While performing the push or the pop operations, it always takes O(1) time.

Applications:

Stack is generally used in problems such as:

• Tower of Hanoi
• Infix conversions and prefix conversions
• Queens problem
• Balancing the symbols
• Undo and redo operations while editing and photoshopping
• Forward and backward features in the web browser.
• Tree traversals
• Histogram problems.
• In memory management, any modern computer uses a stack as the primary management for a running purpose. Each program that is running in a computer system has its memory allocations
• String reversal is also another application of stack. Here one by one, each character gets inserted into the stack. So the string’s first character is on the bottom of the stack, and the last element of a string is on the top of the stack. So after Performing the pop operations on the stack, we get the string in reverse order.