Data Structure stack-max

Question

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

Comments

Defiantly this question is ambiguous because they haven't told how they are actually implementing the max so answer varies how you interpret the question by applying different approaches and interpretation we will get different answer like 12,16,24 etc,

---

They have given this solution where they have mentioned 4B in question but given the answer according to 8B!

---

So, What is the conclusion  .... I am confused

Someone is saying 16 or 32 or 20 or 8 !!!

Answer 1

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.

Comments

Hello Sir , sorry but i didn't get your point.

How can we tell MAX of an array in O(1)?

---

Suppose this question of Stack with Max operation is given as a programming assignment -- how will you do it?

---

Hello sir , sorry for late response. Happy Diwali :)

as i'm able to see , if there is condition like 'No additional space avail' then i don't think that this work can be done in constant time...if there is again condition like only PUSH is allowed , no POP then , using some temp variable we can certainly tell MAX in const time but when 'in b/w' POP is going on , we can't tell MAX in O(1) unless we use some additional stack like Rishabh answered...

I'm not that good with programming , please tell me if i went wrong somewhere.

Answer 2

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.

Answer 3

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.

Answer 4

Its a made easy test series question.

After performing all the operations stack will have 3 values and max will have 1 value so size of data structure after all these operations = size of stack+max= (3+1)*4 =16.

 

In made easy solution,they have given 24 as answer and they have assumed that eachs tack entry is 8B(but question says4).

But we need to include memory occupied by max also as it is part of the data structure.

So 16 should be correct answer

Answer 5

Ans: 20 bytes

Applying efficient algorithm, 

Main_Stack	Max_Stack
5
8	8
6
7	7
6	6
5	5

Here, when 7 is pushed, new entry is created in MAX_STACK because it is the new MAX. 

Next element to be pushed is 6. Applying efficient algorithm there is no need to push it in MAX_STACK. 

Similarly, when 8 is pushed, new entry is created in MAX_STACK of new MAX.

Now, coming to POP peration, 8,6,7 are popped from MAIN_STACK and along with it 8 and 7 are also popped from MAX_STACK.

At the end, 5 is pushed on MAIN_STACK and no need to insert it on MAX_STACK.

So, final table is - 

MAIN_STACK	MAX_STACK
5
6	6
5	5

So, total number of elements = 5

Total size = 5*4 bytes = 20 Bytes

PS : Above concept is discussed in Data Structures and Algorithms - Narasimha Karumanchi