Finding maximum elemet of Stack and deleting it.

[Abdulkhamid]

Hello. I am new in working with c++ stacks. I have a question. How to find the maximum element of stack, then delete it. Thanks in advance.

[Enoizat]

I think you need to pop() all elements and store them into another; then pop() them again and push() them in the original one, skipping the biggest.
I have no idea if there are fastest methods.

[Duthomhas]

Outside of special non-stack accesses into the underlying data, Enoizat has it exactly.

When thinking of stacks, it is useful to imagine those things a buffet restaurants that hold plates. You cannot get to other plates without touching the top plate.

Find the biggest

 3
|7|  |-|
|4|  | |
---  - -

 7    3    biggest so far: 3
|4|  |-|
|-|  | |
- -  - -

 4    7    biggest so far: 7
|-|  |3|
| |  |-|
- -  - -

      4    biggest so far: 7
|-|  |7|
| |  |3|
- -  ---

Eliminate the biggest

 4    7
|-|  |3|
| |  |-|
---  - -

 4    3      toss 7
|-|  |-|
| |  |-|
---  - -

 4    
|3|  |-|
|-|  | |
- -  - -

Enjoy!

[lastchance]

#include <iostream>
#include <stack>
using namespace std;

//==========================================================

template<typename T> T haircut( stack<T> &S )
{
   if ( S.empty() ) return T{};

   // Pop contents of stack into a temporary stack, finding maximum at the same time
   T maximum = S.top();
   stack<T> temp;
   while ( !S.empty() )                
   {
      T value = S.top();
      if ( maximum < value ) maximum = value;
      temp.push( value );
      S.pop();
   }

   // Put back in the stack all but the maximum
   while ( !temp.empty() )
   {
      T value = temp.top();
      if ( value != maximum ) S.push( value );
      temp.pop();
   }

   return maximum;
}

//==========================================================

template<typename T> ostream & operator << ( ostream &strm, stack<T> S )   // deliberately pass copy
{
   while ( !S.empty() )                
   {
      strm << S.top() << " ";
      S.pop();
   }
   return strm;
}

//==========================================================

int main()
{
   stack<int> S;
   for ( int i : { 1, 2, 3, 4, 5, 4, 3, 2, 5, 4, 3, 2, 1, 0 } ) S.push( i );

   cout << "Initial stack (in REVERSE order): " << S << '\n';
   while ( !S.empty() ) cout << "Maximum is " << haircut( S ) << "    Stack is now " << S << '\n';
}

[Enoizat]

Perhaps, if the stack provides a method to get its size, we don’t need to pop() the last value, unless it is the biggest…
Anyway, I think it never needs to be pushed into the temporary copy.

[jonnin]

in practice, you would not use a <stack> c++ container here.

vector's push_back and pop_back are enough to make as good a stack as <stack>, and then you can use remove/erase / iteration to find biggest etc to solve this problem.

Several other containers would also work, list for sure, and probably could rig a map of some flavor to do it.

[lastchance]

jonnin wrote:

in practice, you would not use a <stack> c++ container here.

vector's push_back and pop_back are enough to make as good a stack as <stack>, and then you can use remove/erase / iteration to find biggest etc to solve this problem.

But @jonnin, that would have taken all the FUN out of the problem! And @Duthomas's wonderful ASCII art would have been in vain!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template<typename T> T haircut( vector<T> &S )
{
   if ( S.empty() ) return T{};
   T maximum = *max_element( S.begin(), S.end() );
   S.erase( remove( S.begin(), S.end(), maximum ), S.end() );
   return maximum;
}

template<typename T> ostream & operator << ( ostream &strm, vector<T> &S )
{
   for ( auto e : S ) strm << e << " ";               
   return strm;
}

int main()
{
   vector<int> S{ 1, 2, 3, 4, 5, 4, 3, 2, 5, 4, 3, 2, 1, 0 };
   cout << "Initial vector: " << S << '\n';
   while ( !S.empty() ) cout << "Maximum is " << haircut( S ) << "    Vector is now " << S << '\n';
}