Stack in C Programming

Filed Under: C Programming

A stack is a linear data structure, collection of items of the same type.

Stack follows the Last In First Out (LIFO) fashion wherein the last element entered is the first one to be popped out.

In stacks, the insertion and deletion of elements happen only at one endpoint of it.


1. Operations performed on Stacks

The following are the basic operations served by the Stacks.

  • Push: This function adds an element to the top of the Stack.
  • Pop: This function removes the topmost element from the stack.
  • IsEmpty: Checks whether the stack is empty.
  • IsFull: Checks whether the stack is full.
  • Top: Displays the topmost element of the stack.

2. Working of Stacks

Initially, we set a pointer Peek/Top to keep the track of the topmost item in the stack.

Initialize the stack to -1. Then, we check whether the stack is empty through the comparison of Peek to -1 i.e. Top == -1

As we add the elements to the stack, the position of the Peek element keeps updating every time.

As soon as we pop or delete an item from the set of inputs, the top-most element gets deleted and thus the value of Peek/Top gets reduced.


3. Implementing Stack in C

Stacks can be represented using structures, pointers, arrays or linked lists.

Here, We have implemented stacks using arrays in C.

#include<stdio.h>

#include<stdlib.h>
 
#define Size 4 
 
int Top=-1, inp_array[Size];
void Push();
void Pop();
void show();
 
int main()
{
	int choice;
	
	while(1)	
	{
		printf("\nOperations performed by Stack");
		printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
		printf("\n\nEnter the choice:");
		scanf("%d",&choice);
		
		switch(choice)
		{
			case 1: Push();
					break;
			case 2: Pop();
					break;
			case 3: show();
					break;
			case 4: exit(0);
			
			default: printf("\nInvalid choice!!");
		}
	}
}
 
void Push()
{
	int x;
	
	if(Top==Size-1)
	{
		printf("\nOverflow!!");
	}
	else
	{
		printf("\nEnter element to be inserted to the stack:");
		scanf("%d",&x);
		Top=Top+1;
		inp_array[Top]=x;
	}
}
 
void Pop()
{
	if(Top==-1)
	{
		printf("\nUnderflow!!");
	}
	else
	{
		printf("\nPopped element:  %d",inp_array[Top]);
		Top=Top-1;
	}
}
 
void show()
{
	
	
	if(Top==-1)
	{
		printf("\nUnderflow!!");
	}
	else
	{
		printf("\nElements present in the stack: \n");
		for(int i=Top;i>=0;--i)
			printf("%d\n",inp_array[i]);
	}
}

Output:

Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice:1

Enter element to be inserted to the stack:10

Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice:3

Elements present in the stack: 
10

Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice:2
Popped element:  10

Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End

Enter the choice:3
Underflow!!

4. Time Complexity of Stack Operations

As mentioned above, only a single element can be accessed at a time in Stacks.

While performing push() and pop() operations on the stack, it takes O(1) time.


5. Applications of Stack

As soon as the compiler encounters a function call, it gets pushed into the stack.

In the case of nested functions, the inner functions get executed before the outer functions. This is totally managed by stacks.

The Stack is used to solve a few of the general problems like:

  1. Tower of Hanoi 
  2. N queens problem
  3. Infix to prefix conversion, etc.

6. Conclusion

Thus, in this article, we have understood the concept of Stack data structure and its implementation using Arrays in C.


7. References

Official Documentation of C++ Stacks

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages