How to implement Stack in C programming

Introduction

A Stack is a linear data structure, a collection of items of the same type. In a Stack, insertion and removal of elements occur only at one endpoint. The behavior of a Stack is described as “last in, first out” (LIFO). When an element is “PUSHED” onto the stack, it is the first item to be “popped” off the stack. To reach the oldest inserted item, you have to unpop all the previous items.

In this article, you will learn about the concept of the stack data structure and its implementation using arrays in C.

Operations performed on Stacks

Below are the basic operations provided by Stacks.

• push: adds an element to the top of the stack.
• pop: Removes the topmost element from the stack.
• isEmpty: Checks whether the stack is empty.
• isFull: Checks whether the stack is full or not.
• top: Displays the topmost element of the stack.

The underlying mechanics of Stacks

Initially, a pointer (up) is set to track the topmost item in the stack. The stack is initialized to -1.

Then, the stack is checked for emptyness by comparing top and -1.

As elements are added to the stack, the top position is updated.

As soon as elements are popped or deleted, the topmost element is removed and the top position is updated.

Stack implementation in C

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

This example implements 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("\nPerform operations on the 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 the element to be added onto 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]);
}
}

This program provides the user with four options:

• Pushing an element
• Popping an element
• Show
• End

Waits for the user to enter a number.

• If the user selects 1, the program does a push(). It first checks whether top is equal to SIZE – 1. If true, “Overflow!!” is displayed. Otherwise, the user is prompted to provide a new element to add to the stack.
• If the user selects 2, the program handles a pop(). It first checks whether top is equal to -1. If true, “Underflow!!” is displayed. Otherwise, the top element is removed and the program outputs the resulting stack.
• If the user selects 3, the program handles a show(). It first checks whether top is equal to -1. If true, “Underflow!!” is displayed. Otherwise, the program outputs the resulting stack.
• If the user selects 4, the program exits.

Run this code to push() the number “10” onto the stack:

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 1
Enter the element to be inserted onto the stack: 10

Then show the elements in Stack():

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Elements present in the stack: 
10

Then pop():

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 2

Now, the stack is empty. Try Pop() again:

Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Underflow!! Your code... */

Continue experimenting with this program to understand how a stack works.

Time complexity of stack operations

Only one element can be accessed at a time in stacks.

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

Result

In this article, you learned about the concept of the stack data structure and its implementation using arrays in C.