# How to efficiently implement k stacks in a single array?

Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing elements. Following functions must be supported by kStacks.

push(int x, int sn) –> pushes x to stack number ‘sn’ where sn is from 0 to k-1\
pop(int sn) –> pops an element from stack number ‘sn’ where sn is from 0 to k-1

```java
public class GFG {
    // A Java class to represent k stacks in a single array of size n
    static class KStack {
        int arr[]; // Array of size n to store actual content to be stored in stacks
        int top[]; // Array of size k to store indexes of top elements of stacks
        int next[]; // next[i] will store the next free space if you want to occupy this space in
                    // original array otherwise it something already is present at this index, then
                    // it will store the index of element just below this in the stack
        int n, k;
        int free; // To store the first free space index

        // Constructor
        KStack(int k1, int n1) {
            // Initialize n and k, and allocate memory for all arrays
            k = k1;
            n = n1;
            arr = new int[n];
            top = new int[k];
            next = new int[n];
            // Initialize all stacks as empty
            for (int i = 0; i < k; i++)
                top[i] = -1;
            // Initialize all spaces as free
            free = 0;
            for (int i = 0; i < n - 1; i++)
                next[i] = i + 1;
            next[n - 1] = -1; // Last index has no free space after it
        }

        // To push an item in stack number 'sn' where sn is from 0 to k-1
        void push(int item, int sn) {
            // If there is no free space available
            if (free == -1) {
                System.out.println("Stack Overflow");
                return;
            }
            int i = free; // Store index of first free slot
            // Update index of free slot to index of next slot in free list
            free = next[i];
            // Update next of top and then top for stack number 'sn'
            next[i] = top[sn];
            top[sn] = i;
            // Put the item in array
            arr[i] = item;
        }

        // To pop an from stack number 'sn' where sn is from 0 to k-1
        int pop(int sn) {
            // If stack is empty
            if (top[sn] == -1) {
                System.out.println("Stack Underflow");
                return Integer.MAX_VALUE;
            }
            // Find index of top item in stack number 'sn'
            int i = arr[top[sn]];
            top[sn] = next[i]; // Change top to store next of previous top
            // Attach the previous top to the beginning of free list
            next[i] = free;
            free = i;
            // Return the previous top item
            return arr[i];
        }
    }
}
```
