How to create mergeable stack in C++

Hi there. Today we will see how to merge two stacks in O(1) time complexity using C++. Since we have to solve this in such an efficient way, we won’t be able to use arrays here, because operations with arrays will take O(n) time.

Instead, we have to use linked lists. Because we can merge two stacks easily as well do insertion operations in O(1) time only. So, we will implement our method with linked lists.

We will see how to push and pop in 1 stack, and how to merge two stacks. We will keep two-pointers, 1st will point at the start, and the 2nd will point at the end. The 2nd will help in merging, while the 1st one will help for insertion operations. Now let’s look at the implementation.

Mergeable stack in C++

We will create a function for every operation, because there are a lot of operations. So dividing them into small functions will make it easy to understand. Let’s look at the code now.

#include<bits/stdc++.h> 
using namespace std; 
  
class node 
{ 
public: 
    int num; 
    node* next; 
}; 
  
class newstack 
{ 
public: 
    node* head; 
    node* tail; 
  
    newstack() 
    { 
        head=NULL; 
        tail=NULL; 
    } 
}; 
  
newstack* create() 
{ 
    newstack* stk=new newstack(); 
    return stk; 
} 
  
void push(int num,newstack* stk) 
{ 
    node* temp=new node(); 
    temp->num=num; 
    temp->next=stk->head; 
  
    if (stk->head==NULL)
    {
    stk->tail=temp; 
    }   
       
    stk->head=temp; 
} 
  
int pop(newstack* ms) 
{ 
    if (ms->head==NULL) 
    { 
        cout<<"stack underflow"<<endl; 
        return 0; 
    } 
    else 
    { 
        node* temp=ms->head; 
        ms->head=ms->head->next; 
        int popped=temp->num; 
        delete temp; 
        return popped; 
    } 
} 
  
void merge(newstack* ms1,newstack* ms2) 
{ 
   if(ms1->head==NULL) 
   { 
       ms1->head=ms2->head; 
       ms1->tail=ms2->tail;  
       return; 
   } 
     
   ms1->tail->next=ms2->head; 
   ms1->tail=ms2->tail;  
} 
  
void print(newstack* ms) 
{ 
    node* temp=ms->head; 
    while (temp!=NULL) 
    { 
        cout<<temp->num<<" "; 
        temp=temp->next; 
    }  
} 
  
int main() 
{ 
    newstack* stack1=create(); 
    newstack* stack2=create(); 
    
    int n1,n2,temp;
    cout<<"enter sizes of both the stacks"<<endl;
    cin>>n1>>n2;
    cout<<"enter elements of 1st stack:"<<endl;
    for(int i=1;i<=n1;i++)
    {
    	cin>>temp;
    	push(temp,stack1);
    }
    cout<<"enter elements of 2nd stack:"<<endl;
    for(int i=1;i<=n2;i++)
    {
    	cin>>temp;
    	push(temp,stack2);
    }
  
    merge(stack1,stack2);
    cout<<"The result after merging both stacks:"<<endl; 
    print(stack1); 
}

First, we input the content of both the stacks after creating two stacks. Then we perform the merge operation which merges both of them. Let’s look at the output now.

enter sizes of both the stacks
5
5
enter elements of 1st stack:
5 4 3 2 1
enter elements of 2nd stack:
10 9 8 7 6
The result after merging both stacks:
1 2 3 4 5 6 7 8 9 10

As you can see, the elements of 1st stack appear first, them the elements of 2nd array. The elements appear in reverse order because each element is being added to the top, and print is happening from top to bottom.

Also read: Sort stack using temporary Stacks in C++

Leave a Reply

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