Mid of stack using LinkedList

[ibilal]

Hi all,

I am unable to make any logical algorithm to access middle of stack. Please guide some with examples. I am using stack implemented with linkedlists, I have following functions available for stack like push,pop,top.

Thanks

[LB]

First you have to find out how large the stack is; you can do this by popping elements off the stack and pushing them onto a temp stack. Once you know how big it is, you can figure out which nth item is the middle. Then you just pop off the temp stack, pushing into the original stack again, until you get the middle element. Once you've got that, deal with it, then continue pushing back onto the original stack.

By the end, you have everything back the way it was and you have already accessed the middle element.

[ibilal]

I got some code to work hardcode way, it works for odd numbers. How would I work for even?

int getMid()
{
	if(!isEmpty())
	{
		int x=getSize();
         	int temp=1;
		int temp2=0;
		if(x%2==0)
		{
			for(;temp<x;temp++)
			{
				pop();
			}
			return top();
		}
		else
		{
			//Missing Part???
		}
			
	}
	else
        {
		return NULL;
	}

}

[LB]

If there are an even number of elements, what do you define as the 'middle'?

[moorecm]

Question: How do I get to the 'middle' element of a stack?
Answer: You don't.

If this is a requirement, throw the use of a stack out and find the right data structure!

[vlad from moscow]

An example based on std::stack<int> (without testing)

#include <iostream>
#include <stdexcept>
#include <stack>

int GetMiddleElement( std::stack<int> s ) throw( std::invalid_argument )
{
   if ( s.size() == 0 ) throw std::invalid_argument( "Stack is empty" );

   std::stack<stack>::size_type middle = s.size() / 2;

   for ( std::stack<int>::size_type i = 0; i < middle; i++ ) s.pop();

   return ( s.top() );
}   


int main()
{
   std::stack<int> s = { 1, 2, 3, 4, 5 };

   std::cout << "The middle element = " << GetMiddleElement( s ) << std::endl;

}

[vlad from moscow]

It is strange enough but std::stack has no constructor with initializer list. So the code above I rewrote as

#include <iostream>
#include <stdexcept>
#include <stack>
 
int GetMiddleElement( std::stack<int> s ) throw( std::invalid_argument )
{
   if ( s.size() == 0 ) throw std::invalid_argument( "Stack is empty" );
 
   std::stack<int>::size_type middle = s.size() / 2;
 
   for ( std::stack<int>::size_type i = 0; i < middle; i++ ) s.pop();
 
   return ( s.top() );
}   
 
 
int main()
{
   std::stack<int> s;
   s.push( 5 ); s.push( 4 ); s.push( 3 ); s.push( 2 ); s.push( 1 );
 
   std::cout << "The middle element = " << GetMiddleElement( s ) << std::endl;
 
}