Implémenter une queue dans laquelle push_rear (), pop_front () et get_min () sont toutes des opérations à heure constante

Je suis tombé sur cette question: implémenter une queue dans laquelle push_rear (), pop_front () et get_min () sont tous des opérations à heure constante.

J’ai initialement pensé à utiliser une structure de données min-heap qui présente une complexité O (1) pour un get_min (). Mais push_rear () et pop_front () seraient O (log (n)).

Est-ce que quelqu’un sait quel serait le meilleur moyen d’implémenter une telle queue qui a O (1) push (), pop () et min ()?

J’ai cherché sur Google à ce sujet et je voulais souligner ce fil de l’algorithme Geeks . Mais il semble qu’aucune des solutions ne respecte la règle du temps constant pour les trois méthodes: push (), pop () et min ().

Merci pour toutes les suggestions.

Vous pouvez implémenter une stack avec O (1) pop (), push () et get_min (): stockez simplement le minimum actuel avec chaque élément. Ainsi, par exemple, la stack [4,2,5,1] (1 en haut) devient [(4,4), (2,2), (5,2), (1,1)] .

Vous pouvez ensuite utiliser deux stacks pour implémenter la queue . Poussez sur une stack, faites-en un autre; Si la deuxième stack est vide pendant le pop, déplacez tous les éléments de la première stack vers la seconde.

Par exemple, pour une requête pop , déplacer tous les éléments de la première stack [(4,4), (2,2), (5,2), (1,1)] , la deuxième stack serait [(1,1), (5,1), (2,1), (4,1)] . et maintenant retourner l’élément supérieur de la deuxième stack.

Pour trouver l’élément minimum de la queue, examinez les deux plus petits éléments des min-stacks individuelles, puis prenez le minimum de ces deux valeurs. (Bien sûr, il y a de la logique supplémentaire dans le cas où l’une des stacks est vide, mais ce n’est pas trop difficile à contourner).

Il aura O (1) get_min() et push() et O (1) pop() .

Okay – Je pense que j’ai une réponse qui vous donne toutes ces opérations dans O (1) amorti , ce qui signifie que toute opération peut prendre jusqu’à O (n), mais toute séquence de n opérations prend O (1) temps par opération .

L’idée est de stocker vos données sous la forme d’un arbre cartésien . Il s’agit d’un arbre binary qui obéit à la propriété min-heap (chaque nœud n’est pas plus grand que ses enfants) et est ordonné de manière à ce que le parcours des nœuds vous renvoie les nœuds dans l’ordre où ils ont été ajoutés. Par exemple, voici un arbre cartésien pour la séquence 2 1 4 3 5 :

  1 / \ 2 3 / \ 4 5 

Il est possible d’insérer un élément dans un arbre cartésien en O (1) temps amorti en utilisant la procédure suivante. Regardez la colonne vertébrale droite de l’arbre (le chemin de la racine à la feuille la plus à droite formé en marchant toujours vers la droite). À partir du nœud le plus à droite, parcourez ce chemin jusqu’à ce que vous trouviez le premier nœud plus petit que le nœud que vous insérez.
Modifiez ce noeud pour que son enfant droit soit ce nouveau noeud, puis faites de l’ancien enfant droit de ce noeud l’enfant gauche du noeud que vous venez d’append. Par exemple, supposons que nous voulions insérer une autre copie de 2 dans l’arbre ci-dessus. Nous remontons la colonne vertébrale droite après le 5 et le 3, mais nous nous arrêtons sous le 1 parce que 1 <2. Nous changeons ensuite l'arbre pour ressembler à ceci:

  1 / \ 2 2 / 3 / \ 4 5 

Notez qu’une traversée dans l’ordre donne 2 1 4 3 5 2, qui est la séquence dans laquelle nous avons ajouté les valeurs.

Cela s’exécute en O (1) amorti car nous pouvons créer une fonction potentielle égale au nombre de nœuds dans la colonne vertébrale droite de l’arbre. Le temps réel requirejs pour insérer un nœud est 1 plus le nombre de nœuds dans la colonne vertébrale que nous considérons (appelez ceci k). Une fois que nous avons trouvé la place pour insérer le nœud, la taille de la colonne diminue de longueur k-1, puisque chacun des k nœuds que nous avons visités ne se trouve plus sur la colonne vertébrale et que le nouveau nœud est à sa place. Cela donne un coût amorti de 1 + k + (1 – k) = 2 = O (1) pour l’insert O (1) amorti. Une autre façon de penser à cela, une fois qu’un nœud a été déplacé de la colonne vertébrale droite, ne fait plus jamais partie de la colonne vertébrale droite, et nous n’aurons donc plus jamais à le déplacer. Comme chacun des n nœuds peut être déplacé au maximum une fois, cela signifie que n insertions peuvent effectuer au plus n mouvements, donc le temps d’exécution total est au maximum O (n) pour un O (1) amorti par élément.

Pour faire une étape de dé-file, il suffit de supprimer le nœud le plus à gauche de l’arbre cartésien. Si ce nœud est une feuille, nous avons terminé. Sinon, le nœud ne peut avoir qu’un seul enfant (le bon enfant) et nous remplaçons donc le nœud par son enfant droit. À condition que nous gardions une trace de l’emplacement du nœud le plus à gauche, cette étape prend O (1) heure. Cependant, après avoir supprimé le nœud le plus à gauche et l’avoir remplacé par son fils droit, il se peut que nous ne sachions pas où se trouve le nouveau nœud le plus à gauche. Pour résoudre ce problème, nous descendons simplement la colonne vertébrale gauche de l’arbre en commençant par le nouveau nœud que nous venons de déplacer vers l’enfant le plus à gauche. Je prétends que cela fonctionne toujours dans O (1) temps amorti. Pour voir cela, je prétends qu’un nœud est visité au plus une fois au cours de l’une de ces passes pour trouver le nœud le plus à gauche. Pour le voir, notez qu’une fois qu’un nœud a été visité de cette manière, la seule façon dont nous pourrions avoir à le revoir serait de le déplacer d’un enfant du nœud le plus à gauche au nœud le plus à gauche. Mais tous les nœuds visités sont les parents du nœud le plus à gauche, donc cela ne peut pas arriver. Par conséquent, chaque nœud est visité au plus une fois au cours de ce processus, et la pop s’exécute dans O (1).

On peut faire find-min dans O (1) car l’arbre cartésien nous donne access au plus petit élément de l’arbre gratuitement; c’est la racine de l’arbre.

Enfin, pour voir que les nœuds reviennent dans l’ordre dans lequel ils ont été insérés, notez qu’un arbre cartésien stocke toujours ses éléments pour qu’une traversée de commande les visite dans l’ordre sortingé. Puisque nous supprimons toujours le nœud le plus à gauche à chaque étape, et qu’il s’agit du premier élément de la traversée de commande, nous récupérons toujours les nœuds dans l’ordre dans lequel ils ont été insérés.

En bref, nous obtenons O (1) push and pop amorti, et O (1) find-min le pire des cas.

Si je peux arriver à une implémentation du pire O (1), je la posterai définitivement. C’était un gros problème; Merci de l’avoir posté!

Ok, voici une solution.

D’abord, nous avons besoin de quelques éléments fournissant push_back (), push_front (), pop_back () et pop_front () dans 0 (1). Il est facile à mettre en œuvre avec un tableau et 2 iterators. Le premier iterator se dirigera vers l’avant et le second vers l’arrière. Appelons ce genre de choses deque.

Voici un pseudo-code:

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

Explication:

Exemple, poussez les nombres [12,5,10,7,11,19] et vers notre MyQueue

1) en poussant 12

 D [12] Min[12] 

2) en poussant 5

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

3) en poussant 10

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

4) en poussant 7

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

6) en poussant 11

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

7) en poussant 19

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

Appelons maintenant pop_front ()

nous avons

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

Le minimum est de 5

Appelons à nouveau pop_front ()

Explication: pop_front supprime 5 de D, mais l’élément frontal de Min apparaît également, car il est égal à l’élément avant de D (5).

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

Et le minimum est 7. 🙂

Utilisez un deque (A) pour stocker les éléments et un autre deque (B) pour stocker les minimums.

Lorsque x est mis en queue, relancez-le en A et maintenez pop_backing B jusqu’à ce que l’arrière de B soit inférieur à x, puis push_back x à B.

lors de la mise en queue de A, pop_front A comme valeur de retour, et s’il est égal à l’avant de B, pop_front B également.

Lorsque vous obtenez le minimum de A, utilisez le recto de B comme valeur de retour.

dequeue et getmin sont évidemment O (1). Pour l’opération de mise en queue, considérez le push_back de n éléments. Il y a n push_back à A, n push_back à B et au plus n pop_back de B parce que chaque élément restra dans B ou sera sorti une fois de B. Sur toutes les opérations, il y a O (3n) et donc le coût amorti est O (1) également pour la mise en queue.

Enfin, la raison pour laquelle cet algorithme fonctionne est que lorsque vous mettez en queue x à A, s’il y a des éléments dans B qui sont plus grands que x, ils ne seront jamais minimaux car x restra dans la file est FIFO). Par conséquent, nous devons extraire les éléments de B (à l’arrière) qui sont plus grands que x avant de pousser x dans 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]) 

Si cela ne vous dérange pas de stocker un peu de données supplémentaires, il devrait être sortingvial de stocker la valeur minimale. Push et pop peuvent mettre à jour la valeur si l’élément nouveau ou supprimé est le minimum, et le retour de la valeur minimale est aussi simple que d’obtenir la valeur de la variable.

Cela suppose que get_min () ne modifie pas les données; Si vous préférez avoir quelque chose comme pop_min () (c.-à-d. supprimer l’élément minimum), vous pouvez simplement stocker un pointeur sur l’élément actuel et l’élément qui le précède, et les mettre à jour avec push_rear () et pop_front () ainsi que.

Modifier après les commentaires:

Evidemment, cela conduit à O (n) push et pop dans le cas où le minimum change sur ces opérations, et donc ne satisfait pas ssortingctement les exigences.

Des solutions à cette question, y compris le code, peuvent être trouvées ici: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

Vous pouvez réellement utiliser une LinkedList pour maintenir la queue.

Chaque élément de LinkedList sera de type

 class LinkedListElement { LinkedListElement next; int currentMin; } 

Vous pouvez avoir deux pointeurs Un pointe vers le début et les autres points vers la fin.

Si vous ajoutez un élément au début de la queue. Examinez le pointeur de démarrage et le nœud à insérer. Si le nœud à insérer currentmin est inférieur au nœud startminmin pour insérer currentmin est le minimum. Sinon, mettez à jour le currentmin avec start currentmin.

Répétez la même chose pour 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< 

Cette solution contient 2 files d’attente:
1. main_q – stocke les numéros d’entrée.
2. min_q – stocke les nombres min par certaines règles que nous allons décrire (apparaissent dans les fonctions MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ()).

Voici le code en Python. La queue est implémentée à l’aide d’une liste.
L’idée principale réside dans les fonctions MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ().
Une hypothèse clé est que vider une queue prend o (0).
Un test est fourni à la fin.

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

Le résultat du test ci-dessus est:

 "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 

Implémentation 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(Ssortingng args[]){ try { FastScanner in = newInput(); PrintWriter out = newOutput(); // System.out.println(out); Queue q = new Queue(); int t = in.nextInt(); while(t-- > 0) { Ssortingng[] 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 SsortingngTokenizer 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)); } Ssortingng next() { while (st == null || !st.hasMoreTokens()) { try { st = new SsortingngTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } Ssortingng nextLine(){ Ssortingng 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); } } } 

Nous soaps que push et pop sont des opérations à temps constant [O (1) pour être précis].

Mais quand on pense à get_min () [c.-à-d. Trouver le nombre minimum actuel dans la queue] généralement la première chose qui vient à l’esprit est de chercher dans toute la queue chaque fois que la demande de l’élément minimum est faite. Mais cela ne donnera jamais l’opération à temps constant, qui est l’objective principal du problème.

Ceci est généralement demandé très fréquemment dans les interviews, vous devez donc connaître le tour

Pour ce faire, nous devons utiliser deux autres files d’attente qui conserveront la trace de l’élément minimum et nous devons continuer à modifier ces 2 files d’attente pendant que nous effectuons des opérations de push et pop sur la queue afin d’obtenir un minimum dans O (1) .

Voici le code sudo auto-descriptif basé sur l’approche ci-dessus mentionnée.

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

Implémentation JavaScript

(Crédit à la solution adamax pour cette idée; je basais une implémentation sur celle-ci. Allez au bas pour voir le code entièrement commenté ou lisez les étapes générales ci-dessous. Notez que cela trouve la valeur maximale dans O (1) la valeur minimale – facile à changer

L’idée générale est de créer deux Stacks lors de la construction de la MaxQueue (j’ai utilisé une liste chaînée comme structure de données Stack sous-jacente – non incluse dans le code; mais toute Stack fera aussi longtemps que l’insertion O (1) / effacement). Il y en aura principalement un ( dqStack ) et un autre que nous enverrons principalement ( eqStack ).


Insertion: O (1) pire des cas

Pour la mise en enqueue , si la MaxQueue est vide, nous allons push la valeur dans dqStack avec la valeur max actuelle dans un tuple (la même valeur car c’est la seule valeur dans la MaxQueue ); par exemple:

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

Si la MaxQueue n’est pas vide, nous ne mettons que la valeur dans eqStack ;

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

ensuite, mettez à jour la valeur maximale dans le tuple.

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

Suppression: O (1) amorti

Pour dequeue nous allons dqStack de dqStack et renvoyer la valeur du tuple.

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

Ensuite, si dqStack est vide, déplacez toutes les valeurs dans eqStack vers dqStack , par exemple:

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

Au fur et à mesure que chaque valeur est déplacée, nous vérifions si elle est supérieure à la valeur maximale et la stockons dans chaque tuple:

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

Étant donné que chaque valeur est déplacée au maximum une fois dans dqStack , nous pouvons dire que la dequeue a une complexité temporelle amortie O (1).


Trouver la valeur maximale: O (1) pire des cas

Ensuite, à tout moment, nous pouvons appeler getMax pour récupérer la valeur maximale actuelle dans O (1) temps constant. Tant que la MaxQueue n’est pas vide, la valeur maximale est facilement extraite du prochain dqStack dans 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 */ 

Code

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