Using an array to implement three stacks, can this code work?

This is what I found in the algorithm / interview question book. Others have several posts on this question, but I still have some questions. Here are the original text and the code in the book:

implement 3 stacks using 1 array:
Approach 2:

In this method, any stack can grow as long as there is any free space in the array We allocate space for the stack in order and link the new block to the previous block This means that any new element in the stack retains a pointer to the previous top element of that particular stack In this implementation, we face the problem of unused space For example, if some elements are deleted from the stack, the deleted elements may not necessarily appear at the end of the array Therefore, in this case, we will not be able to use these newly released spaces To overcome this defect, we can maintain a free list, and the whole array space will be provided to the free list initially For each insertion, we delete an entry from the free list If it is deleted, we only need to add the index of the free cell to the free list In this implementation, we will be able to have flexibility in variable space utilization, but we need to increase space complexity

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(), set the buffer [lastindex] to null (line 15), and then indexused – (line 16). Will indexused be a blank header? Let's call the stack top node of the first stack: S1, the second stack: S2, and the third stack: S3; What happens: before I want to pop up S1, I have S1 followed by S2 and S3

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

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

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

Indexused is now 13 – 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 to stackpointer and used as the push index of data. Will it not overwrite S3 (the top-level node of stack3) in the 12th entry?

added:

And how to change it to make it work? At first glance, I would consider implementing a Boolean [] to track the usage of each item in the storage array, but it will consume time and space

thank you!

Solution

As far as I know, you're right - it doesn't store enough information to indicate a vulnerability in memory

One of the advantages of the stack is that it can be allocated over the array list instead of the linked list to store the memory of the previous / next pointer - this implementation eliminates this advantage - it is difficult to imagine an application, which is actually a good solution