Mergeable Stack

Solution

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

1. Remove old arrays.
2. Make a new array for s1 with the same size as the existing array for s1 plus the size of s2.
3. 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.

1. Make two stacks called s1 and s2.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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);
}

You can also try this code with Online C++ Compiler

Run Code

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.

Check out this array problem - Merge 2 Sorted Arrays

Must Read Stack Operations

Frequently Asked Questions

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++.

After reading about how to merge two stacks, are you not feeling excited to read/explore more articles on the topic of DSA? Don't worry; Coding Ninjas has you covered. To learn, see the Stack in C++ (STL), Linked List, Implementation of Stack, Problems of top tech companies for practice, Coding Interview Questions and Data Structures & Algorithms.

You can also consider our Mern Stack Course to give your career an edge over others.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!