K stacks in a single array

Solution

The concept is to efficiently implement k stacks in a single array using two other arrays. This may not make sense for integer stacks, but stack elements can be enormous, such as employee, student, or other stacks with hundreds of bytes per item. We employ two integer arrays as extra space for such huge stacks. Therefore the extra space needed is very little.

The two more arrays are as follows:

1. top[ ]: This is a k-dimensional array that maintains the indices of the top components in all stacks.
2. next[ ]: This has a capacity of n and keeps the next item indexes for the elements in the array arr[].

The actual array arr[] is used to hold k stacks. A stack of free spaces in arr[] is kept in addition to the k stacks. The top of the stack is saved in the 'free' variable. To signal that all stacks are empty, all entries in the top[] are set to -1. Because all slots are initially vacant and referring to the following slot, all entries next[i] are initialized as i+1. The top of the free stack, 'free,' is set to 0.

The execution of the above idea is shown below.

Code:

//C++ program for creating k stacks in a single array

#include<bits/stdc++.h>
using namespace std;
class kStacks
{
	int *arr; 
	int *top; of size k to store indexes of top items of stacks
	int *next; 
	int n, k;
	int free; 
	public:

	//constructor for creating k stacks in a single array

	kStacks(int k,int n);

	bool isFull() 
	{ return (free == -1); }

	// To push an element in stack number 'sn' where sn is from 0 to k-1

	void push(int item,int sn);

	// To pop an element from stack number 'sn'

	int pop(int sn);

	// To check if stack number 'sn' is empty

	bool isEmpty(int sn) 
	{ return (top[sn] == -1); }

};


//constructor for creating k stacks in a single array of dimension n
kStacks::kStacks(int k1, int n1)
{
	// Initialize n and k
	
	k = k1, n = n1;
	arr = new int[n];
	top = new int[k];
	next = new int[n];

	// Initialize all stacks to empty
	
	for (int i = 0; i < k; i++)
	top[i] = -1;

	// Initialize all spaces to free
	
	free = 0;
	for (int i=0; i<n-1; i++)
	next[i] = i+1;
	next[n-1] = -1; // -1 is used to tell end of free list
}


// Pushing an item in stack number 'sn' where sn is from 0 to k-1
void kStacks::push(int item, int sn)
{
	if (isFull())
	{
		cout << "\nStack Overflow\n";
		return;
	}
	int i = free;
	free = next[i];
	next[i] = top[sn];
	top[sn] = i;
	
	// Put the item in array
	
	arr[i] = item;
}

// To pop an element from stack number 'sn' where sn is from 0 to k-1

int kStacks::pop(int sn)
{
	// Underflow check for mergin k stacks in a single array
	if (isEmpty(sn))
	{
	cout << "\nStack Underflow\n";
	return INT_MAX;
	}

	// Find index of top element in stack number 'sn'

	int i = top[sn];
	top[sn] = next[i]; 
	next[i] = free;
	free = i;

	// Returning the previous top element

	return arr[i];
}

//Main function for creating k stacks in a single array

int main()
{
	// Let us create three stacks in an array of size 10
	
	int k = 3, n = 10;
	kStacks ks(k, n);

	// Putting some items in stack 2

	ks.push(17, 2);
	ks.push(14, 2);

	// Putting some items in stack 1

	ks.push(0, 1);
	ks.push(100, 1);
	ks.push(48, 1);

	// Putting some items in stack 0

	ks.push(13, 0);
	ks.push(7, 0);
	ks.push(5, 0);

	cout << "Popped item from stack 0 is " << ks.pop(0) << endl;
	cout << "Popped item from stack 1 is " << ks.pop(1) << endl;
	cout << "Popped item from stack 2 is " << ks.pop(2) << endl;

	return 0;
}

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

Run Code

Output:

The time complexity of push() and pop() operation is O(1). The most excellent feature of the above implementation is that if a slot is open in a stack, an item can be put into any of the stacks, resulting in no wasted space.

Time Complexity: O(N) because we traverse N times with a loop.

Auxiliary Space: O(N), because we're consuming extra space for the stack.

Must Read Stack Operations

Frequently Asked Questions

Define stack.

A stack is a container for added and deleted things using the last-in-first-out (LIFO) principle. Only two operations are permitted in pushdown stacks: pushing an item into the stack and popping an item out of the stack.

Stacks may be used to conduct three different tasks. They are putting something in a stack (push), removing something from the stack (pop), and displaying the stack's contents (peek or top).

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.

When and why should we utilise stack or queue data structures over Arrays/Lists?

Because they help you handle your data in a more specific manner than arrays and lists, you won't have to wonder whether someone arbitrarily placed an entry into the midst of your list, messing up certain invariants when troubleshooting an issue.

Random access is supported via arrays and lists. They are incredibly malleable and highly corruptible. Utilising those previously developed collections is recommended if you wish to handle your data like FIFO or LIFO.

Which data structures are utilised for a graph's BFS and DFS?

The queue data structure is used for BFS, and the stack is used for DFS.

Conclusion

In this article, we have extensively discussed the logic of how to implement k stacks in a single array and the code of it in c++.

After reading about how to implement k stacks in a single array, 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), Implementation of Stack, Problems of top tech companies for practice, Coding Interview Questions and Data Structures & Algorithms.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

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

Happy Learning!