What is Stack Data Structure?

Stack is a linear data structure which follows a particular order in which the operations are performed. It is just like a pile of plates kept on top of each other. It works on the principle of Last-In-First-Out (LIFO) – the last item that was placed is the first item to go out. It is an Abstract Data Type. It is commonly used in most programming languages. It is named stack as it behaves like a real-world stack. For example, a deck of plates.

Working of Stack

Stack data structure works on LIFO basis. LIFO stands for Last-in-first-out. Here, the element which is inserted at last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation. It has only one pointer TOP that points the last or top most element of Stack. Insertion and Deletion in stack can only be done from top only.

TOP pointer is the most important thing here. We have to set its value to -1 at the time of stack initialization so that we can check whether the stack is empty or not by comparing TOP == -1.

Whenever an item is inserted, increase the value of TOP by 1 and place the new element in the position pointed by TOP.

Whenever an element is removed, return the element pointed to by TOP and decrease its value by 1.

Before push() operation must check if stack is already full. [Stack Overflow Condition]

Before pop() operation must check if stack is already empty. [Stack Underflow Condition]

Stack Operations

Stack is an ADT (Abstract Data structure). We can implement this linear structure using array, linked list or some other way. It is supported in different programming languages like C, C++, Java, C# etc. We can perform following operations in a stack:

Push()

Push() is used to add an element to the top of stack. Before inserting an element into the stack, we must check for stack overflow i.e. whether the stack has space to add an item or its already full.

void push(int data) 
{
if(!isFull()) {
top = top + 1;
stack[top] = data;
} 
else 
{
printf("Stack is already full.\n");
}
}

Pop()

Pop() is used to remove an element from the top of stack. Before popping an element from the stack, we must check for stack underflow i.e. whether the stack is empty or it contain item to remove.

int pop(int data)
{
if(!isempty())
{
data = stack[top];
top = top - 1;
return data;
} 
else 
{
printf("Stack is empty. Nothing to remove.\n");
}
}

IsEmpty()

IsEmpty() operation is used to check whether stack is empty or not. It check out for stack underflow.

int isempty() {
if(top == -1)
return 1;
else
return 0;
}

IsFull()

IsFull() operation is used to check whether stack is full or it has space to add more item. It check out for stack overflow.

int isfull() {
if(top == MAXSIZE)
return 1;
else
return 0;
}

Peek()

Peek() is used to retrieve the value of the top element without removing it. It returns the value of top of the stack element.

int peek() {
return stack[top];
}

Stack Implementation Example using C

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define MAX 10

struct stack
{
int items[MAX];
int top;
};

typedef struct stack st;

void createEmptyStack(st *s)
{
s->top=-1;
}

int isfull(st *s)
{
if (s->top==MAX-1)
return 1;
else
return 0;
}

int isempty(st *s)
{
if (s->top==-1)
return 1;
else
return 0;
}

void push(st *s)
{
int newitem;
printf("Enter item to be inserted: ");
scanf("%d",&newitem);
if (isfull(s))
{
printf("STACK FULL");
}
else
{
s->top++;
s->items[s->top]=newitem;
}
}

void pop (st *s)
{
if (isempty(s))
{
printf("\n STACK EMPTY \n");
}
else
{
printf("Item popped= %d",s->items[s->top]);
s->top--;
}
}

void main()
{
int ch;
int loop;
loop=1;
st *s;

createEmptyStack(s);

do
{
printf("\n ***STACK OPERATIONS");
printf("\n 1. PUSH");
printf("\n 2. POP");
printf("\n 3. EXIT");
printf("\n ***************");

printf("\n Enter your choice: ");
scanf("%d", &ch);

switch (ch)
{
case 1:
push(s);
break;
case 2:
pop(s);
break;
case 3:
printf("THANK YOU");
loop=0;
exit(0);
default:
printf("Invalid choice");
}
} while(loop);
getch();
}

Applications of Stack

Through it is a simple data structure and easy to implement, it is beneficial as well. Most common use of this data structure are:

Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver
Forward and backward feature in web browsers
In Graph Algorithms like Topological Sorting and Strongly Connected Components
Infix to Postfix /Prefix conversion
Balancing of symbols
Redo-undo features at many places like editors, photoshop.

Was this article helpful? Must share your views in the comment section below. Keep visiting our Tech Blogs to stay updated with our latest blog posts.

Stack | Data Structure