How to create a mergeable stack?

Last Updated on December 14, 2022 by Prepbytes

Let’s assume there are 2 stacks. Stack A and Stack B. Now we are going to push elements in both the stacks.

After Merge Operation we will push all elements of Stack B in Stack A.

Brief about Stack Data structure:

A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack will be on the top of the stack.

Our task is to design a stack having these functions:-

1. push(s, x): push an element x into stack s.
2. pop(s): pop element from stack s.
3. merge( s1, s2): Merge stack s2 into s1.

Logic:

1. If we choose an Array data structure to create mergeable stack then the time complexity of the merge() function will be more than O(1). Because while merging stack 2 into stack 1 firstly, we have to create a new array for stack 1 of size equal to the number of elements in both stacks and then copy all elements of both stacks in this newly created array for stack 1. So, we can see that this approach is not optimised.

2. What if we choose the Linked List data structure to create a mergeable stack?
   a. We can use the linked list data structure with two pointers.
   b. The first pointer to point the first node of the linked list and the second pointer to point the last node of the linked list so that we can easily connect a new node to the linked list i.e (we don’t have to traverse the whole linked list so that we can reach the end of the linked list to add a new node there).
   c. Another benefit of using two pointers is when the merge() function will be called at that moment we can easily join the last node of one linked list (stack 1) with the first node of another linked list (stack 2) and in this way, we will easily merge two linked list i.e two stacks.
   d. push(): To add a new node i.e (new element into the stack) to the linked list. The new node is added at the beginning of the linked list using the first pointer.
   e. pop(): To delete a node from the linked list. Remove a node from the beginning using the first pointer.
   f. merge(): This function is to merge stack 2’s linked list with stack 1’s linked list. The first pointer of the second stack is assigned to the next pointer of the last pointer of the first linked list.

Code Implementation:

#include <iostream>
using namespace std;

// node class
class node {
public:
    int data;
    node* next;
};

// mystack class
class mystack {
public:
    node* head;
    node* tail;
    // mystack constructor 
    mystack(){
        head = NULL;
        tail = NULL;
    }
};


mystack* create(){
    // creating a new stack
    mystack* ms = new mystack(); 
    return ms;
}
 
void push(int data, mystack* ms){
    // creating new node 
    node* new_Node = new node();
    // assign value 
    new_Node->data = data;
    new_Node->next = ms->head;
 
    if (ms->head == NULL){
        ms->tail = new_Node;
    }
     
    ms->head = new_Node;
}
 
int pop(mystack* ms){
    if (ms->head == NULL) {
        cout << "stack already empty" << endl;
        return 0;
    }
    else {
        node* temp = ms->head;
        ms->head = ms->head->next;
        int popped = temp->data;
        delete temp;
        return popped;
    }
}
 
// merge function to merge stack-2 into stack-1
void merge(mystack* ms1, mystack* ms2){
    if (ms1->head == NULL){
    ms1->head = ms2->head;
    ms1->tail = ms2->tail;
    return;
    }

    // merging stack-2 with stack-1
    // by linking tail node of stack-1 with tail node of stack-2
    ms1->tail->next = ms2->head;
    ms1->tail = ms2->tail;
}
 
void print(mystack* ms){
    node* temp = ms->head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}
 
int main(){
    mystack* ms1 = create();
    mystack* ms2 = create();
 
    // creating node and pushing this new node into stack
    push(6, ms1);
    push(5, ms1);
    push(4, ms1);
    push(9, ms2);
    push(8, ms2);
    push(7, ms2);

    // merge stack-2 into stack-1
    merge(ms1, ms2);

    print(ms1);
}

Output:
4 5 6 7 8 9

This article tried to discuss How to create a mergeable stack?. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.