## Implement 3 stacks using a single array

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

My initial thoughts:
If size of the array is n, we can allocate [0,n/3) to the first stack, [n/3,2n/3) to the second stack and [2n/3,n) to the third stack. We also need to maintain an array of pointers to the positions of the top for each stack.

My initial codes:

```public class Q3_1 {

private final int SIZE = 10;
private Integer[] data = new Integer[SIZE * 3];
private int[] tops = { 0, 0, 0 };

public void push(int stackNum, Integer item) {
data[tops[stackNum] + SIZE * stackNum] = item;
tops[stackNum]++;
}

public Integer pop(int stackNum) {
if (tops[stackNum] == SIZE * stackNum)
return null;
tops[stackNum]--;
Integer element = data[tops[stackNum] + SIZE * stackNum];
data[tops[stackNum] + SIZE * stackNum] = null;
return element;
}

public boolean isEmpty(int stackNum) {
}

@Override
public String toString() {
String result = new String();
for (int i = 0; i < data.length; ++i)
result += data[i] + " ";
return result;
}
}

It works well but if we can also dynamically increase the size, that would be more practically realistic.

Solution:
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;
}
}

The solution utilize a linked-list approach which allow each element in the stack to remember its previous node.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b27ff30c9511', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b27ff30c953c',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b27ff30c953e',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. kapilgupta
May 28, 2012 @ 06:28:09

In second approach …. after push.. if we perform pop then… how is it managing the free space for further push operation .

• The elements are inserted into the array ‘buffer’ sequentially, in other word, it’s mixed up with elements for all of the three stacks and there is no free space in the ‘buffer’. But ‘stackPointer’ always point to the index of last element for each stack and each node in the stack has pointer to previous stack.

2. Mr Rabbit
Sep 17, 2012 @ 14:21:48

I believe you’ll leave “holes” in the array after you pop the items.

The problem is with the indexUsed

So, now take an example

push(0,1) —> indexUsed:0 buffer[0].data=1 stackPointer[0]=0
push(1,10) —> indexUsed:1 buffer[1].data=10 stackPointer[1]=1
push(2,12) —> indexUsed:2 buffer[2].data=12 stackPointer[2]=2
push(0,3) —> indexUsed:3 buffer[3].data=3 stackPointer[0]=3
push(2,13) —> indexUsed:4 buffer[4].data=13 stackPointer[2]=4
pop(0) —> indexUsed:3 buffer[3]=null stackPointer[0]= 0
push(0,5) —> indexUsed:3 buffer[3].data=5 stackPointer[0]=3

// The problem lies here

push(0,6) —> indexUsed:4 buffer[4].data=6 stackPointer[0]=4

This will now replace the item placed by stack number 2 at the position 4, which is not expected.

This will break. Your initial thoughts which are a copy from the book Cracking the Coding Interview are right. Even if the code is a copy, it is helpful to find everything on this site. Nice work (y)

4. Mingtao Sun
Jan 16, 2014 @ 23:16:14

Harsh is right. The code on the book doesn’t work.