Use an array to implement three Stack

Question

I saw the following Java code used to implement three stack on a single array.

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 question1 is that Line 4 has allocated memory for the variable buffer. Why in Line 9, we still need to allocate new StackNode.

My question2 is: Can the function pop help recollect the used memory?

For example,

Stack1_E1 => Stack1_E2 => Stack2_E1 => Stack2_E2 => Stack3_E1

When we call pop(0) // pop the Stack1 Based on my understanding, the free space used by Stack1_E2 will not be reused next time when we call push.

Is the function pop designed correctly? Thank you

Note: This question has been modified and includes the pop function.

Please DO NOT remove the line number from my question. == Thank you — q0987
– q0987, Commented Nov 21, 2010 at 18:11

Jonik · Accepted Answer · 2010-11-22 08:20:04Z

4

Question 1: Line 4 has allocated memory for the variable buffer. Why in Line 9, we still need to allocate new StackNode.

Line 4 creates an array of references to StackNode objects. The actual StackNode objects are then created in line 9.

Question 2: Can the function pop help recollect the used memory?

The pop function gets the next value object (StackNode.value) from the stack, and sets the corresponding StackNode reference in the array to null. The memory that was used by this StackNode will be garbage collected, since the StackNode is not referenced anymore. The memory used by the value object itself will be garbage collected when the object is no longer in use (i.e. not referenced anymore by the caller or other objects)

edited Nov 22, 2010 at 8:20

Jonik

82.1k77 gold badges272 silver badges386 bronze badges

answered Nov 22, 2010 at 7:05

Grodriguez

22.1k11 gold badges72 silver badges118 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

fmt · Accepted Answer · 2010-11-21 17:55:23Z

0

You seem to be familiar with C++. In Java, declaring a variable initializes space for it; the "new" construct is only necessary to call the constructor. (This is why there is no "delete".)

So the Line 4 call creates an array of StackNode object-shaped-spaces, while line 9 creates the actual objects.

answered Nov 21, 2010 at 17:55

fmt

9939 silver badges18 bronze badges

4 Comments

Grodriguez Over a year ago

Declaring a variable initializes space for a reference to the object, not for the object itself. The new actually creates the object. There is no delete because Java uses garbage collection: Objects are released when they are no longer in use (== not referenced anymore). Line 4 creates an array of references to StackNodes. The actual StackNodes are created in line 9.

Jonik Over a year ago

@Grodriguez, I was sort of waiting for someone to come and explain that. Consider posting an answer of your own (since both of current answers have faults) — you'll be sure have my vote!

fmt Over a year ago

@Grodriguez: Well, learn something every day. Thank you. (I just got fried on that exact point on my java test today, it would seem.)

Grodriguez Over a year ago

@Jonik: I have done so, especially since one of the two answers is now gone.

Rocky · Accepted Answer · 2014-01-02 23:30:49Z

//Array to implement 3 Stacks

#include<stdio.h>
#include<stdlib.h>
#define size 13

struct Stack{
    int arr[size];
    int top;
}st[3];


void push(int item, int sno){
    if(isFull(sno)){
        printf("Overflow....!!\n");

    }
    else{
       st[sno].top++;

        st[sno].arr[st[sno].top]=item;
      }
}

int isFull(int sno){
    if(sno==1&&st[sno].top==(size/3)-1){
        return 1;
    }
    else if(sno==2&& st[sno].top==(size/3)-1){
        return 1;
    }
    else if(sno==3 && st[sno].top==(size-1 -2*(size/3))){
        return 1;
    }
    else{
        return 0;
    }
}

int isEmpty(int sno){
    if(st[sno].top==-1){
        return 1;
    }
    else{
        return 0;
    }
}


int pop(int sno){
int item;
  if(isEmpty(sno)){
    printf("Underflow....!!\n");
  }
  else{

    item = st[sno].arr[st[sno].top];
    st[sno].top--;
    return item;
}
}

void display(int sno){
    int i;

    for(i=st[sno].top;i>=0;i--){
        printf("%d->",st[sno].arr[i]);
    }
}

int main(){

    st[1].top=-1;
    st[2].top=-1;
    st[3].top=-1;

    push(10,1);
    push(20,1);
    push(30,1);
    push(40,1);

    display(1);

    printf("\n");
    push(50,2);
    display(2);
    printf("\n");
    pop(2);
    pop(2);
    //display(2);

    push(60,3);
    push(70,3);
    push(80,3);
    push(90,3);
    push(100,3);
    printf("\n");
    display(3);
    push(110,3);





    return 0;
}

Collectives™ on Stack Overflow

Use an array to implement three Stack

3 Answers 3

Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related