GATE CSE 2004 | Question: 3

Question

A single array $A[1 \ldots \text{MAXSIZE}]$ is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables $top1$ and $top2$ $(top1 < top 2)$ point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for $\text{“}\textsf{stack full}\text{”}$ is

• A. $(top1 = \text{MAXSIZE} / 2)$ and $(top2 = \text{MAXSIZE} / 2 + 1)$

• B. $top1 + top2 = \text{MAXSIZE}$

• C. $(top1 = \text{MAXSIZE} / 2)$ or $(top2 = \text{MAXSIZE})$

• D. $top1 = top2 - 1$

Comments

15

32

31(top1)

44(top2)

76

9

10

3

simply  top1=top2-1; show stack full . Therefore option D correct

---

this question is interesting because we can directly get to the answer as option D but finding the counterexamples to show why option A,C,D are wrong took some time..

As always T1< T2 and both can fill the stacks oppositely until they come close and that's why stack full condition is T1=T2-1

---

https://www.youtube.com/live/QjQ4AtJs3wQ?si=URj1DLGq82bVVrP2&t=420

Answer 1

Answer is (D).

Since the stacks are growing from opposite ends, initially $top1 = 1$ and $top2 = MAXSIZE$. Now, to make the space usage most efficient we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So, either of the stack can grow as long as there is space on the array and hence the condition must be $top1 = top2 - 1$.

Comments

Can you help me to clear below mentioned stack? Am not able to get " how top1 = top2 - 1 " and also what are these values 12,13,14,15,16,17,18,19,21 and 20 ?

---

@Prashant.Pethe top1= 7, top2=8(considering the array index starts from 0)

so top1=top2-1.

It's an array containing the elements 12,13,14,15,16,17,18,19,21 and 20 and top1 and top2 mark the top of the two stacks respectively where the 1st stack grows from left to right and the second one vice versa.

---

if you vividly study the question that condition is top1 < top2 then everything is clear no need to check other options option  D is correct .

Answer 2

Consider array with 10 index:

top1

top2

Now seek Top1+ Top2= maxsize but stack contain 2 elements only. So Option B is fail.

12

13

14

15

16

17

18

19 (top1)

21(top2)

20

here top1= top2-1 shows stack is full only. So Option D is correct.

top1

top2

We see here stack is not full so condition Fail. So Option C is fail.

Option A is says both array have same size but there may be case that stack 2 contain 1 element and stack 2 contain 9 elements , which is not possible with case A.

D is answer

Comments

@gokou  check here

---

@anirudh SIR , 

top1

top2

Here , How  top1 + top2 = MAX SIZE ? top1 and top2 are stack top they are incremented when new elemets are added to stack  

In one element  stack given above top1=top2= 1  , top1 + top2 = 2 only . 

And here ,

12

13

14

15

16

17

18

19 (top1)

21(top2)

20

N= 10 , Top1=8 Top2=2
Top1 <= MAX-Top1 holds good . So option B should be true ? 

Please correct me if wrong  

---

@anirudh SIR , 

Top1 and Top2 is 

top1 and top 2 (top < top 2) point to the location of the topmost element in each of the stacks

But I considered Top1 and Top2 as number of elements in the stacks , is that the reason I arrived at option B ?

---

I think,option A says both the stack have same size.

---

@ Prashant.

Your explanation is very good.

---

You haven't filled the entire array. So how can you say the stack is not full in case 3??

I may sound silly but someone please give a clarity.

---

In third case stack is empty  only from maxsize/2+1 to maxsize-1..so space is not use efficiently.

---

in option a top1 = maxsize /2 and top2 = maxsize/2 +1

if we use 1 in 2 then

top2 = top1 +1

=> top1=top2-1

and in this way the array is utilized efficiently so why is A a wrong answer

Answer 3

Look at how heap and stack sections are incorporated in the Runtime Environment.

That is the most efficient way to utilize the space. If we divide the space by half, what if one entity requires 60% of the space, while the other entity requires none? Halving the available space is an inefficient way to utilize it.

Efficient utilization would be to let a stack take up all the space if the other stack doesn't want it.

 

For the array [1...MaxSize] Let top1 point to 0, and top2 point to MaxSize+1 in the beginning, since both the stacks are empty.

Stack full will be when:-

Option D

Answer 4

The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks

refer:

http://www.geeksforgeeks.org/implement-two-stacks-in-an-array/

Answer 5

The correct answer is D. $top1 = top2 - 1$.

 

Explanation

 

To implement two stacks efficiently in a single array $A[1 \dots \text{MAXSIZE}]$, the standard approach is to have them grow from opposite ends towards the middle. This allows one stack to use any available free space, even if the other stack is empty.

1. Stack 1 Setup:

   • Starts at the beginning of the array (index 1).

   • Grows upwards (incrementing the index).

   • $top1$ points to the current top element of Stack 1.

2. Stack 2 Setup:

   • Starts at the end of the array (index $\text{MAXSIZE}$).

   • Grows downwards (decrementing the index).

   • $top2$ points to the current top element of Stack 2.

3. The "Full" Condition:

   • The array is not full as long as there is at least one empty slot between the top of Stack 1 and the top of Stack 2.

   • The stacks meet when the pointer for Stack 1 ($top1$) is immediately adjacent to the pointer for Stack 2 ($top2$).

   • Visually, the array looks like this when full: [... Stack 1 elements ..., top1, top2, ... Stack 2 elements ...]

   • Mathematically, this means the index of $top2$ is exactly one greater than the index of $top1$.

   $$top2 = top1 + 1$$

   Rearranging this equation gives:

    

   $$top1 = top2 - 1$$

 

Why other options are incorrect:

 

• A. $(top1 = \text{MAXSIZE}/2)$ and $(top2 = \text{MAXSIZE}/2 + 1)$: This describes a specific case where both stacks have an equal number of elements. However, "efficient use of space" means Stack 1 could have 1 element and Stack 2 could have 99 (in a size 100 array). This option is too restrictive.

• B. $top1 + top2 = \text{MAXSIZE}$: This equation does not represent the collision of pointers. For example, in an array of size 10, if Stack 1 has 1 element (at index 1) and Stack 2 has 2 elements (at indices 9, 10, so top2=9), the array isn't full, yet $1 + 9 = 10$.

• C. $(top1 = \text{MAXSIZE}/2)$ or $(top2 = \text{MAXSIZE})$: This again refers to fixed boundaries rather than the dynamic relationship between the two stack pointers.

Answer 6

I think both A and D are correct.actually both defining same thing.

Comments

no Option D is variable in nature but A is fixed to mid point and adjacent to mid.

---

got it. Thank you.

So D is the answer

---

@anirudh SIR , Why not B?

---

Sir, is the midpoint thing not efficient? What is the need for flexibility here?