This blog covers a stack problem which is commonly called a mergeable stack. Stacks are among the most important and often asked data structures in programming contests and technical interviews. There are various standard stack problems and techniques. This blog tackles a coding task that involves how to merge two stacks.

Probleme Statement

Ninja has been given a problem in which he has to perform the following operations

push(Stack s, x): x is added to stack s.

pop(Stack s): The top item in the stack is removed.

merge(Stack s1, Stack s2): Merge s2's contents into s1.

The above operations should have a time complexity of O(1).

Example:

Here is an example to show mergeable stack. Let the operations be

push(3, s1);

push(2, s1);

push(1, s1);

push(4, s2);

push(5,s2);

push(6,s2);

merge(s1, s2);

display(s1);

The mergeable stack and the output of the above operation is: 1 2 3 6 5 4

Solution

If we use the array implementation of the stack, we cannot merge in O(1) time since we must do the following stages.

Remove old arrays.

Make a new array for s1 with the same size as the existing array for s1 plus the size of s2.

Copy the previous contents of s1 and s2 to the new array for s1.

We can use a circular linked list to do this. The goal is to maintain track of the linked list's last node. The top of the stack is indicated by the next of the previous node.

Algorithm

Here, we first make two stacks and then attempt to make a mergeable stack.

Make two stacks called s1 and s2.

Create a push function that takes an integer value and a stack as parameters. Create a node in it. Update the new node's data as an integer and link it to the top of the stack.

If the top of the stack is null, the tail of the stack is updated as a new node. Otherwise, create a new node at the top of the stack.

Make a function called pop that takes a stack as an argument. If the stack's head is null, display "stack underflow," else store the stack's head in a new node and update the head as next to the head. Return the new node's data and remove the node.

Make a function merge that takes two stacks as parameters. Determine whether the head of stack 1 is null. It returns after updating its head as the head of stack two and tail as the tail of stack 2.

Otherwise, make the next of the tail of stack one the head of stack two and the tail of stack one the tail of stack 2.

Code

// C++ program to create mergeable stack
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node* next;
};
// class for mergeable stack
class mystack {
public:
node* head;
node* tail;
mystack()
{
head = NULL;
tail = NULL;
}
};
mystack* create()
{
mystack* ms = new mystack(); // creating a new stack for mergeable stack
return ms;
}
void push(int data, mystack* ms)
{
node* temp = new node();
temp->data = data;
temp->next = ms->head;
// when pushing first element in the stack the tail
// must be pointed by that first element
if (ms->head == NULL)
ms->tail = temp;
ms->head = temp;
}
int pop(mystack* ms)
{
if (ms->head == NULL) {
cout << "stack underflow" << endl;
return 0;
}
else {
node* temp = ms->head;
ms->head = ms->head->next;
int popped = temp->data;
delete temp;
return popped;
}
}
// function for mergeable stack
void merge(mystack* ms1, mystack* ms2)
{
if (ms1->head == NULL)
{
ms1->head = ms2->head;
ms1->tail = ms2->tail;
return;
}
ms1->tail->next = ms2->head;
ms1->tail = ms2->tail;
}
void display(mystack* ms)
{
node* temp = ms->head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
// main function for mergeable stack
int main()
{
mystack* ms1 = create();
mystack* ms2 = create();
push(10, ms1);
push(11, ms1);
push(12, ms1);
push(13, ms2);
push(14, ms2);
push(15, ms2);
merge(ms1, ms2);
display(ms1);
}

Output

The image below shows the merged stack for the problem which is to create a mergeable stack.

Complexity

Here is the complexity analysis to create the mergeable stack.

Time Complexity: O(1) because all operations use constant time.

Auxiliary Space: O(1) since we are not taking up any more space.

Explain why the Stack data structure is recursive.

A stack is a recursive data structure because it is either empty or made up of a top and the remainder, which is a stack in and of itself.

Why are stacks beneficial?

They're convenient since they allow you to insert or remove from the front of a data structure in constant time O(1) operations. A stack is commonly employed in compilers to ensure that the brackets and parentheses in a code file are balanced, i.e., have an opening and closing counterpart. Stacks can also be used to evaluate mathematical expressions.

How is the stack implemented?

Array, Structure, Pointer, and Linked List can all be used to implement a stack. Stacks can be either fixed in size or dynamically resized. The stack will be implemented using arrays in this case, resulting in a fixed-size stack implementation.

What is the stack overflow condition?

A stack overflow is an unpleasant event that occurs when a computer programme attempts to use more memory space than the call stack has available. The call stack is a buffer in programming that holds requests that must be addressed. The size of a call stack is determined by several variables.

What are the stack's limitations?

Stack memory is really restricted. Putting too many things on the stack raises the possibility of stack overflow. It is not feasible to gain access at random. Variable storage will be rewritten, resulting in unpredictable behaviour of the function or application.

Conclusion

In this article, we have extensively discussed the logic of how to merge two stacks and the code for it in c++.