Introduction
A stack is a linear data structure, a collection of items of the same type.
In a stack, the insertion and deletion of elements happen 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 becomes the first item that will be “popped” out of the stack.
To reach the oldest entered item, you must pop all the previous items.
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
Operations Performed on Stacks
The following are the basic operations served 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.
top: Displays the topmost element of the stack.
Underlying Mechanics of Stacks
Initially, a pointer (top) is set to keep track of the topmost item in the stack. The stack is
initialized to -1.
Then, a check is performed to determine if the stack is empty by comparing top to -1.
As elements are added to the stack, the position of top is updated.
As soon as elements are popped or deleted, the topmost element is removed, and the
position of top is updated.
Implementing Stack 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 presents the user with four options:
1. Push the element
2. Pop the element
3. Show
4. End
It waits for the user to input a number.
If the user selects 1, the program handles a push(). First, it checks whether top is
equivalent to SIZE - 1. If true, "Overflow!!" is displayed. Otherwise, the user is
asked to provide the new element to add to the stack.
If the user selects 2, the program handles a pop(). First, it checks to see if top is
equivalent to -1. If true, "Underflow!!" is displayed. Otherwise, the topmost element
is removed, and the program outputs the resulting stack.
If the user selects 3, the program handles a show(). First, it checks to see if top is
equivalent to -1. If true, "Underflow!!" is displayed. Otherwise, the program outputs
the resulting stack.
If the user selects 4, the program exits.
Execute 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 on the 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
Popped element: 10
Now, the stack is empty. Attempt to 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!!
Continue to experiment with this program to understand how a stack works.
Time Complexity of Stack Operations
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.
