1

I need to compute the peek mid element also the problem statement for implementing this method is as follows:-

*returns object which has the middle value among the all objects without removing it from the stack. *returns the object which has the value of following order (size()/2)+1 *e.g. *When the stack has the following values (1, 2, 5, 4, 2, 6) *this method returns 4 and doesn't remove the object.

so my query is:-

should i consider the middle element in terms of position i.e. after sorting the elements of the stack the mid element is obtained as mid = stack[size()/2+1] or should i consider it in terms of value i.e. mid= max+min/2

as in above problem both the situations are correct( in my point of view) i.e.

stack[size()/2+1]=stack[6/2+1]=4

and max+min/2=6+1/2=3.5 and rounding off will be equal to 4

kindly help me understanding the problem statement

paul
  • 23
  • 1
  • 4

1 Answers1

1

A stack is a data structure, and as such in the most generic case should be able to store any data type. The fact that you are dealing with ints is just a simplification for your assignment. Data structure wise, it makes sense that you consider the middle element, and not perform any computation on element values (that is too specific for a data structure).

It seems like what you want is the ((n/2) + 1) th element, therefore the element at index (n/2) in this example.

filip-fku
  • 3,265
  • 1
  • 21
  • 19
  • yes...."in most generic case" but the problem given to me contains an interface of stack named" SortableStack". so all the confusion lies here as the name suggest that stack needs to be sorted... – paul Aug 22 '11 at 05:26
  • My answer still holds, you just may have to sort the underlying array before performing the operations. It seems strange to have a sortable stack though, since a stack is by definition "first in last out". But that's up to your homework spec:) – filip-fku Aug 22 '11 at 05:30
  • 1
    oh...got it....can you please tell me , if there is a way of getting this middle value without performing sorting..as sorting is a resource intensive task and in this problem i need to get only one value( i.e middle value) – paul Aug 22 '11 at 05:43
  • You can't avoid the sorting to find the middle element. Also if it's a sorted stack you should keep it sorted at all times. You can reduce the performance impact by inserting every element at the correct sorted position and ensure you have a sorted array at all times. This will cause an O(n) insert cost for each item. Once you have it sorted just use the approach in my answer.. – filip-fku Aug 22 '11 at 06:00