CareerCup

If we can destroy the stack:
Pop the elements into a queue. Pop into queue twice, dequeue once. One pass.

T MiddleElement<T>(Stack<T> s) {
    if (s.IsEmpty()) throw;
    queue <T> candidates;
    T current;
    while(!s.IsEmpty()) {
        candidates.Enqueue(s.Pop());
        if (!s.IsEmpty()) {
            candidates.Enqueue(s.Pop());
        }
        current = candidates.Dequeue();
    }
    return current;
}

O(n) time. Unfold the stack recursively, calculate the index of the middle, then fold it back and return the middle.

template <class T>
pair<T, size_t> middle(stack<T> s, size_t i){
        if (s.empty()) 
                if (i == 0) throw "empty stack!";
        else    
                return make_pair<T, size_t>(T(), i / 2);
        T tmp = s.top();
        s.pop();                
        pair<T, size_t> res = middle(s, i + 1);
        s.push(tmp);    
        if (i == res.second) res.first = tmp; // found the middle!
        return res;     
}

If stack is stored in a linked list. then question reduces to finding the middle node in a linked list, which is possible using the two pointer strategy.

it wouldn't be in a list but it's a good question to ask the interviewer. based on what we know we have to assume it's a stack. in other words, you've got top, pop, push, size and thats it. hell if you had an iterator or access to the underlying vector or deque it'd a moot question

use two stacks.
space complexity will be doubled but push,pop,top,mid all will be O(1).
Idea is to push the element twice in second stack, so that the second stack will get filled twice as fast as first one so it'll always contain mid element on top for current available elements in stack one.

Below is the pseudo code:
Let S1 and S2 are two stacks and curMid=0

PUSH:
{
    S1.Push(data);
    if(S1.size() > S2.size())
    {
         if(S2.size()==0)curMid=data;
         S2.Push(curMid);
         S2.Push(curMid);
         curMid=S1.top();
    }
}
POP:
{
    data=S1.Pop();
    if(S1.size()+1 < S2.size())
    {
        S2.Pop();
        S2.Pop();
    }
    return data;
}
MID:
{
    return S2.top();
}

Example
let elements of stack are 1,4,3,2,22,55,9
then return 4

This was posted earlier in question?id=10274826 (which I suppose is the same question).

T MiddleElement<T>(Stack<T> s) {
    if (s.IsEmpty()) throw;
    queue <T> candidates;
    T current;
    while(!s.IsEmpty()) {
        candidates.Enqueue(s.Pop());
        if (!s.IsEmpty()) {
            candidates.Enqueue(s.Pop());
        }
        current = candidates.Dequeue();
    }
    return current;
}

Pop the stack and store the element into a binary search tree, the root should be the middle value.

pop the stack, store the elements into a dynamic array, keep track of the length of the array, when the stack is empty, find the middle element of the array.

Hi,
How about the following approach.

lets take stack is stack1.
lets take 2 pointers , p1 and p2
for every pop , keep increment p1 , so that p1 will point to latest pop'ed out element.
increment p2 for every odd count of pop's...

increment p2 , for 1 , 3 , 5 , pop'ings etc..
so at the end , p2 will point to middle element of the stack.

The idea is to get the middle element in O(1) T.C.
We maintain a Doubly Linked List as the under lying
data structure for storage. We maintain a pointer
to the middle element as the linked list grows or shrinks


public class MiddleStack{
private DLLNode headNode;
private DLLNode middleNode;
private int middleIndex;
private int size;

public MiddleStack(){
this.headNode = new DLLNode(null);
}

public void push(Object data){
if(headNode == null){ //empty stack
headNode = new DLLNode(data);
middleNode = headNode;
}else if(headNode.getData() == null){ //empty stack
headNode.setData(data);
middleNode = headNode;
}else{
DLLNode llNode = new DLLNode(data);
llNode.setNext(headNode);
headNode.setPrevious(llNode);
headNode = llNode;
}
size++;
if(size == 1){
middleIndex = 1;
} else if (middleIndex < Math.round((double)size/ 2.0 )){
middleIndex++;
middleNode = middleNode.getPrevious();
}
}

public Object top(){
if(headNode == null || headNode.getData() == null){
return null;
}else{
return headNode.getData();
}
}

public Object pop(){
if(headNode == null || headNode.getData() == null){
throw new EmptyStackException("Stack empty");
}else{
Object data = headNode.getData();
if(headNode.getNext() == null){
headNode.setData(null);
}else{
headNode = headNode.getNext();
}
headNode.setPrevious(null);
size--;
if(size == 1){
middleIndex = 1;
} else if (middleIndex > Math.round((double)size/ 2.0 )){
middleIndex--;
middleNode = middleNode.getNext();
}
return data;
}
}

public Object getMiddle(){
return middleNode.getData();
}

public static void main(String[] args){
MiddleStack middleStack = new MiddleStack();
middleStack.push(1);
middleStack.push(2);
middleStack.push(3);
middleStack.push(4);
middleStack.push(5);
middleStack.push(6);
middleStack.push(7);
middleStack.push(8);
middleStack.push(9);
middleStack.push(10);
while(!middleStack.isEmpty()){
System.out.println("Top: " + middleStack.top() + " ---> Middle: " + middleStack.getMiddle());
middleStack.pop();
}
}

}


The output of the main method is as follows.
Top: 10 ---> Middle: 5
Top: 9 ---> Middle: 5
Top: 8 ---> Middle: 4
Top: 7 ---> Middle: 4
Top: 6 ---> Middle: 3
Top: 5 ---> Middle: 3
Top: 4 ---> Middle: 2
Top: 3 ---> Middle: 2
Top: 2 ---> Middle: 1
Top: 1 ---> Middle: 1

why all are telling the middle of the stack by index.........tell the middle of the stack by value....
like sorting the stack and then returning the middle element of sorted stack

give more efficient algorithm for this

Let us consider stack as S, and take two stacks S1 and S2. Pop from S and push into S1 and S2 alternatively and make count of elements say COUNT. If COUNT is even then you can take any of two stacks S1,S2(because middle of stack contains two elements) and send it to the same function iteratively. If COUNT is odd, take second stack S2 and send to the same function iteratively. Do this until you get COUNT = 1 in S2.

I am a little confused... Is the question about the middle index value of the stack or the median of the stack? I am assuming its the middle value(median)
Eg:

Elements of Stack: 
2
7
4
5
1
8
6
5
3

Here middle indexed value is 1 ( index 4)
Where as median is 4

Please let me know if I misunderstood the problem??

If it is middle value, then we can do the following

1. Pop all the elements of the stack and sum them and divide my the number of elements, in the above example 2+7+4+5+1+8+6+5+3= 42 => 42/9 => 4
2. Push all the elements back to the stack and while pushing store the value nearest to your calculated median.
3. Return the index and median of the stack.

If it is middle value, then we can do the following

1. Pop all the elements of the stack and sum them and divide my the number of elements, in the above example 2+7+4+5+1+8+6+5+3= 42 => 42/9 => 4
2. Push all the elements back to the stack and while pushing store the value nearest to your calculated median.
3. Return the index and median of the stack.

sort the stack using two temporary stacks(not constraint on space, we can do with one temporary stack) and i counted the no of elements in the stack. At the end of first outer loop, i can able to get the sorted stack in s1 and i have no of elements "count". While popping back, using "count", i can able to get the middle value(median). If the "count" is even (mid1+mid2)/2 becomes the median, otherwise mid2
becomes the median.
clarify me if there are any errors.

int returnMidVal(stack s)
{
  int count=0,val=0,val1=0;
  stack s1, s2;
  while(s!=null)
  {
   val = s.pop(); 
   count++;
   while(s1!=null)
   {
     val1 = s1.pop();
     if(val >= val1)
     {
       s1.push(val1);
       break;
     }
     else
     {
       s2.push(val1);
     } 
   }
   s1.push(val);
   while(s2!=null)
   {
     s1.push(s2.pop());
   }
  }
  if(count == 0) return 0;
  int mid1, mid2;
  int index = 0;
  while(s1!=null)
  {
    val = s1.pop();
    index++;
    if(index == (count/2)) mid1 = val;
    if(index == (count/2)+1) mid2 = val;
    s.push(val);
  }
  if(count%2 ==0)
  {
    return (mid1+mid2)/2;
  }
  else
  {
    return mid2;
  }
}

Sorry for the wrong algo...as Ravi mentioned, I was calculating the mean not the median. The solution posted by Ravi works perfect, but I guess it can be improved alot by using arrays instead of 2 extra stacks and lot of push and pop operations.

Following algo can be used to find the middle value
1. pop all the elements of the stack into an array ( you will get the num of elements in the stack)
2. Apply quick sort partition algo on th array, by selecting a random pivot
- using the pivot index we can determine if the median lies left of the pivot or in the right
- select an appropriate half and apply the partion algo, until we find the pivot that is the center of the array
3. Return that element or the median of medians

That treatment has on better tracking, and seems common and trends cause of a work or strain. See your acupuncture, best herbalist the human helps as.