OK - myślę, że mam odpowiedź, która daje Ci wszystkie te operacje w O(1), co oznacza, że każda jedna operacja może zająć do O(n), ale każda sekwencja N operacji zajmuje o(1) Czas na operację .

Chodzi o przechowywanie danych jako drzewo kartezjańskie. Jest to drzewo binarne zgodne z właściwością min-heap (każdy węzeł nie jest większy niż jego dzieci) i jest uporządkowane w taki sposób, że przesunięcie w kolejności węzłów zwraca węzły w tej samej kolejności, w jakiej zostały dodane. Na przykład, oto drzewo kartezjańskie Dla ciągu 2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

Można wstawić element do drzewa kartezjańskiego w czasie O (1), korzystając z poniższej procedury. Spójrz na prawy grzbiet drzewa (ścieżka od korzenia do najbardziej prawego liścia utworzona przez zawsze chodzenie w prawo). Zaczynając od węzła po prawej stronie, Skanuj w górę wzdłuż tej ścieżki, aż znajdziesz pierwszy węzeł mniejszy niż wstawiany.
Zmień ten węzeł tak, aby jego prawe dziecko było tym nowym węzłem, a następnie uczyń poprzednie prawe dziecko tego węzła lewym dzieckiem właśnie dodanego węzła. Załóżmy na przykład, że chcemy wstawić kolejną kopię 2 do powyższego drzewa. Wchodzimy prawym kręgosłupem obok 5 i 3, ale zatrzymujemy się poniżej 1, Ponieważ 1

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Zauważ, że przesunięcie w kolejności daje 2 1 4 3 5 2, czyli sekwencję, w której dodaliśmy wartości.

To działa w o(1), ponieważ możemy utworzyć funkcję potencjalną równą liczbie węzłów w prawym grzbiecie drzewa. Czas rzeczywisty wymagany do wstawienia węzła to 1 plus liczba węzłów w kręgosłupie, którą rozważamy (nazwijmy to k). Gdy znajdziemy miejsce do wstawienia węzła, rozmiar kręgosłupa kurczy się o długość k-1, ponieważ każdy z węzłów K, które odwiedziliśmy, nie jest już na prawym kręgosłupie, a nowy węzeł jest na jego miejscu. Daje to amortyzowany koszt 1 + k + (1 - k) = 2 = O (1), dla amortyzowany o (1) wkładka. Jako inny sposób myślenia o tym, gdy węzeł został przeniesiony z prawego kręgosłupa, nigdy nie jest częścią prawego kręgosłupa ponownie, a więc nigdy nie będziemy musieli go przenieść ponownie. Ponieważ każdy z n węzłów może być przesunięty co najwyżej raz, oznacza to, że n wstawek może wykonać co najwyżej n ruchów, więc całkowity czas działania wynosi co najwyżej O(n) dla zamortyzowanego O (1) na element.

Aby wykonać krok dequeue, po prostu usuwamy najbardziej lewy węzeł z drzewa kartezjańskiego. Jeśli ten węzeł jest liściem, skończyliśmy. W przeciwnym razie węzeł może mieć tylko jedno dziecko (prawe dziecko), więc zamieniamy węzeł na jego prawe dziecko. Pod warunkiem, że będziemy śledzić, gdzie znajduje się najbardziej lewy węzeł, ten krok zajmuje O(1) czas. Jednak po usunięciu najbardziej lewego węzła i zastąpieniu go prawym potomkiem, możemy nie wiedzieć, gdzie znajduje się nowy najbardziej lewy węzeł. Aby to naprawić, po prostu idziemy w dół lewego kręgosłupa drzewa zaczynając od nowego węzła, który właśnie przeniósł się do lewego dziecka. Twierdzę, że to wciąż trwa w O (1) zamortyzowanym czasie. Aby to zobaczyć, twierdzę, że węzeł jest odwiedzany co najwyżej raz podczas jednego z tych przejść, aby znaleźć najbardziej lewy węzeł. Aby to zobaczyć, zauważ, że gdy węzeł został odwiedzony w ten sposób, jedynym sposobem, w jaki moglibyśmy kiedykolwiek potrzebować, aby spojrzeć na niego ponownie, byłoby przeniesienie go z dziecka z lewego węzła do lewego węzła. Ale wszystkie odwiedzane węzły są rodzicami lewego węzła, więc tak się nie może stać. W związku z tym każdy węzeł jest odwiedzany co najwyżej raz w trakcie tego procesu, a pop działa w O (1).

Możemy znaleźć-min W O(1), ponieważ drzewo kartezjańskie daje nam dostęp do najmniejszego elementu drzewa za darmo; jest to korzeń drzewa.

Wreszcie, aby zobaczyć, że węzły wracają w tej samej kolejności, w jakiej zostały wstawione, zauważ, że drzewo kartezjańskie zawsze przechowuje swoje elementy tak, że przesunięcie w kolejności odwiedza je w kolejności posortowanej. Ponieważ zawsze usuwamy lewy węzeł na każdym kroku i jest to pierwszy element przejścia inorder, Zawsze dostajemy węzły z powrotem w kolejności, w jakiej zostały wstawione.

W skrócie, otrzymujemy O(1) amortyzowany push i pop, oraz o(1) najgorszy przypadek find-min.

Jeśli uda mi się wymyślić najgorszą implementację O(1), na pewno ją opublikuję. To był wielki problem; dzięki za umieszczenie go!

Ok, oto jedno rozwiązanie.

Najpierw potrzebujemy rzeczy, które zapewnią push_back (), push_front (), pop_back () i pop_front () w 0(1). Jest łatwy do zaimplementowania za pomocą tablic i 2 iteratorów. Pierwszy iterator wskaże przód, drugi do tyłu. Nazwijmy takie rzeczy deque.

Oto pseudo-kod:

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

Explanation:

Przykład wypchnijmy liczby [12,5,10,7,11,19] i do naszego MyQueue

1)pchanie 12

D [12]
Min[12]

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

3)pchanie 10

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

4)pchanie 7

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

6)pchanie 11

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

7)pchanie 19

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

Teraz wywołajmy pop_front ()

Mamy

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

Minimum to 5

Wywołajmy ponownie pop_front ()

Explanation: pop_front usunie 5 z D, ale będzie też wyskakiwał przedni element Min, ponieważ jest równy przedni element D (5).

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

A minimum to 7. :)

Użyj jednego deque (A) do przechowywania elementów, a drugiego deque (B) do przechowywania minimów.

Gdy X jest zapytane, push_back go do A i zachować pop_backing B aż tył B jest mniejszy niż x, następnie push_back x do B.

Po usunięciu a, pop_front a jako wartość zwracaną, a jeśli jest równa przodowi B, to również pop_front B.

Podczas uzyskiwania minimum A, użyj przodu B jako wartości zwracanej.

Dequeue i getmin są oczywiście O(1). Dla operacji enqueue, rozważmy push_back n elementów. Istnieje n push_back do A, n push_back do B i co najwyżej n pop_back z B, ponieważ każdy element pozostanie w B lub zostanie wyskakujący raz z B. ponad wszystkimi operacjami są o(3n) i dlatego zamortyzowany koszt to O(1), jak również dla enqueue.

Na koniec algorytm ten działa, ponieważ gdy zapytasz x Do A, jeśli w B są elementy większe niż x, nigdy nie będą one minimami, ponieważ x pozostanie w kolejce dłużej niż dowolne elementy w B (Kolejka a to FIFO). Dlatego musimy wyskakiwać elementy w B (z tyłu), które są większe niż x, zanim wepchniemy x do 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])

Jeśli nie masz nic przeciwko przechowywaniu dodatkowych danych, przechowywanie minimalnej wartości powinno być trywialne. Push i pop mogą zaktualizować wartość, jeśli nowy lub usunięty element jest minimum, a zwrócenie minimalnej wartości jest tak proste, jak uzyskanie wartości zmiennej.

Zakłada się, że get_min() nie zmienia danych; jeśli wolisz mieć coś takiego jak pop_min () (tzn. usunąć minimalny element), możesz po prostu zapisać wskaźnik do rzeczywistego elementu i elementu poprzedzającego to (jeśli istnieje), i zaktualizuj je odpowiednio za pomocą push_rear () i pop_front (), jak również.

Edit after comments:

Oczywiście prowadzi to do O (n) push i pop w przypadku, gdy minimalne zmiany w tych operacjach, a więc nie spełnia ściśle wymagań.

Rozwiązania tego pytania, w tym kod, można znaleźć tutaj: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

Możesz używać LinkedList do utrzymywania kolejki.

Każdy element w LinkedList będzie typu

class LinkedListElement
{
   LinkedListElement next;
   int currentMin;
}

Możesz mieć dwa wskaźniki, jeden wskazuje na początek, a drugi na koniec.

Jeśli dodasz element do początku kolejki. Sprawdź wskaźnik początkowy i węzeł do wstawienia. Jeśli węzeł do wstawienia currentmin jest mniejszy niż start currentmin węzeł do wstawienia currentmin jest minimum. W przeciwnym razie zaktualizuj currentmin za pomocą start currentmin.

Powtórz to samo dla 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;
}

To rozwiązanie zawiera 2 kolejki:
1. main_q-przechowuje numery wejściowe.
2. min_q-przechowuje liczby min według określonych reguł, które będziemy opisywać (pojawiają się w funkcjach MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min()).

Oto kod w Pythonie. Kolejka jest zaimplementowana przy użyciu listy.
Główna idea leży w MainQ.enqueue (x), MainQ.dequeue (), MainQ.funkcje get_min ().
Jednym z kluczowych założeń jest to, że opróżnienie kolejki zajmuje o (0).
Test jest dostępny na koniec.

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

Wynik powyższego testu to:

"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

Implementacja Javy

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

Wiemy, że push i pop są operacjami w czasie stałym [o (1), aby być precyzyjnym].

Ale kiedy myślimy o get_min () [tj. aby znaleźć bieżącą minimalną liczbę w kolejce] ogólnie pierwszą rzeczą, która przychodzi nam na myśl, jest przeszukanie całej kolejki za każdym razem, gdy żądanie minimalnego elementu jest wykonane. Ale to nigdy nie da stałej pracy czasu, który jest głównym celem problemu.

Jest to zazwyczaj zadawane bardzo często w wywiadach, więc musisz wiedzieć, że trick

Aby to zrobić musimy użyć jeszcze dwóch kolejek, które będą śledzić minimalny element i musimy dalej modyfikować te 2 kolejki, jak wykonujemy operacje push i pop na kolejce, tak aby minimalny element został uzyskany w czasie O(1).

Oto samoopisowy kod sudo oparty na wyżej wymienionym podejściu.

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

Implementacja JavaScript

(kredyt na rozwiązanie adamax za pomysł; I luźno na jej podstawie powstała implementacja. Przejdź do dołu, aby zobaczyć w pełni skomentowany kod lub przeczytaj ogólne kroki poniżej. Zauważ, że to znajduje maksymalną wartość W O (1) stałym czasie, a nie minimalną wartość --łatwo zmienić w górę):

Ogólna idea polega na stworzeniu dwóch stosów po zbudowaniu MaxQueue (Użyłem listy połączonej jako podstawowej struktury danych Stack -- nie zawartej w kodzie; ale każda Stack będzie działać tak długo, jak będzie zaimplementowana Z O(1) wstawianie/usuwanie). Jedną z nich będziemy w większości pop od (dqStack) i jedną będziemy w większości push do (eqStack).

Dla enqueue, Jeśli MaxQueue jest pusty, będziemy push wartość dqStack wraz z bieżącą wartością maksymalną w krotce (ta sama wartość od jest to jedyna wartość w MaxQueue); np.:

const m = new MaxQueue();

m.enqueue(6);

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

Jeśli MaxQueue nie jest pusta, push wystarczy wartość do eqStack;

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

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

Następnie zaktualizuj maksymalną wartość krotki.

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

Dla {[23] }będziemy pop z dqStack i zwrócimy wartość z krotki.

m.dequeue();
> 6

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

Wtedy, jeśli dqStack jest puste, Przenieś wszystkie wartości w eqStack do dqStack, np.:

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

Gdy każda wartość zostanie przesunięta, Sprawdzimy, czy jest większa niż max do tej pory i zapiszemy ją w każdej krotce:

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

Ponieważ każda wartość jest przenoszona do dqStack co najwyżej , możemy powiedzieć, że dequeue mA o(1) zamortyzowaną złożoność czasową.

Wtedy, w dowolnym momencie, możemy zadzwonić getMax aby pobrać aktualną maksymalną wartość w o (1) stałym czasie. Tak długo, jak MaxQueue nie jest pusty, maksymalna wartość jest łatwo wyciągana z następnej krotki w 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
*/

kod

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