wake-up-neo.com

Implementieren Sie eine Warteschlange, in der Push_rear (), pop_front () und get_min () alle Operationen mit konstanter Zeit sind

Ich bin auf diese Frage gestoßen: Implementiere eine Warteschlange, in der Push_rear (), pop_front () und get_min () alle konstanten Zeitoperationen sind.

Anfangs dachte ich daran, eine Min-Heap-Datenstruktur zu verwenden, die O(1) Komplexität für ein get_min () hat. Push_rear () und pop_front () wären jedoch O (log (n)).

Weiß jemand, was der beste Weg ist, eine solche Warteschlange zu implementieren, die O(1) Push (), Pop () und Min () hat?

Ich googelte darüber und wollte auf diesen Algorithmus Geeks Thread hinweisen. Es scheint jedoch, dass keine der Lösungen einer konstanten Zeitregel für alle 3 Methoden folgt: Push (), Pop () und Min ().

Danke für alle Vorschläge.

72
bits

Sie können einen Stack mit O(1) pop (), Push () und get_min () implementieren: Speichern Sie einfach das aktuelle Minimum zusammen mit jedem Element. So wird beispielsweise der Stack [4,2,5,1] (1 oben) zu [(4,4), (2,2), (5,2), (1,1)].

Dann können Sie zwei Stacks verwenden, um die Warteschlange zu implementieren . Schiebe auf einen Stapel, springe von einem anderen; Wenn der zweite Stapel während des Pops leer ist, verschieben Sie alle Elemente vom ersten Stapel in den zweiten.

Zum Beispiel für eine pop-Anforderung, die alle Elemente aus dem ersten Stapel [(4,4), (2,2), (5,2), (1,1)] bewegt, wäre der zweite Stapel [(1,1), (5,1), (2,1), (4,1)]. und kehre nun das oberste Element vom zweiten Stapel zurück.

Um das minimale Element der Warteschlange zu ermitteln, betrachten Sie die kleinsten zwei Elemente der einzelnen Min-Stapel und nehmen Sie dann das Minimum dieser beiden Werte. (Natürlich gibt es eine zusätzliche Logik, wenn einer der Stapel leer ist, aber das ist nicht zu schwer umzugehen).

Es wird O(1) get_min() und Push() haben und O(1) pop() amortisiert werden. 

91
adamax

Okay - ich glaube, ich habe eine Antwort, die Ihnen alle diese Operationen in amortisierten O (1) gibt, was bedeutet, dass jede Operation bis zu O dauern könnte (n), aber jede Folge von n Operationen benötigt O(1) Zeit pro Operation .

Die Idee ist, Ihre Daten als kartesischer Baum zu speichern. Dies ist ein Binärbaum, der der Eigenschaft min-heap folgt (jeder Knoten ist nicht größer als seine untergeordneten Knoten) und so angeordnet ist, dass Sie bei einem Inorder Traversal der Knoten die Knoten in der Reihenfolge zurückerhalten, in der sie hinzugefügt wurden. Hier ist zum Beispiel ein kartesischer Baum für die Sequenz 2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

Es ist möglich, ein Element in O(1) amortisierter Zeit in einen kartesischen Baum einzufügen. Schauen Sie sich den rechten Rücken des Baumes an (den Weg von der Wurzel bis zum äußersten rechten Blatt, der entsteht, wenn Sie immer nach rechts gehen). Beginnen Sie am rechten Knoten und scannen Sie auf diesem Pfad nach oben, bis Sie den ersten Knoten finden, der kleiner ist als der Knoten, den Sie einfügen.
Ändern Sie diesen Knoten so, dass sein rechtes Kind dieser neue Knoten ist, und machen Sie dann das frühere rechte Kind dieses Knotens zum linken Kind des soeben hinzugefügten Knotens. Angenommen, wir möchten eine weitere Kopie von 2 in den obigen Baum einfügen. Wir gehen den rechten Rücken entlang, vorbei an der 5 und der 3, halten aber unterhalb der 1, weil 1 <2. Wir ändern dann den Baum so, dass er so aussieht:

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Beachten Sie, dass ein Inorder Traversal 2 1 4 3 5 2 ergibt. In dieser Reihenfolge haben wir die Werte hinzugefügt.

Dies wird amortisiert O(1) ausgeführt, da wir eine potenzielle Funktion erstellen können, die der Anzahl der Knoten auf der rechten Seite des Baums entspricht. Die zum Einfügen eines Knotens erforderliche Echtzeit ist 1 plus die Anzahl der Knoten in der Wirbelsäule, die wir berücksichtigen (nennen Sie dies k). Sobald wir den Platz zum Einfügen des Knotens gefunden haben, verringert sich die Größe der Wirbelsäule um die Länge k - 1, da sich nicht mehr jeder der von uns besuchten k Knoten auf der rechten Wirbelsäule befindet und der neue Knoten an seiner Stelle ist. Dies ergibt abgeschriebene Anschaffungskosten von 1 + k + (1 - k) = 2 = O (1) für das abgeschriebene Insert O(1). Wenn ein Knoten von der rechten Wirbelsäule entfernt wurde, ist er nie mehr Teil der rechten Wirbelsäule, sodass wir ihn nie mehr verschieben müssen. Da jeder der n Knoten höchstens einmal verschoben werden kann, bedeutet dies, dass n Einfügungen höchstens n Bewegungen ausführen können, sodass die Gesamtlaufzeit für eine amortisierte O(n) höchstens O(1) pro Element.

Um einen Schritt zum Entfernen der Warteschlange durchzuführen, entfernen wir einfach den Knoten ganz links aus dem kartesischen Baum. Wenn dieser Knoten ein Blatt ist, sind wir fertig. Andernfalls kann der Knoten nur ein untergeordnetes Element (das richtige untergeordnete Element) haben. Daher ersetzen wir den Knoten durch das richtige untergeordnete Element. Vorausgesetzt, wir verfolgen, wo sich der Knoten ganz links befindet, dauert dieser Schritt O(1). Nach dem Entfernen des Knotens ganz links und dem Ersetzen durch den untergeordneten Knoten ganz rechts wissen wir möglicherweise nicht, wo sich der neue Knoten ganz links befindet. Um dies zu beheben, gehen wir einfach den linken Rücken des Baums entlang, beginnend mit dem neuen Knoten, den wir gerade zum Kind ganz links verschoben haben. Ich behaupte, dass dies noch in O(1) amortisierter Zeit läuft. Um dies zu sehen, behaupte ich, dass ein Knoten während eines dieser Durchgänge höchstens einmal besucht wird, um den am weitesten links liegenden Knoten zu finden. Um dies zu sehen, ist zu beachten, dass, sobald ein Knoten auf diese Weise besucht wurde, der einzige Weg, den wir jemals brauchen könnten, um ihn erneut zu betrachten, wäre, wenn er von einem untergeordneten Knoten des ganz linken Knotens auf den ganz linken Knoten verschoben würde. Alle besuchten Knoten sind jedoch Eltern des Knotens ganz links, sodass dies nicht passieren kann. Folglich wird jeder Knoten während dieses Vorgangs höchstens einmal besucht, und der Popup wird in O (1) ausgeführt.

Wir können find-min in O(1) ausführen, weil der kartesische Baum uns freien Zugriff auf das kleinste Element des Baums gewährt. Es ist die Wurzel des Baumes.

Beachten Sie, dass ein kartesischer Baum seine Elemente immer so speichert, dass ein Inorder Traversal sie in sortierter Reihenfolge aufruft, um sicherzustellen, dass die Knoten in der gleichen Reihenfolge zurückkehren, in der sie eingefügt wurden. Da wir bei jedem Schritt immer den am weitesten links stehenden Knoten entfernen und dies das erste Element der Inorder-Traversierung ist, erhalten wir die Knoten immer in der Reihenfolge zurück, in der sie eingefügt wurden.

Kurz gesagt, wir erhalten O(1) amortisiertes Push and Pop und O(1) Worst-Case-Find-Min.

Wenn ich eine Worst-Case-Implementierung O(1) finden kann, werde ich sie definitiv veröffentlichen. Das war ein großes Problem; danke fürs posten!

26
templatetypedef

Ok, hier ist eine Lösung.

Zuerst brauchen wir etwas, was Push_back (), Push_front (), pop_back () und pop_front () in 0 (1) bereitstellt. Mit Array und 2 Iteratoren ist es einfach zu implementieren. Der erste Iterator zeigt nach vorne und von hinten nach hinten. Nennen wir solche Sachen Deque.

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

Erklärung:

Nehmen wir zum Beispiel Push-Nummern [12,5,10,7,11,19] und zu unserer MyQueue

1) Drücken von 12

D [12]
Min[12]

2) Drücken von 5

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

3) 10 drücken

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

4) Drücken von 7

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

6) Drücken von 11

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

7) Drücken von 19

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

Nun rufen wir pop_front () auf.

wir haben 

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

Das Minimum ist 5

Rufen wir noch einmal pop_front () auf

Erläuterung: pop_front entfernt 5 von D, aber auch das vordere Element von Min wird angezeigt, da es dem vorderen Element von D (5) entspricht.

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

Und Minimum ist 7. :)

21
UmmaGumma

Verwenden Sie einen Deque (A) zum Speichern der Elemente und einen weiteren Deque (B) zum Speichern der Minima.

Wenn x in die Warteschlange eingereiht ist, schieben Sie es nach A zurück und halten Sie pop_backing B gedrückt, bis die Rückseite von B kleiner als x ist.

beim Abreißen von A ist pop_front A als Rückgabewert und wenn es gleich der Vorderseite von B ist, auch pop_front B.

wenn Sie ein Minimum von A erhalten, verwenden Sie die Vorderseite von B als Rückgabewert.

dequeue und Getmin sind offensichtlich O (1). Berücksichtigen Sie für die Enqueue-Operation Push_back von n Elementen. Es gibt n Push_back nach A, n Push_back nach B und höchstens n pop_back von B, da jedes Element entweder in B bleibt oder einmal von B ausgefällt wird. Insgesamt gibt es O(3n) - Operationen und damit die Die fortgeführten Anschaffungskosten betragen ebenfalls O(1) für die Enqueue.

Der Grund, warum dieser Algorithmus funktioniert, ist der Grund, dass, wenn Sie x in A einreihen, in B Elemente, die größer als x sind, diese niemals Mindestwerte sind, da x länger in der Warteschlange A bleibt als Elemente in B (eine Warteschlange) ist FIFO). Deshalb müssen wir Elemente in B (von hinten) herausnehmen, die größer als x sind, bevor wir x in B drücken.

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])
3
jianglai

Wenn Sie nichts dagegen haben, ein paar zusätzliche Daten zu speichern, sollte es unbedeutend sein, den Mindestwert zu speichern. Push und Pop können den Wert aktualisieren, wenn das neue oder entfernte Element das Minimum ist. Die Rückgabe des Minimalwerts ist so einfach wie das Abrufen des Werts der Variablen.

Dies setzt voraus, dass get_min () die Daten nicht ändert. Wenn Sie lieber etwas wie pop_min () haben (dh das minimale Element entfernen), können Sie einfach einen Zeiger auf das eigentliche Element und das davor liegende Element (falls vorhanden) speichern und diese mit Push_rear () und pop_front () aktualisieren auch.

Nach Kommentaren bearbeiten:

Offensichtlich führt dies zu O(n) Push and Pop für den Fall, dass sich das Minimum bei diesen Vorgängen ändert, und erfüllt somit nicht unbedingt die Anforderungen.

1
Andy Mikula

Sie können tatsächlich eine LinkedList verwenden, um die Warteschlange zu verwalten.

Jedes Element in LinkedList wird vom Typ sein 

class LinkedListElement
{
   LinkedListElement next;
   int currentMin;
}

Sie können zwei Zeiger haben, von denen einer auf den Anfang und die anderen auf das Ende zeigt. 

Wenn Sie ein Element am Anfang der Warteschlange hinzufügen. Untersuchen Sie den Startzeiger und den einzufügenden Knoten. Wenn der Knoten zum Einfügen von currentmin kleiner ist als der Start currentmin, wird der Knoten zum Einfügen von currentmin das Minimum. Andernfalls aktualisieren Sie currentmin mit start currentmin.

Wiederholen Sie dasselbe für Enque.

1
Sandeep

Lösungen zu dieser Frage, einschließlich Code, finden Sie hier: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

1
Olhovsky

Wir wissen, dass Push und Pop konstante Zeitoperationen sind [um genau zu sein (1)].

Wenn wir jedoch an get_min () denken (d. H., Um die aktuelle Mindestanzahl in der Warteschlange zu ermitteln), ist im Allgemeinen das erste, was mir einfällt, dass die ganze Warteschlange jedes Mal durchsucht wird, wenn die Anforderung nach dem Minimalelement erfolgt. Dies führt jedoch niemals zu einer konstanten Zeitoperation, die das Hauptziel des Problems ist.

Dies wird in den Interviews in der Regel sehr häufig gestellt, daher müssen Sie den Trick kennen

Um dies zu tun, müssen wir zwei weitere Warteschlangen verwenden, die die Spur des minimalen Elements beibehalten, und wir müssen diese beiden Warteschlangen weiter modifizieren, während wir Push- und Pop-Vorgänge in der Warteschlange durchführen, so dass das minimale Element in O(1) Zeit.

Hier ist der selbstbeschreibende Sudo-Code, der auf dem oben genannten Ansatz basiert. 

    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;
    }
0
Sachin
#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;
}
0
TheMan

Diese Lösung enthält 2 Warteschlangen:
1. main_q - speichert die Eingangsnummern.
2. min_q - speichert die min-Zahlen nach bestimmten Regeln, die wir beschrieben haben (erscheint in den Funktionen MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ()).

Hier ist der Code in Python. Die Warteschlange wird mithilfe einer Liste implementiert.
Die Hauptidee liegt in den Funktionen MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ().
Eine Schlüsselannahme ist, dass das Leeren einer Warteschlange o (0) erfordert. 
.__ Am Ende steht ein Test zur Verfügung.

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 __== '__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))

Die Ausgabe des obigen Tests ist:

"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
0
user3139774

Java-Implementierung

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);
        }
    }
}
0
Nitish Bhagat