How to implement 3 stacks with one array?

Question

Sometimes, I come across the following interview question: How to implement 3 stacks with one array ? Of course, any static allocation is not a solution.

Answer 1

Here's my solution for it in C# -

/*  Program: Implement 3 stacks using a single array
 *
 *  Date: 12/26/2015
 */

using System;

namespace CrackingTheCodingInterview
{
    internal class Item
    {
        public object data;
        public int prev;
    }

    /// <summary>
    /// Class implementing 3 stacks using single array
    /// </summary>
    public class Stacks
    {
        /// <summary>
        /// Pushing an element 'data' onto a stack 'i'
        /// </summary>
        public void Push(int i, object d)
        {
            i--;
            if (available != null)
            {
                int ava = (int)available.DeleteHead();
                elems[ava].data = d;
                elems[ava].prev = top[i];
                top[i] = ava;
            }
            else
            {
                Console.WriteLine("Array full. No more space to enter!");
                return;
            }
        }

        /// <summary>
        /// Popping an element from stack 'i'
        /// </summary>
        public object Pop(int i)
        {
            i--;
            if (top[i] != -1)
            {
                object popVal = elems[top[i]].data;
                int prevTop = elems[top[i]].prev;
                elems[top[i]].data = null;
                elems[top[i]].prev = -1;
                available.Insert(top[i]);
                top[i] = prevTop;

                return popVal;
            }
            else
            {
                Console.WriteLine("Stack: {0} empty!", i);
                return null;
            }
        }

        /// <summary>
        /// Peeking top element of a stack
        /// </summary>
        public object Peek(int i)
        {
            i--;
            if (top[i] != -1)
            {
                return elems[top[i]].data;
            }
            else
            {
                Console.WriteLine("Stack: {0} empty!", i);
                return null;
            }
        }

        /// <summary>
        /// Constructor initializing array of Nodes of size 'n' and the ability to store 'k' stacks
        /// </summary>
        public Stacks(int n, int k)
        {
            elems = new Item[n];
            top = new int[k];

            for (int i = 0; i < k; i++)
            {
                top[i] = -1;
            }

            for (int i = 0; i < n; i++)
            {
                elems[i] = new Item();
                elems[i].data = null;
                elems[i].prev = -1;
            }

            available = new SinglyLinkedList();

            for (int i = n - 1; i >= 0; i--)
            {
                available.Insert(i);
            }
        }

        private Item[] elems;
        private int[] top;
        private SinglyLinkedList available;
    }

    internal class StacksArrayTest
    {
        static void Main()
        {
            Stacks s = new Stacks(10, 3);
            s.Push(1, 'a');
            s.Push(1, 'b');
            s.Push(1, 'c');

            Console.WriteLine("After pushing in stack 1");
            Console.WriteLine("Top 1: {0}", s.Peek(1));

            s.Push(2, 'd');
            s.Push(2, 'e');
            s.Push(2, 'f');
            s.Push(2, 'g');

            Console.WriteLine("After pushing in stack 2");
            Console.WriteLine("Top 1: {0}", s.Peek(1));
            Console.WriteLine("Top 2: {0}", s.Peek(2));

            s.Pop(1);
            s.Pop(2);

            Console.WriteLine("After popping from stack 1 and 2");
            Console.WriteLine("Top 1: {0}", s.Peek(1));
            Console.WriteLine("Top 2: {0}", s.Peek(2));

            s.Push(3, 'h');
            s.Push(3, 'i');
            s.Push(3, 'j');
            s.Push(3, 'k');
            s.Push(3, 'l');

            Console.WriteLine("After pushing in stack 3");
            Console.WriteLine("Top 3: {0}", s.Peek(3));

            Console.ReadLine();
        }
    }
}

Output:

After pushing in stack 1
Top 1: c
After pushing in stack 2
Top 1: c
Top 2: g
After popping from stack 1 and 2
Top 1: b
Top 2: f
After pushing in stack 3
Top 3: l

I refer to this post for coding it - http://codercareer.blogspot.com/2013/02/no-39-stacks-sharing-array.html

Answer 2

package job.interview; import java.util.Arrays;

public class NStack1ArrayGen<T> {

    T storage[];
    int numOfStacks;
    Integer top[];
    public NStack1ArrayGen(int numOfStks, T myStorage[]){
        storage = myStorage;
        numOfStacks = numOfStks;
        top = new Integer[numOfStks];
        for(int i=0;i<numOfStks;i++){top[i]=-1;}
    }
    public void push(int stk_indx, T value){
        int r_indx = stk_indx -1;
        if(top[r_indx]+numOfStacks < storage.length){
            top[r_indx] = top[r_indx] < 0 ? stk_indx-1 : top[r_indx]+numOfStacks;
            storage[top[r_indx]] = value;
        }
    }
    public T pop(int stk_indx){
        T ret = top[stk_indx-1]<0 ? null : storage[top[stk_indx-1]];
        top[stk_indx-1] -= numOfStacks;
        return ret;
    }
    public void printInfo(){
        print("The array", Arrays.toString(storage));
        print("The top indices", Arrays.toString(top));
        for(int j=1;j<=numOfStacks;j++){
            printStack(j);
        }
    }
    public void print(String name, String value){
        System.out.println(name + " ==> " + value);
    }
    public void printStack(int indx){
        String str = "";
        while(top[indx-1]>=0){
            str+=(str.length()>0 ? "," : "") + pop(indx);
        }
        print("Stack#"+indx,str);
    }
    public static void main (String args[])throws Exception{
        int count=4, tsize=40;
        int size[]={105,108,310,105};
        NStack1ArrayGen<String> mystack = new NStack1ArrayGen<String>(count,new String[tsize]); 
        for(int i=1;i<=count;i++){
            for(int j=1;j<=size[i-1];j++){
                mystack.push(i, "stk"+i+"_value"+j);
            }
        }
    }
}

This prints:

The array ==> [stk1_value1, stk2_value1, stk3_value1, stk4_value1, stk1_value2, stk2_value2, stk3_value2, stk4_value2, stk1_value3, stk2_value3, stk3_value3, stk4_value3, stk1_value4, stk2_value4, stk3_value4, stk4_value4, stk1_value5, stk2_value5, stk3_value5, stk4_value5, stk1_value6, stk2_value6, stk3_value6, stk4_value6, stk1_value7, stk2_value7, stk3_value7, stk4_value7, stk1_value8, stk2_value8, stk3_value8, stk4_value8, stk1_value9, stk2_value9, stk3_value9, stk4_value9, stk1_value10, stk2_value10, stk3_value10, stk4_value10] The top indices ==> [36, 37, 38, 39] Stack#1 ==> stk1_value10,stk1_value9,stk1_value8,stk1_value7,stk1_value6,stk1_value5,stk1_value4,stk1_value3,stk1_value2,stk1_value1 Stack#2 ==> stk2_value10,stk2_value9,stk2_value8,stk2_value7,stk2_value6,stk2_value5,stk2_value4,stk2_value3,stk2_value2,stk2_value1 Stack#3 ==> stk3_value10,stk3_value9,stk3_value8,stk3_value7,stk3_value6,stk3_value5,stk3_value4,stk3_value3,stk3_value2,stk3_value1 Stack#4 ==> stk4_value10,stk4_value9,stk4_value8,stk4_value7,stk4_value6,stk4_value5,stk4_value4,stk4_value3,stk4_value2,stk4_value1

Answer 3

I have a solution for this question. The following program makes the best use of the array (in my case, an array of StackNode Objects). Let me know if you guys have any questions about this. [It's pretty late out here, so i didn't bother to document the code - I know, I should :) ]

public class StackNode {
    int value;
    int prev;

    StackNode(int value, int prev) {
        this.value = value;
        this.prev = prev;
    }
}


public class StackMFromArray {
    private StackNode[] stackNodes = null;
    private static int CAPACITY = 10;
    private int freeListTop = 0;
    private int size = 0;
    private int[] stackPointers = { -1, -1, -1 };

    StackMFromArray() {
        stackNodes = new StackNode[CAPACITY];
        initFreeList();
    }

    private void initFreeList() {
        for (int i = 0; i < CAPACITY; i++) {
            stackNodes[i] = new StackNode(0, i + 1);
        }
    }

    public void push(int stackNum, int value) throws Exception {
        int freeIndex;
        int currentStackTop = stackPointers[stackNum - 1];
        freeIndex = getFreeNodeIndex();
        StackNode n = stackNodes[freeIndex];
        n.prev = currentStackTop;
        n.value = value;
        stackPointers[stackNum - 1] = freeIndex;
    }

    public StackNode pop(int stackNum) throws Exception {
        int currentStackTop = stackPointers[stackNum - 1];
        if (currentStackTop == -1) {
            throw new Exception("UNDERFLOW");
        }

        StackNode temp = stackNodes[currentStackTop];
        stackPointers[stackNum - 1] = temp.prev;
        freeStackNode(currentStackTop);
        return temp;
    }

    private int getFreeNodeIndex() throws Exception {
        int temp = freeListTop;

        if (size >= CAPACITY)
            throw new Exception("OVERFLOW");

        freeListTop = stackNodes[temp].prev;
        size++;
        return temp;
    }

    private void freeStackNode(int index) {
        stackNodes[index].prev = freeListTop;
        freeListTop = index;
        size--;
    }

    public static void main(String args[]) {
                    // Test Driver
        StackMFromArray mulStack = new StackMFromArray();
        try {
            mulStack.push(1, 11);
            mulStack.push(1, 12);
            mulStack.push(2, 21);
            mulStack.push(3, 31);
            mulStack.push(3, 32);
            mulStack.push(2, 22);
            mulStack.push(1, 13);
            StackNode node = mulStack.pop(1);
            node = mulStack.pop(1);
            System.out.println(node.value);
            mulStack.push(1, 13);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Answer 4

Space (not time) efficient. You could:

1) Define two stacks beginning at the array endpoints and growing in opposite directions.

2) Define the third stack as starting in the middle and growing in any direction you want.

3) Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.

You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.

Edit

Above you may see an example. The shifting is done with an equal space partitioning policy, although other strategies could be chosen depending upon your problem heuristics.

Edit

Following @ruslik's suggestion, the middle stack could be implemented using an alternating sequence for subsequent pushes. The resulting stack structure will be something like:

| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |

In this case, you'll need to store the number n of elements on the middle stack and use the function:

f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3  

to know the next array element to use for this stack.

Although probably this will lead to less shifting, the implementation is not homogeneous for the three stacks, and inhomogeneity (you know) leads to special cases, more bugs and difficulties to maintain code.

Answer 5

Store the stack in the area in such way when first stack goes into index 0, then 0+3=3, then 3+3=6...; the second one goes into indexes 1, 1+3=4, 4+3=7...; the the third one goes into indexes 2, 2+3=5, 5+3=8 So if we mark the first stack elements with a, as one with b and there with c we get: a1 b1 c1 a2 b2 c2 a3 b3 c3...

There could be gaps but we always know the top indexes which are stored in 3-element topIndex array.

Answer 6

I think you should divide array in 3 pieces, making head of first stack at 0, head of second stack at n/3, head of 3rd stack at n-1.

so implement push operation on :

1. first & second stack make i++ and for 3rd stack make i--;
2. If you encounter that first stack have no space to push, shift 2nd stack k/3 positions forward. Where k is the number of positions left to be filled in array.
3. If you encounter that second stack have no space to push, shift 2nd stack 2*k/3 positions backward. Where k is the number of positions left to be filled in array.
4. If you encounter that third stack have no space to push, shift 2nd stack 2*k/3 positions backward. Where k is the number of positions left to be filled in array.

We are shifting k/3 and 2*k/3 when no space is left so that after shifting of middle stack, each stack have equal space available for use.