edited by
35,122 views
48 votes
48 votes

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

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

  2. $top1 + top2 = \text{MAXSIZE}$

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

  4. $top1 = top2 - 1$

edited by

6 Answers

Best answer
62 votes
62 votes

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$.

edited by
36 votes
36 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

6 votes
6 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/

6 votes
6 votes

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:

Related questions

19 votes
19 votes
4 answers
1
Kathleen asked Sep 18, 2014
6,945 views
The best data structure to check whether an arithmetic expression has balanced parentheses is aqueuestacktreelist
27 votes
27 votes
3 answers
2
Kathleen asked Sep 18, 2014
5,595 views
The elements $32, 15, 20, 30, 12, 25, 16,$ are inserted one by one in the given order into a maxHeap. The resultant maxHeap is
19 votes
19 votes
3 answers
4
Kathleen asked Sep 18, 2014
6,388 views
Level order traversal of a rooted tree can be done by starting from the root and performingpreorder traversalin-order traversaldepth first searchbreadth first search