GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
319 views

How it is 24? I'm not getting it.

asked in DS by Loyal (4.4k points)  
edited by | 319 views
I too think 12 is correct
Still ambigious answer, no valid reason for weather it's 12 or 24??

3 Answers

+5 votes
Best answer

I think the answer is 24. 

If we see, there will be only three elements after all the operations which may prompt us to think the size of the stack is =12 bytes (3*4 bytes) .

But STACK is a static data structure  and hence needs to allocate space for all the numbers even if they are not present in the stack simultaneouly. 

Here , numbers are  - 5 5 6 6 7 8  (Consider them as block of memory rather than nummbers )

So, size of the  datastructure will be = 6* 4 Bytes= 24 Bytes 

PUSH and POP operations doesn't allocate or free memory . They are simply the  Increment/decrement of Stack Pointer.

answered by (445 points)  
selected by
if this is the case then we have atmost 4 elements.

push(5) push(6) push(7) pop push(6) push(8) pop pop push(5)

then 4*4=16

isn't it?

 

and other thing if we use linked list instead of array then what will be size??

There will be six elements after the above set of operations. So size of stack is 24. Max reports the maximum element in stack and will not remove it. And Stack need not be a static data structure. If Stack is implemented using a linked list then it can grow dynamically. PUSH operation will create a node, allocate memory to it and then add it to the stack. If so each node will also contain a pointer which will consume some memory. But no such condition is mentioned in the question and hence can be ignored.

I will upvote only if you remove that "I think" written in your answer. 

I have a better implementation for this. Consider storing the elements as the normal stack, but with it we have another stack to store the max element. Whenever we perform push operation on the original stack, we check if it is larger(or equal) than top of currMax stack, if it is we push it into both the stacks, otherwise push it only on the original stack. Now when we perform POP, we check if the top element of original stack is equal to the top element of currMax stack, if it is, then we pop from both the stacks, otherwise pop only from original stack.

Consider the example:

O denotes original stack, M denotes currMax stack. The rightmost element is the top element of the stack

push(5):

O: 5

M: 5

push(6):

O: 5 6

M: 5 6   (since, 6 >= 5)

push(7):

O: 5 6 7

M: 5 6 7 (since 7 >= 6)

pop:

O: 5 6

M: 5 6 (since top of M == element to be popped, i.e. 7 == 7)

max:

returns 6 (top of M)

push(6):

O: 5 6 6

M: 5 6 6  (since 6 >= 6)

push(8)

O: 5 6 6 8

M: 5 6 6 8  (since 8 >= 6)

pop:

O:5 6 6

M: 5 6 6  (since top of M == popped element, i.e 8 == 8)

pop:

O: 5 6

M: 5 6    (again, since top of M == popped element, i.e 6 == 6)

push(5):

O: 5 6 5

M: 5 6   (This time we will not push 5 into M, since 5 >= 6 is false).

So, this requires lesser space and same time complexity. So, the answer according to this is 20 (= 5 * 4)

Am I wrong somewhere?
When we implement a Stack using an array then it is static in nature and after push and pop operation no memory is allocated or freed but when we implement a Stack using linked list then for push operation we have to allocate memory and after pop operation memory is freed then I think the answer will be 12 bytes.
+2 votes

Ans b) 24

There will be six elements after the above set of operations. So size of stack is 24. Max reports the maximum element in stack and will not remove it. And Stack need not be a static data structure. If Stack is implemented using a linked list then it can grow dynamically. PUSH operation will create a node, allocate memory to it and then add it to the stack. If so each node will also contain a pointer which will consume some memory. But no such condition is mentioned in the question and hence can be ignored.

answered by Loyal (3.7k points)  
+1 vote

Answer Varies.

Stack is linear data structure.

If its static implementation of stack, iel using linear array then answer is 24 bytes. when total used space is asked.

If its dynamic implementation of stack, ie. using linked list then answer is 12 bytes.

Also if current allocated space asked in static implementation then its 12 bytes.

answered by Junior (537 points)  


Top Users Sep 2017
  1. Habibkhan

    7808 Points

  2. Warrior

    2746 Points

  3. rishu_darkshadow

    2692 Points

  4. Arjun

    2672 Points

  5. A_i_$_h

    2426 Points

  6. nikunj

    1980 Points

  7. manu00x

    1920 Points

  8. Bikram

    1854 Points

  9. makhdoom ghaya

    1770 Points

  10. SiddharthMahapatra

    1718 Points


26,239 questions
33,805 answers
80,214 comments
31,159 users