Describe how you could use a single array to implement three stacks

Question

I'm preparing for an interview so I'm trying to solve some problems to stretch my mind. Here is one:

Describe how you could use a single array to implement three stacks.

And here is my implementation:

class StackUnderflowError extends RuntimeException {
    public StackUnderflowError(String msg) {
        super(msg);
    }
} 


class ThreeStacks<T>{

private T[] array;
private int firstIndex = 0;
private int secondIndex = 1;
private int thirdIndex = 2;

public ThreeStacks(Class<T> classT, int capacity) {
    array = (T[])Array.newInstance(classT, capacity);
}

void push(T data, int stack){ //enum to select the stack
    switch(stack)
    {
        case 1: pushOne(data);
            break;
        case 2: pushTwo(data);
            break;
        case 3: pushThree(data);
            break;
        default: throw new IllegalArgumentException("stack");
    }
}

T pop(int stack){
    switch(stack){
        case 1: return popOne();
        case 2: return popTwo();
        case 3: return popThree();
        default: throw new IllegalArgumentException("stack");
    }
}

private void pushOne(T data) {
    if (firstIndex > array.length - 1) {
        throw new StackOverflowError("firstStack");
    } else{
        array[firstIndex] = data;
        firstIndex += 3;
    }
}

private void pushTwo(T data) {
    if (secondIndex > array.length - 1) {
        throw new StackOverflowError("secondStack");
    } else{
        array[secondIndex] = data;
        secondIndex += 3;
    }
}

private void pushThree(T data) {
    if (thirdIndex > array.length - 1) {
        throw new StackOverflowError("thirdStack");
    } else{
        array[thirdIndex] = data;
        thirdIndex += 3;
    }
}

private T popOne() {
    firstIndex -= 3;
    if(firstIndex < 0){
        throw new StackUnderflowError("fristStack");
    }
    return array[firstIndex];
}

private T popTwo() {
    secondIndex -= 3;
    if(secondIndex < 0){
        throw new StackUnderflowError("fristStack");
    }
    return array[secondIndex];
}

private T popThree() {
    thirdIndex -= 3;
    if(thirdIndex < 0){
        throw new StackUnderflowError("fristStack");
    }
    return array[thirdIndex];
}

}

And test:

    ThreeStacks<String> threeStacks = new ThreeStacks<>(String.class, 1024);
    threeStacks.push("1", 1);
    threeStacks.push("2", 2);
    threeStacks.push("3", 3);
    threeStacks.push("4", 1);
    threeStacks.push("5", 2);
    threeStacks.push("6", 3);

    System.out.println( threeStacks.pop(1) );
    System.out.println( threeStacks.pop(2) );
    System.out.println( threeStacks.pop(2) );
    System.out.println( threeStacks.pop(1) );
    //System.out.println( threeStacks.pop(1) );

How can I improve this? A few thoughts:

• use array instead of switch (stacks' indexes)
• use enum to choose stack
• use ArrayList (if interviewer agrees)

Answer 1

Solution that I found

In this approach, any stack can grow as long as there is any free space in the array. We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.

In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array. So, in that case, we would not be able to use those newly freed spaces. To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.

In this implementation we would be able to have flexibility in terms of variable space utilization but we would need to increase the space complexity.

 int stackSize = 300;
 int indexUsed = 0;
 int[] stackPointer = {-1,-1,-1};
 StackNode[] buffer = new StackNode[stackSize * 3];
 void push(int stackNum, int value) {
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = indexUsed;
    indexUsed++;
    buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value);
 }

int pop(int stackNum) {
    int value = buffer[stackPointer[stackNum]].value;
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
    buffer[lastIndex] = null;
    indexUsed--;
    return value;
 }
 int peek(int stack) { return buffer[stackPointer[stack]].value; }
 boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }

class StackNode {
 public int previous;
 public int value;
 public StackNode(int p, int v){
    value = v;
    previous = p;
 }
}

Answer 2

How can I improve this?

This question is a rather interesting one. By upping the count of stacks to three, we can no longer be assured of an optimal utilization of the array (for two, each stack could start from one of the ends).

So the problem here is that of optimal utilization of the array, Your solution divides the array equally into three, so that even if there is space left in one of the stacks, your other stacks are unable to use it.

Perhaps it would be profitable to consider the more general case of storing n stacks in the array.

If you think about it, the problem is remarkably similar to memory allocation or file space allocation in a hard disk. This would be my approach. I assume that the array is an array of integers.

• Use reverse end of the array as a normal stack - call it S.

• When adding a new (tag,number) (i,x) to the stacks, check if the previous number was added to the same stack i.

  • If it was, just push it to S
  • If not, count the entries of the stack S,
    • Write the current stack S to the free cells from the beginning.
    • Write the tag (say j) of the stack currently stored in S to the first free cell from the beginning say A[c].
    • Write count to the next free cell A[c+1].
    • Reset S, save i as the current tag, add x to beginning of S
    • A block should look like x,x,x,x,x,[0,1,2,3,..,tag,count],_,_
  • Repeat.

Reading an entry (i,y?) of stack i is simple,

• First check to see if the stack S is the one we need, if so, return the last element from the other end of S
• If not,
  • Go to the last element of A, and read the length and tag.
  • If the tag is not the one we are looking for,
    • skip length entries and read the next tag and length
    • repeat until the tag we want is found.
• If it is, then return immediately previous non-null entry in the block.

This has the problem that the blocks may become fragmented. This can be alleviated by having a compaction triggered once in a while (so that its cost is amortized) to compact the blocks.

---

One improvement is to not use the reverse end as the stack of current tag, but just use the current free cell from the beginning itself. It has the advantage of avoiding copying when the tag is switched.

Answer 3

The implementation you have basically splits your array into 3 equal sub-arrays, and each stack can only use the elements of its subarray. It would be roughly the same as setting the first index to 0, the second index to array.length/3, and the third to array.length*2/3. Instead, you're working based on modular congrence; the first stack uses indices where that have a modulo by 3 of 0, the second stack 1 and the third stack 2.

"Improving" it depends on what you want to improve; space efficiency or performance? You could create a stack for which any number of unused indices could store values of any one stack, by implementing two "slide" helper methods:

private void SlideRight(int index, int stackNum)
{
    //keep a count of all elements in the array and make sure this operation
    //will not push an element "off the edge"
    if(totalCount + offset > array.length) throw new StackOverflowException();

    for(int i=totalCount-1; i>index; i--)
       array[i] = array[i-1];

    for(int j=stackNum; j<stacks.length; j++)
       stacks[j]++;
}

private void SlideLeft(int index, int stackNum)
{
    for(int i=index; i<totalCount-1; i++)
       array[i] = array[i+1];

    for(int j=stackNum; j<stacks.length; j++)
       stacks[j]++;
}

These can be used to push and pop values into any stack, up to the full capacity of the array:

public int[] stacks = new int[3]{0,0,0};

public void Push(int value, int stackNum)
{
   SlideRight(stacks[stackNum-1], stackNum);
   array[stacks[stackNum-1]] = value;
   stacks[stackNum-1]++;
   totalCount++;
}

public void Pop(int stackNum)
{
   int result = array[stacks[stackNum-1]]
   SlideLeft(stacks[stackNum-1], stackNum);
   stacks[stackNum-1]--;
   totalCount--;
   return result;
}

The downside is having to perform count-N swaps to insert a value into index N (which basically means that pushing or popping from stack X is bound in time to the number of elements in stacks higher than X).

Another option is to use the array to implement a simple "hashset"-like structure (with 3 "hashes"; one per stack). The general is to create a Node struct, which your primary array will hold copies of. Each Node holds the actual value pushed, and the index of the next lower Node in that stack. To push, create a Node, assign the value and the index of the current "top" node of that Stack, then put that Node in the first available spot in the array (which you must keep track of because elements can be added/removed from pretty much anywhere) and remember its location as the new "top". To pop, do the opposite; go to the remembered "top" index, get that Node, then clear that index (checking to see if it's a lower index than the currently-known "first available"), and set the "top" node to the popped node's "next" index. The advantage is O(1) access in most cases (pushing a node, which requires determining the next null index of the array for the next push, is worst-case linear); the disadvantage is extra space necessary to maintain the links between nodes of a stack.