> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/how-to-efficiently-implement-k-stacks-in-a-single-array.md).

# 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];
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/how-to-efficiently-implement-k-stacks-in-a-single-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.