Problem

Implement 3 stacks in 1 array

Solution

Method 1 - Create 3 Stacks with Fixed Max Size

Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: [ means inclusive, while ( means exclusive of the end point).

  • for stack 1, we will use [0, n/3)
  • for stack 2, we will use [n/3, 2n/3)
  • for stack 3, we will use [2n/3, n)

Code

Java
int stackSize = 300;
int[] buffer = new int[stackSize * 3];
int[] stackPointer = {0,0,0}; // stack pointers to track top element

void push(int stackNum, int value) {
    /* Find the index of the top element in the array + 1, and
    increment the stack pointer */
    int index = stackNum * stackSize + stackPointer[stackNum] + 1;
    stackPointer[stackNum]++;
    buffer[index] = value;
}

int pop(int stackNum) {
    int index = stackNum * stackSize + stackPointer[stackNum];
    stackPointer[stackNum]--;
    int value = buffer[index];
    buffer[index] = 0;
    return value;
}

int peek(int stackNum) {
    int index = stackNum * stackSize + stackPointer[stackNum];
    return buffer[index];
}

boolean isEmpty(int stackNum) {
    return stackPointer[stackNum] == stackNum * stackSize;
}

Method 2 - Getting Space Efficient Solution

Here is the procedure to do so:

  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.

So this is what happens: 

  • First stack grows from left to right.
  • Second stack grows from right to left.
  • Third stack starts from the middle. Suppose odd sized array for simplicity. Then third stack grows like this:       5 3 1 2 4

First and second stacks are allowed to grow maximum at the half size of array. The third stack can grow to fill in the whole array at a maximum. Worst case scenario is when one of the first two arrays(arrays at both ends) grows at 50% of the array. Then there is a 50% waste of the array. To optimize the efficiency the third array (i.e. the array in the middle) must be selected to be the one that grows quicker than the other two.

Code

Java
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();
       }
   }
}