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) {
		return tops[stackNum] == SIZE * stackNum;
	}

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

Comments after running:

  • 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;
		}
	}

Comments:

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

5 Comments (+add yours?)

  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 .

    Reply

    • Runhe Tian
      May 30, 2012 @ 09:05:18

      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.

      Reply

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

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

    Reply

  3. Harsh Doshi
    Aug 20, 2013 @ 16:47:49

    Your solution doesn’t work.

    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)

    Reply

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

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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: