Функция, которая оставит самые маленькие вхождения в нижней части стека

Question

Я пытаюсь записать стек так, чтобы все вхождения наименьшего элемента находились внизу стека, а порядок остальных элементов не изменился. Например, если у меня есть стек [4,3,1,5,8,1,4], он станет [4,3,5,8,4,1,1], но моя проблема в том, что порядок меняетсяпоэтому я получу что-то вроде этого [4,5,3,4,8,1,1]

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

void minstack(stack<int> &s)
{

stack<int> t1,t2;
int count=0,min;
if(!s.empty())
    {

      while(!s.empty())
      {
          if(s.top() <min)
            { min=s.top();
                count=0;
                }

          t1.push(s.top()); s.pop();
          count++; 
      }
for(int i = 0 ; i<count;i++)

{
    s.push(min);
}

 while(!t1.empty())
      {
          if(t1.top()!=min);
          { s.push(t1.top());
              }
          t1.pop();
      }
}
}
int main()
{
    stack <int> s;
    s.push(4);
        s.push(3);
    s.push(1);
    s.push(5);
    s.push(8);
    s.push(1);
        s.push(4);
minstack(s);
while(!s.empty())
{
    cout<<s.top()<<" "; s.pop();
}

}

Answer 1

Вот идея. Сначала нам нужно найти наименьший элемент стека. Определите временный стек t. Теперь мы вытолкнем все элементы один за другим из s и поместим их в t. В то же время следите за минимальным значением min и количеством раз, с которым оно встречалось до сих пор в процессе добавления в count. Как только это будет сделано, обратите внимание, что у вас будет обратный порядок элементов в t и у вас будет min и count. Теперь мы вставим count количество элементов со значением min обратно в s. Затем начните выталкивать и толкать от t до s за исключением элементов, которые равны min.