Implementing 3 stacks using 1 array, will this code work?

Question

This is what I found in the question book with the algorithm / interview, someone had a few posts on this, but I still have some questions, here is the original text and code in the book:

implement 3 stacks using 1 array: Approach 2: 

In this approach, any stack can grow as long as there is free space in the array. We sequentially allocate space to the stacks and associate the new blocks with the previous block. This means that any new item on the stack holds a pointer to the previous top item of this particular stack. In this implementation, we are faced with the problem of unused space. For example, if a stack deletes some of its elements, deleted elements may not necessarily appear at the end of the array. Thus, in this case, we will not be able to use these newly freed spaces. To overcome this drawback, we can save a free list, and the entire array space will be initially provided to a free list. For each insert, we will remove the entry from the free list. In the case of deletion, we simply add the free cell index to the free list. In this implementation, we could have the flexibility to use variable spaces, but we would need to increase the complexity of the space.

 1 int stackSize = 300; 2 int indexUsed = 0; 3 int[] stackPointer = {-1,-1,-1}; 4 StackNode[] buffer = new StackNode[stackSize * 3]; 5 void push(int stackNum, int value) { 6 int lastIndex = stackPointer[stackNum]; 7 stackPointer[stackNum] = indexUsed; 8 indexUsed++; 9 buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value); 10 } 11 int pop(int stackNum) { 12 int value = buffer[stackPointer[stackNum]].value; 13 int lastIndex = stackPointer[stackNum]; 14 stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous; 15 buffer[lastIndex] = null; 16 indexUsed--; 17 return value; 18 } 19 int peek(int stack) { return buffer[stackPointer[stack]].value; } 20 boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; } 21 22 class StackNode { 23 public int previous; 24 public int value; 25 public StackNode(int p, int v){ 26 value = v; 27 previous = p; 28 } 29 } 

my question is: in mothod pop () after setting the buffer [lastIndex] to null (line 15) and indexUsed - (line 16), will indexUsed be the head of the white space? call the Stack Top nodes of the first stack: S1, second stack: S2, third stack: S3; what happens if: I have s1 followed by s2 and s3 that were pressed before I wanted to stroke s1,

 index: 10 11 12 13 ------------------------------- | ... | s1 | s2 | s3 | null | ------------------------------- 

indexUsed is now 13. Now, if I want to pop () on the first stack, it will become:

 index: 10 11 12 13 ---------------------------------- | ... | null | s2 | s3 | null | ---------------------------------- 

and indexUsed is now 13, that is 12, so what happens if I want to push a new Node to this array, according to the push () method, in line 7 indexUsed is assigned stackPointer and is used as the index of clicking on the array, will it overwrite s3 ( top stack Node3) in the 12th record?

 added: 

and how do I change it to make it work? at first glance, I would think of introducing a logical [] to track the usage of each record in the storage array, but it will be time and space.

Thanks!

Answer 1

As far as I can tell, you're right - it does not store enough information to indicate holes in memory.

One of the big advantages to the stack is that it can be allocated on top of the list of arrays instead of a linked list that preserves the memory of previous / next pointers. This implementation eliminates this advantage - it's hard. Imagine an application in which it is a really good solution.

Answer 2

"To overcome this shortcoming, we can save a free list, and the entire array space will be initially provided to the free list."

Basically, you can save the “fourth” stack containing all the empty places in the array. The array will be initialized when this 4th stack is full. Each time you push 1/2/3 onto the stack, you will exit from the fourth. Each time you pop out with 1/2/3, you will push it back into the fourth. This way you always know where the free slot is.