Преобразование из десятичной в двоичную в Ocaml

Мы знаем, что push и pop являются постоянными операциями времени [O (1), чтобы быть точным].

Но когда мы думаем о get_min () [т.е. для нахождения текущего минимального числа в очереди] обычно первое, что приходит на ум, - это поиск всей очереди каждый раз, когда выполняется запрос для элемента минимума. Но это никогда не даст постоянной работы, что является главной целью проблемы.

Обычно это часто задают в интервью, поэтому вы должны знать трюк

To сделайте это, мы должны использовать еще две очереди, которые будут содержать дорожку минимального элемента, и мы должны продолжить модификацию этих двух очередей, поскольку мы выполняем операции push и pop в очереди, чтобы минимальный элемент был получен в O (1) раз.

Вот самоописательный судо-код, основанный на упомянутом выше подходе.

    Queue q, minq1, minq2;
    isMinq1Current=true;   
    void push(int a)
    {
      q.push(a);
      if(isMinq1Current)
      {
        if(minq1.empty) minq1.push(a);
        else
        {
          while(!minq1.empty && minq1.top < =a) minq2.push(minq1.pop());
          minq2.push(a);
          while(!minq1.empty) minq1.pop();
          isMinq1Current=false;
        }
      }
      else
      {
        //mirror if(isMinq1Current) branch. 
      }
    }

    int pop()
    { 
      int a = q.pop();
      if(isMinq1Current)
      {
        if(a==minq1.top) minq1.pop();
      }
      else
      {
        //mirror if(isMinq1Current) branch.    
      }
    return a;
    }