This blog covers a stack problem. 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 involving merging k stacks into a single array.

Problem Statement

In this blog, Ninja has been given a problem in which he has to create a kStacks data structure to represent k stacks. The implementation of kStacks should only utilise one array, i.e., all k-stacks should store their items in the same array. kStacks must support the following functionalities. pop(int sn), pops an element from stack number 'sn' where sn is from 0 to k-1 push(int x, int sn), pushes x to stack number 'sn' where sn is from 0 to k-1.

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:

top[ ]: This is a k-dimensional array that maintains the indices of the top components in all stacks.

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;
}

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.

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