Introduction to Stacks in Data Structures

Stack in Data Structures

Stack is one of the basic linear Data structures that we use for storing our data. Data in a stack is
stored in a serialized manner. One important thing about using a Stack is that the data first entered in
the stack will be at the last of the stack. This is one of the reason why we also called Stack a LIFO Data
Structure, i.e; Last in First Out. We’ll be discussing more about this feature later in this article.

Basic Terminology of Stack

Before we move on further with understanding the Stack Data Structure, we need to learn about the
basic terminology that is associated with this data structure so that understanding stack will be a little
easy for us.

The basic terminology that we will be using in Stack is :

 Top – This refers to the topmost element of the stack, or in other words the element last
entered in the stack.

 Push () – This is one of the operation that we can perform on stack, for inserting data in this
data structure.

 Pop () – This operation deals with deleting the data from the stack. It deletes the top-most data
from the stack.

 Peek () – This operation helps us in looking at the topmost element of the data without
removing it from the stack.

A stack may be implemented to have a bounded capacity. If the stack is full and does not contain
enough space for push operation, the stack is then considered to be in an overflow state.

Below is simple representation of a stack with push and pop operations.Limitation in using StackOne of
the major limitation in using stack is that it only operates on the topmost element of the stack.

Time Complexity For Stack

Best :O(1) Average: O(n) Worst: O(n)

Space Complexity: O(1)

Average Comparisons

(n+1)/2

Applications of Stacks in Data Structures

There a lot of places where we use stack without even realizing it. Let’s see some of the most common
uses of stack data structure.

Real life examples of Stack

1. Stacking up dishes after washing them.

2. Deck of cards

3. Stacking a pile of boxes in our store rooms.

4. Libraries stack pile of books and articles.

Some Coding/Programming Applications of Stack

1. Recursion

2. Backtracking

3. Memory management

4. Process Management

Advantages of Using Stack over other data structures

 Manages the data in a Last in First out (LIFO) method which is not possible with Linked list and
array.

 When a function is called the local variables are stored in a stack, and it is automatically
destroyed once returned.

 A stack is used when a variable is not used outside that function.

 It allows you to control how memory is allocated and deallocated.

 Stack automatically cleans up the object.

 Not easily corrupted

 Variables cannot be resized.

Disadvantages of Using Stack over other data structures

 Stack memory is very limited.

 Creating too many objects on the stack can increase the risk of stack overflow.

 Random access is not possible.

 Variable storage will be overwritten, which sometimes leads to undefined behavior of the
function or program.
  The stack will fall outside of the memory area, which might lead to an abnormal termination.

Operations on a Stack

There are many operations that can be used to manipulate a stack.

A stack is a data structure in which the operations are executed in constant time.

There are a number of operations that can be performed on a stack, but there are two
major operations that are used to manipulate a stack.

These operations are:

 Push()
 Pop()
Push()

 The push operation in a stack is synonymous to insertion in a data structure.

 In simpler words, inserting a new element in a stack is known as push.
 The time complexity of the Push() operation is O(1), i.e , it occurs in constant
time.

Let us understand how a push() operation works. Let us consider we have to push a
given number of elements in the stack.

The elements to be inserted are: 12 , 08 , 21 , 33 , 18 , 40.

Step 1:

 Initially we have an empty stack.

 Top = NULL.
Step 2:

 Push the element 12 in the stack.

 Top = 12

Step 3:

 Push the element 08 in the stack.

 Top = 08.

Step 4:

 Push the element 21 in the stack.

  Top = 21

Step 5:

 Push the element 33 in the stack.

 Top = 33.

Step 6:

 Push the element 18 in the stack.

 Top = 18
Step 7:

 Push the element 40 in the stack.

 Top = 40.

Step 8:

 Final stack is shown as follows.

 Top = 40
Pop()

 The Pop operation in a stack is synonymous to deletion in a data structure.

 In simpler words, deleting an existing element from a stack is known as pop.
 The time complexity of the Pop() operation is O(1), i.e , it occurs in constant time.

Let us understand how a pop() operation works. Let us consider we have to pop a given
number of elements in the stack.

The elements to be deleted from the stack are : 40 , 18 , 33.

Step 1:

 The first element to be deleted from the stack is 40.

 We can see the value of top points to 40.
 We perform the pop operation and the element 40 is popped out off the stack.
 The remaining elements are shown in the image.
 Top = 18.
Step 2:

 The second element to be deleted from the stack is 18.

 We can see the value of top points to 18.
 We perform the pop operation and the element 18 is popped out off the stack.
 The remaining elements are shown in the image.
 Top = 33.

Step 3:
  The next element to be deleted from the stack is 33.
 We can see the value of top points to 33.
 We perform the pop operation and the element 33 is popped out off the stack.
 The remaining elements are shown in the image.
 Top = 21.

Code for Stack in C++ (using Class)

// Cpp Program for Implmentation of stack (array) using structure
#include<iostream>
using namespace std;

class Stack
{
public:
int top;
int maxSize;
int* array;
Stack(int max)
{
top=-1;
maxSize=max;
array=new int[max];
}
int isFull()
{
if(top==maxSize-1)
cout<<"Will not be able to push maxSize reached"<<endl;
return top==maxSize-1;
}

int isEmpty()
 {
if(top==-1)
cout<<"Will not be able to pop minSize reached"<<endl;
return top==-1;
}
void push(int item)
{
if(isFull()) return;
array[++top]=item;
cout<<"We have pushed "<<item<<" to stack"<<endl;
}
int pop()
{
if(isEmpty()) return INT_MIN;
return array[top--];
}
int peek()
{
if(isEmpty()) return INT_MIN;
return array[top];
}
};

int main()
{
Stack stack(10);
stack.push(5);
stack.push(10);
stack.push(15);
int flag=1;
while(flag)
{
if(!stack.isEmpty())
cout<<"We have popped "<< stack.pop()<<" from stack"<<endl;
else
cout<<"Can't Pop stack must be empty\n";

cout<<"Do you want to Pop again? Yes: 1 No: 0\n";

cin>>flag;
}

Output

We have pushed 5 to stack

We have pushed 10 to stack
We have pushed 15 to stack
We have popped 15 from the stack
Do you want to Pop again? Yes: 1 No: 0
0
____________________________________________________________________________
Implementation of a stack using an Array (Without Class)

#include<iostream>
using namespace std;
#define size 20

int Stack[size],top_of_stack;

void Push(int [],int); //to insert elements in the stack

void Pop (int []);//to delete elements from the stack
void display(int []); //to display the elements

int main()
{
int num=0;
int option=0;
top_of_stack=-1;

while(1)
{
cout<<"\n 1: Push \n 2: Pop \n 3: Display \n 4: Exit \n Enter one of your
choices: ";
cin>>option;

switch(option)
{
case 1:
cout<<"Enter the item you want to insert :";
cin>>num;
Push(Stack,num);
break;

case 2:
Pop(Stack);
break;

case 3:
display(Stack);
break;

case 4:
exit(0);

default:
cout<<"\nPlease enter a correct option\n";
break;
 }
}

void Push(int stack[],int num)

{
if(top_of_stack==size-1)
{
cout<<"\nCannot add element, Stack is full\n";
return;
}
top_of_stack++;
stack[top_of_stack]=num;
}

void Pop(int stack[])

{
int del_num;
if(top_of_stack==-1)
{
cout<<"Empty Stack.\n";
return;
}

del_num=stack[top_of_stack];
top_of_stack--;
cout<<"Element deleted: "<<del_num<<endl;
return;
}

void display(int stack[])

{
int i=0;
if(top_of_stack==-1)
{
cout<<"Empty Stack .\n";
return;
}

cout<<"Top of stack is: "<<stack[top_of_stack]<<endl;

for(i = top_of_stack ; i >=0 ; i--)
{
cout<<" "<<stack[i]<<" ";
}
cout<<"\n\n";
}
Output

1: Push
2: Pop
3: Display
4: Exit
Enter one of your choices: 1
Enter the item you want to insert :1
1: Push
2: Pop
3: Display
4: Exit

Enter one of your choices: 1

Enter the item you want to insert :2
1: Push
2: Pop
3: Display
4: Exit
Enter one of your choices: 1

Enter the item you want to insert :3

1: Push
2: Pop
3: Display
4: Exit
Enter one of your choices: 2

Element deleted: 3
1: Push
2: Pop
3: Display
4: Exit
Enter one of your choices: 3

Top of stack is:

2 1

1: Push
2: Pop
3: Display
4: Exit
Enter one of your choices: 4

Further Reading and Visualization:

 https://www.cs.usfca.edu/~galles/visualization/StackArray.html

 https://www.youtube.com/watch?v=DKlXEAZYB7I&list=PLLOxZwkBK52Akgqf4oSWPOQO9ROWS
_9rc&index=14