Ответ 1

Вы можете реализовать стек с помощью O (1) pop(), push() и get_min(): просто сохраните текущий минимум вместе с каждым элементом. Так, например, стек [4,2,5,1] (1 сверху) становится [(4,4), (2,2), (5,2), (1,1)].

Затем вы можете использовать два стека для реализации очереди. Нажмите на один стек, поп из другого; если второй стек пуст во время поп, переместите все элементы из первого стека во второй.

Например, для запроса pop, перемещая все элементы из первого стека [(4,4), (2,2), (5,2), (1,1)], второй стек будет [(1,1), (5,1), (2,1), (4,1)]. и теперь верните верхний элемент из второго стека.

Чтобы найти минимальный элемент очереди, посмотрите на наименьшие два элемента отдельных мини-стеков, затем возьмите минимум этих двух значений. (Конечно, здесь есть дополнительная логика: случай, когда один из стеков пуст, но это не так сложно работать).

Он будет иметь O (1) get_min() и push() и амортизируется O (1) pop().

Ответ 2

Хорошо - я думаю, что у меня есть ответ, который дает вам все эти операции в амортизированном O (1), что означает, что любая одна операция может занимать O (n), но любая последовательность из n операций принимает O (1) время на операцию.

Идея состоит в том, чтобы хранить ваши данные как декартово дерево. Это двоичное дерево, подчиняющееся свойству min-heap (каждый node не больше его дочерних элементов) и упорядочен таким образом, что обход узлов по порядку возвращает вам узлы в том же порядке, в котором они были добавлено. Например, здесь декартово дерево для последовательности 2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

Можно вставить элемент в декартово дерево в O (1), амортизированное время, используя следующую процедуру. Посмотрите на правый позвоночник дерева (путь от корня до самого правого листа, образованный всегда, идя вправо). Начиная с самого правого node, сканируйте вверх по этому пути, пока не найдете первый node меньше, чем node, который вы вставляете.
Измените этот node так, чтобы его правый дочерний элемент был этим новым node, затем сделайте этот node прежний правый дочерний левый дочерний элемент node, который вы только что добавили. Например, предположим, что мы хотим вставить другую копию 2 в указанное выше дерево. Мы поднимаемся по правому корешку мимо 5 и 3, но останавливаемся ниже 1, потому что 1 < 2. Затем мы изменим дерево, чтобы выглядеть так:

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Обратите внимание, что обход по порядку дает 2 1 4 3 5 2, который представляет собой последовательность, в которую мы добавили значения.

Это выполняется в амортизированном O (1), потому что мы можем создать потенциальную функцию, равную числу узлов в правом разрезе дерева. Реальное время, необходимое для вставки node, равно 1 плюс число узлов в рассматриваемом нами позвоночнике (назовем это k). Как только мы найдем место для вставки node, размер позвоночника сократится на длину k - 1, так как каждый из k узлов, которые мы посетили, больше не находится на правом хребте, а новый node находится на своем месте, Это дает амортизированную стоимость 1 + k + (1 - k) = 2 = O (1) для амортизированной вставки O (1). В качестве другого способа думать об этом, как только node был удален с правого позвоночника, он никогда не будет частью правого позвоночника, и поэтому нам больше не придется его перемещать. Поскольку каждый из n узлов может перемещаться не более одного раза, это означает, что n вложений может выполнять не более n ходов, поэтому общая продолжительность выполнения не более O (n) для амортизированного O (1) для каждого элемента.

Чтобы сделать шаг dequeue, мы просто удалим левый node из декартового дерева. Если этот node является листом, мы закончили. В противном случае node может иметь только один дочерний элемент (правый ребенок), и поэтому мы заменим node его правым дочерним элементом. При условии, что мы будем отслеживать, где находится самый левый node, этот шаг занимает O (1) раз. Однако, удалив самый левый node и заменив его своим правым дочерним элементом, мы можем не знать, где находится новый левый node. Чтобы исправить это, мы просто ходим по левому позвоночнику дерева, начиная с нового node, который мы только что переместили в самый левый ребенок. Я утверждаю, что это все еще работает в O (1) амортизированном времени. Чтобы убедиться в этом, я утверждаю, что node посещается не более одного раза во время любого из этих проходов, чтобы найти самый левый node. Чтобы увидеть это, обратите внимание, что после того, как этот node был посещен таким образом, единственный способ, который нам когда-либо понадобится, посмотреть на него снова, будет, если бы он был перемещен из дочернего элемента самого левого node в самый левый node. Но все узлы, которые были посещены, являются родителями самого левого node, поэтому этого не может быть. Следовательно, каждый node посещается не более одного раза во время этого процесса, а pop запускается в O (1).

Мы можем найти find-min в O (1), потому что декартово дерево дает нам доступ к наименьшему элементу дерева бесплатно; это корень дерева.

Наконец, чтобы увидеть, что узлы возвращаются в том же порядке, в котором они были вставлены, обратите внимание, что декартово дерево всегда хранит свои элементы, так что обход посещений посещает их в отсортированном порядке. Поскольку мы всегда удаляем самый левый node на каждом шаге, и это первый элемент обхода порядка, мы всегда возвращаем узлы в том порядке, в котором они были вставлены.

Короче говоря, мы получаем O (1) амортизированный push и pop, а O (1) наихудший поиск-min.

Если я смогу придумать наихудшую реализацию O (1), я обязательно опубликую ее. Это была большая проблема; спасибо за публикацию!

Ответ 3

Хорошо, вот одно решение.

Сначала нам нужны некоторые вещи, которые предоставляют push_back(), push_front(), pop_back() и pop_front() в 0 (1). Его легко реализовать с помощью массива и двух итераторов. Первый итератор будет указывать на фронт, второй на спину. Позвольте назвать такой материал deque.

Вот псевдокод:

class MyQueue//Our data structure
{
    deque D;//We need 2 deque objects
    deque Min;

    push(element)//pushing element to MyQueue
    {
        D.push_back(element);
        while(Min.is_not_empty() and Min.back()>element)
             Min.pop_back();
        Min.push_back(element);
    }
    pop()//poping MyQueue
    {
         if(Min.front()==D.front() )
            Min.pop_front();
         D.pop_front();
    }

    min()
    {
         return Min.front();
    }
}

Объяснение:

Пример дайте push номера [12,5,10,7,11,19] и нашему MyQueue

1) нажатие 12

D [12]
Min[12]

2) нажатие 5

D[12,5]
Min[5] //5>12 so 12 removed

3) нажатие 10

D[12,5,10]
Min[5,10]

4) нажатие 7

D[12,5,10,7]
Min[5,7]

6) нажатие 11

D[12,5,10,7,11]
Min[5,7,11]

7) нажатие 19

D[12,5,10,7,11,19]
Min[5,7,11,19]

Теперь позвоните по вызову pop_front()

мы получили

 D[5,10,7,11,19]
 Min[5,7,11,19]

Минимум 5

Позвольте снова вызвать pop_front()

Объяснение: pop_front удалит 5 из D, но также добавит передний элемент Min, потому что он равен D переднему элементу (5).

 D[10,7,11,19]
 Min[7,11,19]

И минимум равен 7.:)

Ответ 4

Используйте один deque (A) для хранения элементов и другого deque (B) для сохранения минимумов.

Когда x выставлен в очередь, push_back это в и сохраните pop_backing B, пока задняя часть B не станет меньше x, а затем push_back x в B.

при удалении A, pop_front A в качестве возвращаемого значения, и если он равен фронту B, pop_front B также.

при получении минимума A используйте переднюю часть B как возвращаемое значение.

dequeue и getmin, очевидно, O (1). Для операции enqueue рассмотрите push_back из n элементов. Существует n push_back для A, n push_back для B и не более n pop_back из B, потому что каждый элемент либо останется в B, либо будет выведен один раз из B. Во всех случаях есть операции O (3n), и поэтому амортизированная стоимость равна O (1), а также для очереди.

Наконец, причина, по которой этот алгоритм работает, заключается в том, что когда вы вставляете x в A, если в B есть элементы, большие, чем x, они никогда не будут минимальными, потому что x останется в очереди A дольше, чем любые элементы в B (очередь FIFO). Поэтому нам нужно выскочить элементы в B (сзади), которые больше x, прежде чем мы нажмем x в B.

from collections import deque


class MinQueue(deque):
    def __init__(self):
        deque.__init__(self)
        self.minq = deque()

    def push_rear(self, x):
        self.append(x)
        while len(self.minq) > 0 and self.minq[-1] > x:
            self.minq.pop()
        self.minq.append(x)

    def pop_front(self):
        x = self.popleft()
        if self.minq[0] == x:
            self.minq.popleft()
        return(x)

    def get_min(self):
        return(self.minq[0])

Ответ 5

Если вы не возражаете хранить немного лишних данных, для сохранения минимального значения должно быть тривиально. Push и pop могут обновлять значение, если новый или удаленный элемент является минимальным, и возврат минимального значения так же просто, как получение значения переменной.

Предполагается, что get_min() не изменяет данные; если вы предпочитаете что-то вроде pop_min() (т.е. удаляете минимальный элемент), вы можете просто сохранить указатель на фактический элемент и предшествующий ему элемент (если есть) и обновить их соответственно с помощью push_rear() и pop_front() также.

Редактировать после комментариев:

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

Ответ 6

Решения по этому вопросу, включая код, можно найти здесь: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

Ответ 7

Фактически вы можете использовать LinkedList для поддержания очереди.

Каждый элемент LinkedList будет иметь тип

class LinkedListElement
{
   LinkedListElement next;
   int currentMin;
}

У вас может быть два указателя. Один указывает на "Пуск", а другие - на "Конец".

Если вы добавите элемент в начало очереди. Изучите указатель Start и node для вставки. Если node для вставки currentmin меньше начального токаmin node для вставки currentmin является минимальным. Else обновить currentmin с помощью start currentmin.

Повторите то же самое для enque.

Ответ 8

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

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

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

Чтобы сделать это, мы должны использовать еще две очереди, которые будут содержать трек минимального элемента, и мы должны продолжить модификацию этих двух очередей, поскольку мы делаем операции 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;
    }

Ответ 9

#include <iostream>
#include <queue>
#include <deque>
using namespace std;

queue<int> main_queue;
deque<int> min_queue;

void clearQueue(deque<int> &q)
{
  while(q.empty() == false) q.pop_front();
}

void PushRear(int elem)
{
  main_queue.push(elem);

  if(min_queue.empty() == false && elem < min_queue.front())
  {
      clearQueue(min_queue);
  }

  while(min_queue.empty() == false && elem < min_queue.back())
  {
      min_queue.pop_back();
  }

  min_queue.push_back(elem);
}

void PopFront() 
{
  int elem = main_queue.front();
  main_queue.pop();

  if (elem == min_queue.front())
  {
       min_queue.pop_front();
  }
}

int GetMin() 
{ 
  return min_queue.front(); 
}

int main()
{
  PushRear(1);
  PushRear(-1);
  PushRear(2);

  cout<<GetMin()<<endl;
  PopFront();
  PopFront();
  cout<<GetMin()<<endl;

  return 0;
}

Ответ 10

Это решение содержит 2 очереди:
 1. main_q - сохраняет номера ввода.
 2. min_q - сохраняет минимальные номера по определенным правилам, которые мы будем описывать (появляются в функциях MainQ.enqueue(x), MainQ.dequeue(), MainQ.get_min()).

Вот код в Python. Очередь реализуется с использованием списка.
Основная идея заключается в функциях MainQ.enqueue(x), MainQ.dequeue(), MainQ.get_min().
Одно из основных предположений заключается в том, что опустошение очереди занимает o (0).
Тест завершен.

import numbers

class EmptyQueueException(Exception):
    pass

class BaseQ():
    def __init__(self):
        self.l = list()

    def enqueue(self, x):
        assert isinstance(x, numbers.Number)
        self.l.append(x)

    def dequeue(self):
        return self.l.pop(0)

    def peek_first(self):
        return self.l[0]

    def peek_last(self):
        return self.l[len(self.l)-1]

    def empty(self):
        return self.l==None or len(self.l)==0

    def clear(self):
        self.l=[]

class MainQ(BaseQ):
    def __init__(self, min_q):
        super().__init__()
        self.min_q = min_q

    def enqueue(self, x):
        super().enqueue(x)
        if self.min_q.empty():
            self.min_q.enqueue(x)
        elif x > self.min_q.peek_last():
            self.min_q.enqueue(x)
        else: # x <= self.min_q.peek_last():
            self.min_q.clear()
            self.min_q.enqueue(x)

    def dequeue(self):
        if self.empty():
            raise EmptyQueueException("Queue is empty")
        x = super().dequeue()
        if x == self.min_q.peek_first():
            self.min_q.dequeue()
        return x

    def get_min(self):
        if self.empty():
            raise EmptyQueueException("Queue is empty, NO minimum")
        return self.min_q.peek_first()

INPUT_NUMS = (("+", 5), ("+", 10), ("+", 3), ("+", 6), ("+", 1), ("+", 2), ("+", 4), ("+", -4), ("+", 100), ("+", -40),
              ("-",None), ("-",None), ("-",None), ("+",-400), ("+",90), ("-",None),
              ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None))

if __name__ == '__main__':
    min_q = BaseQ()
    main_q = MainQ(min_q)

    try:
        for operator, i in INPUT_NUMS:
            if operator=="+":
                main_q.enqueue(i)
                print("Added {} ; Min is: {}".format(i,main_q.get_min()))
                print("main_q = {}".format(main_q.l))
                print("min_q = {}".format(main_q.min_q.l))
                print("==========")
            else:
                x = main_q.dequeue()
                print("Removed {} ; Min is: {}".format(x,main_q.get_min()))
                print("main_q = {}".format(main_q.l))
                print("min_q = {}".format(main_q.min_q.l))
                print("==========")
    except Exception as e:
        print("exception: {}".format(e))

Вывод теста выше:

"C:\Program Files\Python35\python.exe" C:/dev/python/py3_pocs/proj1/priority_queue.py
Added 5 ; Min is: 5
main_q = [5]
min_q = [5]
==========
Added 10 ; Min is: 5
main_q = [5, 10]
min_q = [5, 10]
==========
Added 3 ; Min is: 3
main_q = [5, 10, 3]
min_q = [3]
==========
Added 6 ; Min is: 3
main_q = [5, 10, 3, 6]
min_q = [3, 6]
==========
Added 1 ; Min is: 1
main_q = [5, 10, 3, 6, 1]
min_q = [1]
==========
Added 2 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2]
min_q = [1, 2]
==========
Added 4 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2, 4]
min_q = [1, 2, 4]
==========
Added -4 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4]
min_q = [-4]
==========
Added 100 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100]
min_q = [-4, 100]
==========
Added -40 ; Min is: -40
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 5 ; Min is: -40
main_q = [10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 10 ; Min is: -40
main_q = [3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 3 ; Min is: -40
main_q = [6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Added -400 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400]
min_q = [-400]
==========
Added 90 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 6 ; Min is: -400
main_q = [1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 1 ; Min is: -400
main_q = [2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 2 ; Min is: -400
main_q = [4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 4 ; Min is: -400
main_q = [-4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed -4 ; Min is: -400
main_q = [100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 100 ; Min is: -400
main_q = [-40, -400, 90]
min_q = [-400, 90]
==========
Removed -40 ; Min is: -400
main_q = [-400, 90]
min_q = [-400, 90]
==========
Removed -400 ; Min is: 90
main_q = [90]
min_q = [90]
==========
exception: Queue is empty, NO minimum

Process finished with exit code 0

Ответ 11

Реализация Java   

import java.io.*;
import java.util.*;

public class queueMin {
    static class stack {

        private Node<Integer> head;

        public void push(int data) {
            Node<Integer> newNode = new Node<Integer>(data);
            if(null == head) {
                head = newNode;
            } else {
                Node<Integer> prev = head;
                head = newNode;
                head.setNext(prev);
            }
        }

        public int pop() {
            int data = -1;
            if(null == head){
                System.out.println("Error Nothing to pop");
            } else {
                data = head.getData();
                head = head.getNext();
            }

            return data;
        }

        public int peek(){
            if(null == head){
                System.out.println("Error Nothing to pop");
                return -1;
            } else {
                return head.getData();
            }
        }

        public boolean isEmpty(){
            return null == head;
        }
    }

    static class stackMin extends stack {
        private stack s2;

        public stackMin(){
            s2 = new stack();
        }

        public void push(int data){
            if(data <= getMin()){
                s2.push(data);
            }

            super.push(data);
        }

        public int pop(){
            int value = super.pop();
            if(value == getMin()) {
                s2.pop();
            }
            return value;
        }

        public int getMin(){
            if(s2.isEmpty()) {
                return Integer.MAX_VALUE;
            }
            return s2.peek();
        }
    }

     static class Queue {

        private stackMin s1, s2;

        public Queue(){
            s1 = new stackMin();
            s2 = new stackMin();
        }

        public  void enQueue(int data) {
            s1.push(data);
        }

        public  int deQueue() {
            if(s2.isEmpty()) {
                while(!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
            }

            return s2.pop();
        }

        public int getMin(){
            return Math.min(s1.isEmpty() ? Integer.MAX_VALUE : s1.getMin(), s2.isEmpty() ? Integer.MAX_VALUE : s2.getMin());
        }

    }



   static class Node<T> {
        private T data;
        private T min;
        private Node<T> next;

        public Node(T data){
            this.data = data;
            this.next = null;
        }


        public void setNext(Node<T> next){
            this.next = next;
        }

        public T getData(){
            return this.data;
        }

        public Node<T> getNext(){
            return this.next;
        }

        public void setMin(T min){
            this.min = min;
        }

        public T getMin(){
            return this.min;
        }
    }

    public static void main(String args[]){
       try {
           FastScanner in = newInput();
           PrintWriter out = newOutput();
          // System.out.println(out);
           Queue q = new Queue();
           int t = in.nextInt();
           while(t-- > 0) {
               String[] inp = in.nextLine().split(" ");
               switch (inp[0]) {
                   case "+":
                       q.enQueue(Integer.parseInt(inp[1]));
                       break;
                   case "-":
                       q.deQueue();
                       break;
                   case "?":
                       out.println(q.getMin());
                   default:
                       break;
               }
           }
           out.flush();
           out.close();

       } catch(IOException e){
          e.printStackTrace();
       }
    }

    static class FastScanner {
        static BufferedReader br;
        static StringTokenizer st;

        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDoulbe() {
            return Double.parseDouble(next());
        }
    }

    static FastScanner newInput() throws IOException {
        if (System.getProperty("JUDGE") != null) {
            return new FastScanner(new File("input.txt"));
        } else {
            return new FastScanner(System.in);
        }
    }
    static PrintWriter newOutput() throws IOException {
        if (System.getProperty("JUDGE") != null) {
            return new PrintWriter("output.txt");
        } else {
            return new PrintWriter(System.out);
        }
    }
}

Ответ 12

Реализация JavaScript

(Подтвердите решение adamax для этой идеи, я свободно основал на ней реализацию). Перейдите в конец, чтобы увидеть полностью прокомментированный код или прочитайте общие шаги ниже. Обратите внимание, что это находит максимальное значение в O (1) постоянном времени, а не минимальное значение --easy для изменения):

Общая идея состоит в том, чтобы создать два стека при построении MaxQueue (я использовал связанный список в качестве базовой структуры данных Stack - не включен в код, но любой Stack будет делать, пока он реализован с помощью O (1) вставки/удаление). Один мы в основном pop из (dqStack) и один мы в основном push на (eqStack).

В случае enqueue, если MaxQueue пуст, мы будем push значение в dqStack вместе с текущим максимальным значением в кортеже (то же самое значение, поскольку это единственное значение в MaxQueue); например:

const m = new MaxQueue();

m.enqueue(6);

/*
the dqStack now looks like:
[6, 6] - [value, max]
*/

Если MaxQueue не пуст, мы push только значение eqStack;

m.enqueue(7);
m.enqueue(8);

/*
dqStack:         eqStack: 8
         [6, 6]           7 - just the value
*/

затем обновите максимальное значение в кортеже.

/*
dqStack:         eqStack: 8
         [6, 8]           7
*/

Для dequeue мы pop из dqStack и возвращает значение из кортежа.

m.dequeue();
> 6

// equivalent to:
/*
const tuple = m.dqStack.pop() // [6, 8]
tuple[0];
> 6
*/

Затем, если dqStack пуст, переместите все значения в eqStack в dqStack, например:

// if we build a MaxQueue
const maxQ = new MaxQueue(3, 5, 2, 4, 1);

/*
the stacks will look like:

dqStack:         eqStack: 1
                          4
                          2
         [3, 5]           5
*/

По мере перемещения каждого значения мы проверим, будет ли оно больше max до сих пор и сохраните его в каждом кортеже:

maxQ.dequeue(); // pops from dqStack (now empty), so move all from eqStack to dqStack
> 3

// as dequeue moves one value over, it checks if it greater than the ***previous max*** and stores the max at tuple[1], i.e., [data, max]:
/*
dqStack: [5, 5] => 5 > 4 - update                          eqStack:
         [2, 4] => 2 < 4 - no update                         
         [4, 4] => 4 > 1 - update                            
         [1, 1] => 1st value moved over so max is itself            empty
*/

Поскольку каждое значение переносится в dqStack не более одного раза, можно сказать, что у dequeue есть O (1) амортизированная временная сложность.

Затем в любой момент времени мы можем вызвать getMax для получения текущего максимального значения в O (1) постоянном времени. Пока MaxQueue не пуст, максимальное значение легко вытягивается из следующего кортежа в dqStack.

maxQ.getMax();
> 5

// equivalent to calling peek on the dqStack and pulling out the maximum value:
/*
const peekedTuple = maxQ.dqStack.peek(); // [5, 5]
peekedTuple[1];
> 5
*/

Код

class MaxQueue {
  constructor(...data) {
    // create a dequeue Stack from which we'll pop
    this.dqStack = new Stack();
    // create an enqueue Stack to which we'll push
    this.eqStack = new Stack();
    // if enqueueing data at construction, iterate through data and enqueue each
    if (data.length) for (const datum of data) this.enqueue(datum);
  }
  enqueue(data) { // O(1) constant insertion time
    // if the MaxQueue is empty,
    if (!this.peek()) {
      // push data to the dequeue Stack and indicate it the max;
      this.dqStack.push([data, data]); // e.g., enqueue(8) ==> [data: 8, max: 8]
    } else {
      // otherwise, the MaxQueue is not empty; push data to enqueue Stack
      this.eqStack.push(data);
      // save a reference to the tuple that next in line to be dequeued
      const next = this.dqStack.peek();
      // if the enqueueing data is > the max in that tuple, update it
      if (data > next[1]) next[1] = data;
    }
  }
  moveAllFromEqToDq() { // O(1) amortized as each value will move at most once
    // start max at -Infinity for comparison with the first value
    let max = -Infinity;
    // until enqueue Stack is empty,
    while (this.eqStack.peek()) {
      // pop from enqueue Stack and save its data
      const data = this.eqStack.pop();
      // if data is > max, set max to data
      if (data > max) max = data;
      // push to dequeue Stack and indicate the current max; e.g., [data: 7: max: 8]
      this.dqStack.push([data, max]);
    }
  }
  dequeue() { // O(1) amortized deletion due to calling moveAllFromEqToDq from time-to-time
    // if the MaxQueue is empty, return undefined
    if (!this.peek()) return;
    // pop from the dequeue Stack and save it data
    const [data] = this.dqStack.pop();
    // if there no data left in dequeue Stack, move all data from enqueue Stack
    if (!this.dqStack.peek()) this.moveAllFromEqToDq();
    // return the data
    return data;
  }
  peek() { // O(1) constant peek time
    // if the MaxQueue is empty, return undefined
    if (!this.dqStack.peek()) return;
    // peek at dequeue Stack and return its data
    return this.dqStack.peek()[0];
  }
  getMax() { // O(1) constant time to find maximum value
    // if the MaxQueue is empty, return undefined
    if (!this.peek()) return;
    // peek at dequeue Stack and return the current max
    return this.dqStack.peek()[1];
  }
}