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

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

       1
     /   \
    2      3
          / \
         4   5

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

       1
     /   \
    2      2
          /
         3
        / \
       4   5

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

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

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

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

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

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

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

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

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

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

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();
    }
}

объяснение:

пример давайте подтолкнем числа [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. :)

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

когда x поставлен в очередь, push_back его в A и держать 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])

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

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

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

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

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

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

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

class LinkedListElement
{
   LinkedListElement next;
   int currentMin;
}

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

Если вы добавляете элемент в начало очереди. Проверьте начальный указатель и узел для вставки. Если узел для вставки currentmin меньше, чем start currentmin узел для вставки currentmin является минимальным. Иначе обновите currentmin с помощью start currentmin.

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

#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;
}

это решение содержит 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

Реализация 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);
        }
    }
}

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

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

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

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

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

    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;
    }

реализация JavaScript

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

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

---

вставка: O (1) худший случай

на enqueue, если MaxQueue пусто, мы будем push значение dqStack вместе с текущим максимальным значением в кортежа!--36--> (то же значение, так как это единственное значение в 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
*/

---

Удаление: O (1) амортизированный

на 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's 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) амортизированной времени.

---

найти максимальное значение: 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's 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's 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's data
    const [data] = this.dqStack.pop();
    // if there's 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];
  }
}