The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.5k views

A single array $A[1 .. MAXSIZE]$ is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables $top1$ and $top2$ $(top < 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 “stack full” is

  1. $(top1 = MAXSIZE / 2)$ and $(top2 = MAXSIZE / 2 + 1)$

  2. $top1 + top2 = MAXSIZE$

  3. $(top1 = MAXSIZE / 2)$ or $(top2 = MAXSIZE)$

  4. $top1 = top2 - 1$

asked in DS by Veteran (59.4k points)
edited by | 2.5k views
+2
Option D is true

let n=10 size of array
indexing 1 to 10
//define the constant
Initialsize 0
Maxsize 11

let stack1 represent as x=0
let stack2 represent as x=1
initial value of top1=Initialsize;
initial value of top2=Maxsize;
push(int n,int x)
{
if(top1==(top2-1))
{
stack overflow
}
else
{
if(x==0)
{
stack[top]=x;
top++;
}
else
{
stack[top]=x;
top--;
}
}
}

int pop(int n,int x)
{
int p;
if(x==0)
{
if(top1==Initialsize)
{
stack1 is empty
return;
}
else
{
p= top1;
top1--;
}
}
else
{
if(top2==Maxsize)
{
stack2 is empty
return;
}
else
{
p= top2;
top2++;
}
}
}

5 Answers

+30 votes
Best answer

ans (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$;

answered by Active (5.2k points)
edited by
0

@arjun SIR , 

The two stacks grow from opposite ends of the array. 

top 1 grows from begining and top 2 grows from end  the moment it crosses is top 1 <= N-top 2 then Option B should be correct ?

+2

Gokhu top1 is 1st index and top 2 is last index . sum is maxsize is not for full stack condition na.

top1                                              top2

now seek top1+ top2= maxsize but stack contain 2 elements only.

12      13   14    15     16    17   18      19 (top1)     21(top2)   20  

here top1= top2-1 shows stack is full only.

 

0

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 ?

0
@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.
+11 votes

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

answered by Veteran (59.6k points)
0

@gokou  check here

0

@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  

0

@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 ?

+5 votes

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/

answered by Loyal (7.6k points)
–4 votes
A ) top1= ⎣MAXSIZE/2⎦

     top2= ⎣MAXSIZE/2⎦+1
answered by Active (2.7k points)
0
That would limit the maximum size of each stack to be half of the array.
–4 votes
I think both A and D are correct.actually both defining same thing.
answered by Active (2.6k points)
+2
no Option D is variable in nature but A is fixed to mid point and adjacent to mid.
0
got it. Thank you.

So D is the answer
0
@anirudh SIR , Why not B?


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,526 questions
42,803 answers
121,617 comments
42,166 users