Implemente uma fila na qual push_rear (), pop_front () e get_min () são operações de tempo constante

Eu me deparei com essa pergunta: Implemente uma fila na qual push_rear (), pop_front () e get_min () são operações de tempo constante.

Inicialmente, pensei em usar uma estrutura de dados min-heap que tivesse complexidade O (1) para um get_min (). Mas push_rear () e pop_front () seriam O (log (n)).

Alguém sabe qual seria a melhor maneira de implementar essa fila que tem O (1) push (), pop () e min ()?

Eu pesquisei sobre isso, e queria apontar este tópico do Algorithm Geeks . Mas parece que nenhuma das soluções segue regra de tempo constante para todos os 3 methods: push (), pop () e min ().

Obrigado por todas as sugestões.

Você pode implementar uma pilha com O (1) pop (), push () e get_min (): basta armazenar o mínimo atual junto com cada elemento. Assim, por exemplo, a pilha [4,2,5,1] (1 no topo) torna-se [(4,4), (2,2), (5,2), (1,1)] .

Então você pode usar duas pilhas para implementar a fila . Empurre para uma pilha, pop de outro; se a segunda pilha estiver vazia durante o pop, mova todos os elementos da primeira pilha para a segunda.

Por exemplo, para uma solicitação pop , movendo todos os elementos da primeira pilha [(4,4), (2,2), (5,2), (1,1)] , a segunda pilha seria [(1,1), (5,1), (2,1), (4,1)] . e agora retorna o elemento top da segunda pilha.

Para encontrar o elemento mínimo da fila, observe os dois elementos menores das min-stacks individuais e, em seguida, pegue o mínimo desses dois valores. (Claro, há alguma lógica extra aqui, caso uma das pilhas esteja vazia, mas isso não é muito difícil de resolver).

Terá O (1) get_min() e push() e O (1) pop() amortizado.

Ok – Eu acho que tenho uma resposta que dá a você todas essas operações em O (1) amortizado , significando que qualquer operação pode levar até O (n), mas qualquer sequência de n operações leva O (1) tempo por operação .

A ideia é armazenar seus dados como uma tree cartesiana . Esta é uma tree binária que obedece à propriedade min-heap (cada nó não é maior que seus filhos) e é ordenada de forma que uma travessia in-order dos nós forneça de volta os nós na mesma ordem em que eles foram adicionados. Por exemplo, aqui está uma tree cartesiana para a sequência 2 1 4 3 5 :

  1 / \ 2 3 / \ 4 5 

É possível inserir um elemento em uma tree cartesiana em O (1) tempo amortizado usando o seguinte procedimento. Olhe para a espinha direita da tree (o caminho da raiz até a folha mais à direita, formado sempre caminhando para a direita). Começando no nó mais à direita, faça uma varredura ascendente ao longo deste caminho até encontrar o primeiro nó menor que o nó que você está inserindo.
Altere esse nó para que seu filho direito seja esse novo nó e, em seguida, transforme o filho direito antigo desse nó no filho esquerdo do nó que você acabou de include. Por exemplo, suponha que queremos inserir outra cópia de 2 na tree acima. Andamos pela espinha direita passando pelo 5 e pelo 3, mas paramos abaixo do 1 porque 1 <2. Então, mudamos a árvore para ficar assim:

  1 / \ 2 2 / 3 / \ 4 5 

Observe que uma travessia inorder fornece 2 1 4 3 5 2, que é a sequência na qual adicionamos os valores.

Isso é executado em O (1) amortizado porque podemos criar uma function potencial igual ao número de nós na lombada direita da tree. O tempo real necessário para inserir um nó é 1 mais o número de nós na coluna que consideramos (chame isso de k). Uma vez que encontramos o lugar para inserir o nó, o tamanho da coluna encolhe pelo comprimento k – 1, uma vez que cada um dos k nós que visitamos não estão mais na espinha direita, e o novo nó está em seu lugar. Isso fornece um custo amortizado de 1 + k + (1 – k) = 2 = O (1), para a inserção O (1) amortizada. Como outra maneira de pensar sobre isso, uma vez que um nó foi removido da coluna direita, ele nunca faz parte da coluna direita novamente e, portanto, nunca mais precisaremos movê-lo novamente. Como cada um dos n nós pode ser movido no máximo uma vez, isso significa que n inserções podem fazer no máximo n movimentos, então o tempo total de execução é no máximo O (n) para um O (1) amortizado por elemento.

Para fazer uma etapa de desenfileiramento, simplesmente removemos o nó mais à esquerda da tree cartesiana. Se esse nó for uma folha, terminamos. Caso contrário, o nó só pode ter um filho (o filho certo) e, portanto, substituímos o nó por seu filho direito. Desde que possamos rastrear onde o nó mais à esquerda está, essa etapa leva o tempo O (1). No entanto, após remover o nó mais à esquerda e substituí-lo por seu filho direito, talvez não saibamos onde está o novo nó mais à esquerda. Para consertar isso, simplesmente andamos pela espinha esquerda da tree, começando no novo nó que acabamos de mover para o filho mais à esquerda. Eu afirmo que isso ainda funciona no tempo O (1) amortizado. Para ver isso, eu afirmo que um nó é visitado no máximo uma vez durante qualquer um desses passos para encontrar o nó mais à esquerda. Para ver isso, observe que, uma vez que um nó tenha sido visitado dessa maneira, a única maneira de podermos analisá-lo novamente seria se ele fosse movido de um filho do nó mais à esquerda para o nó mais à esquerda. Mas todos os nós visitados são pais do nó mais à esquerda, então isso não pode acontecer. Conseqüentemente, cada nó é visitado no máximo uma vez durante esse processo, e o pop é executado em O (1).

Nós podemos fazer find-min em O (1) porque a tree cartesiana nos dá access ao menor elemento da tree de graça; é a raiz da tree.

Finalmente, para ver que os nós retornam na mesma ordem em que foram inseridos, observe que uma tree cartesiana sempre armazena seus elementos de modo que uma passagem in-line os visite na ordem de sorting. Como sempre removemos o nó mais à esquerda em cada etapa, e este é o primeiro elemento do percurso interno, sempre obtemos os nós de volta na ordem em que foram inseridos.

Em resumo, obtemos O (1) push e pop amortizados, e O (1) o pior caso find-min.

Se eu puder chegar a uma implementação O (1) do pior caso, eu definitivamente postarei. Este foi um grande problema; obrigado por postar!

Ok, aqui está uma solução.

Primeiro precisamos de algumas coisas que fornecem push_back (), push_front (), pop_back () e pop_front () em 0 (1). É fácil implementar com array e 2 iteradores. Primeiro iterador apontará para frente, segundo para trás. Vamos chamar essas coisas deque.

Aqui está o pseudo-código:

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

Explicação:

Exemplo, vamos empurrar números [12,5,10,7,11,19] e para o nosso MyQueue

1) empurrando 12

 D [12] Min[12] 

2) empurrando 5

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

3) empurrando 10

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

4) empurrando 7

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

6) empurrando 11

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

7) empurrando 19

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

Agora vamos chamar pop_front ()

obtemos

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

O mínimo é 5

Vamos chamar pop_front () novamente

Explicação: pop_front irá remover 5 de D, mas também irá aparecer o elemento frontal de Min, porque é igual ao elemento frontal de D (5).

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

E o mínimo é 7. 🙂

Use um deque (A) para armazenar os elementos e outro deque (B) para armazenar os mínimos.

Quando x é enfileirado, push_back para A e mantém o pop_backing B até que a parte de trás de B seja menor que x, então push_back x para B.

ao remover a linha A, pop_front A como valor de retorno, e se for igual à frente de B, pop_front B também.

ao obter o mínimo de A, use a frente de B como valor de retorno.

Dequeue e getmin são obviamente O (1). Para a operação de enfileiramento, considere o push_back de n elementos. Há n push_back para A, n push_back para B e no máximo n pop_back de B porque cada elemento permanecerá em B ou será retirado uma vez de B. No geral, existem operações O (3n) e, portanto, o custo amortizado é O (1) também para o enfileiramento.

Por fim, o motivo pelo qual esse algoritmo funciona é que quando você enfileira x em A, se houver elementos em B maiores que x, eles nunca serão mínimos agora, porque x permanecerá na fila A mais que qualquer elemento em B (uma fila é FIFO). Portanto, precisamos destacar elementos em B (de trás) maiores que x antes de empurrarmos x para 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]) 

Se você não se importa em armazenar um pouco de dados extras, deve ser trivial armazenar o valor mínimo. Push e pop podem atualizar o valor se o elemento novo ou removido for o mínimo e retornar o valor mínimo é tão simples quanto obter o valor da variável.

Isso está assumindo que get_min () não altera os dados; Se você preferir ter algo como pop_min () (ou seja, remover o elemento mínimo), você pode simplesmente armazenar um ponteiro para o elemento real e o elemento anterior (se houver) e atualizá-los de acordo com push_rear () e pop_front () também.

Editar após comentários:

Obviamente, isso leva a O (n) push e pop no caso em que as mudanças mínimas nessas operações, e por isso não satisfazem estritamente os requisitos.

Soluções para esta questão, incluindo código, podem ser encontradas aqui: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

Você pode realmente usar um LinkedList para manter a fila.

Cada elemento no LinkedList será do tipo

 class LinkedListElement { LinkedListElement next; int currentMin; } 

Você pode ter dois pointers Um aponta para o início e o outro aponta para o fim.

Se você adicionar um elemento ao início da fila. Examine o ponteiro Iniciar e o nó a ser inserido. Se o nó para inserir currentmin for menor que o nó startmin atual para inserir currentmin é o mínimo. Ou então atualize o currentmin com start currentmin.

Repita o mesmo para enque.

 #include  #include  #include  using namespace std; queue main_queue; deque min_queue; void clearQueue(deque &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< 

Esta solução contém 2 filas:
1. main_q – armazena os números de input.
2. min_q – armazena os números mínimos por certas regras que descreveremos (aparecem nas funções MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ()).

Aqui está o código em Python. A fila é implementada usando uma lista.
A idéia principal está nas funções MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ().
Uma suposição chave é que o esvaziamento de uma fila leva o (0).
Um teste é fornecido no final.

 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)) 

A saída do teste acima é:

 "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 

Implementação Java

 import java.io.*; import java.util.*; public class queueMin { static class stack { private Node head; public void push(int data) { Node newNode = new Node(data); if(null == head) { head = newNode; } else { Node 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 { private T data; private T min; private Node next; public Node(T data){ this.data = data; this.next = null; } public void setNext(Node next){ this.next = next; } public T getData(){ return this.data; } public Node 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); } } } 

Sabemos que push e pop são operações de tempo constante [O (1) para ser preciso].

Mas quando pensamos em get_min () [ie para encontrar o número mínimo atual na fila] geralmente a primeira coisa que vem à mente é pesquisar toda a fila toda vez que a solicitação para o elemento mínimo é feita. Mas isso nunca dará a operação do tempo constante, que é o objective principal do problema.

Isso geralmente é feito com muita frequência nas entrevistas, então você deve conhecer o truque

Para fazer isso, temos que usar mais duas filas que manterão o rastreio do elemento mínimo e teremos que modificar essas duas filas à medida que fizermos operações push e pop na fila, de modo que o elemento mínimo seja obtido no tempo O (1). .

Aqui está o código sudo auto-descritivo baseado na abordagem acima mencionada.

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

Implementação JavaScript

( Acredito na solução da adamax para a ideia; Baseei uma implementação na mesma. Salte para a parte inferior para ver o código totalmente comentado ou leia as etapas gerais abaixo. Observe que ele encontra o valor máximo em tempo constante O (1) o valor mínimo – fácil de mudar):

A idéia geral é criar dois Stacks na construção do MaxQueue (usei uma linked list como a estrutura de dados do Stack subjacente – não incluída no código; mas qualquer Stack fará o tempo que for implementado com inserção de O (1) / eliminação). Nós vamos principalmente pop de ( dqStack ) e um nós vamos principalmente push para ( eqStack ).


Inserção: O (1) pior caso

Para enqueue , se o MaxQueue estiver vazio, enviaremos o valor para dqStack junto com o valor máximo atual em uma tupla (o mesmo valor, já que é o único valor no MaxQueue ); por exemplo:

 const m = new MaxQueue(); m.enqueue(6); /* the dqStack now looks like: [6, 6] - [value, max] */ 

Se o MaxQueue não estiver vazio, eqStack apenas o valor para eqStack ;

 m.enqueue(7); m.enqueue(8); /* dqStack: eqStack: 8 [6, 6] 7 - just the value */ 

em seguida, atualize o valor máximo na tupla.

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

Exclusão: O (1) amortizado

Para o dequeue , vamos pop partir do dqStack e retornar o valor da tupla.

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

Então, se dqStack estiver vazio, mova todos os valores em eqStack para dqStack , por exemplo:

 // 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 */ 

À medida que cada valor é movido, verificaremos se ele é maior que o máximo até o momento e o armazenaremos em cada tupla:

 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], ie, [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 */ 

Como cada valor é movido para dqStack no máximo uma vez , podemos dizer que o dequeue tem O (1) complexidade de tempo amortizado.


Encontrando o valor máximo: O (1) pior caso

Então, a qualquer momento, podemos chamar getMax para recuperar o valor máximo atual no tempo constante O (1). Contanto que o MaxQueue não esteja vazio, o valor máximo é facilmente retirado da próxima tupla no 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 */ 

Código

 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]); // eg, 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; eg, [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]; } }