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

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.

---

they are asking size of stack after performing those operations so in that way 24B seems a wrong answer.

---

The question is referring to the additional memory required to support the max operation assuming it to be done in O(1) time -- though this is not mentioned in the question.

---

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