Wie Implementieren stack mit Priorität in die Warteschlange?

, Wie die Umsetzung stack mit Priorität in die Warteschlange?

Jungs das ist ein Microsoft Interview-Frage für Software Engineer/Developer.Ich kann einfach nicht Sinn der Frage.Also ich goggled und gefunden:

Stapel und Warteschlangen können modelliert werden, als bestimmte Arten von priority queues. In einem Stapel, die Priorität jedes eingefügte element ist streng monoton Steigend; so, das Letzte eingefügte element ist immer das erste abgerufen werden.

Also, was diese Frage will uns zu tun.Als Stapel (korrigiert mich, wenn falsch) bin, werden implizit implementiert, die als priority-queues (Priorität monoton steigende als Elemente Hinzugefügt werden).

Weiß jemand die Bedeutung dieser Frage.Was sollen wir tun, wenn diese Art von Frage in einem interview gefragt.

Stacks sind nicht in der Regel implementiert, die als priority-queues. Fragen Sie Sie, wie würden Sie implementieren Sie einen stack mit Hilfe einer priority-queue, wenn Sie musste. Und Sie haben beschrieben, die einen stack als einen speziellen Fall einer priority queue, um Ihnen den Einstieg. Soweit ich sehen kann, die Frage ist trivial, wenn Sie wissen, was ein stack ist und was eine Priorität ist, obwohl ich vermute, dass der Punkt vielleicht nicht so sehr die eigentliche Implementierung, als ein Weg, um herauszufinden, wie eine bestimmte Priorität-Warteschlange verhält sich mit einer bestimmten Nutzung Muster, das könnte ganz normal sein. Vielleicht ineffizient.
In einem Wort: schlecht.
Jungs immer noch nicht, wie Sie zur Umsetzung des LIFO-Verhalten des Stacks in der priority queue.
+1 zu SteveJessop zu sagen, "ich nehme an, der Punkt ist vielleicht nicht so sehr die tatsächliche Umsetzung, als eine Art und Weise zu untersuchen, wie eine bestimmte Priorität-Warteschlange verhält sich mit einer bestimmten Nutzung Muster, das könnte ganz normal sein"

InformationsquelleAutor Algorithmist | 2011-02-02

algorithm

20

Pseudocode:
```
//stack of Key
class Stack {
    class Element { int prio, Key elem; };
    MaxPriorityQueue<Element> q;
    int top_priority = 0;

    void push(Key x) { q.push(Element(top_priority++, x)); }
    Key pop() { top_priority--; return q.pop().elem; }
};
```
LIFO-Verhalten folgt aus der Tatsache, dass jedes neue element geschoben wird, mit einer Priorität höher als alle aktuellen Elemente, so wird es knallte, bevor Sie.

Gibt es zwei Möglichkeiten, um eine Antwort auf diese interview-Frage. Man ist zu erklären, im detail die Struktur oben. Die zweite ist kurz zu erwähnen, Murmele etwas von O(lg n) und sagen, Sie würden nie implementiert einen stack, auf diese Weise.

Dank larsmans für Ihre Lösung.Das heißt, wir sind immer erforderlich, um ein element einzufügen, mit einer Priorität höher als alle bisher eingefügten Elemente sonst das eingefügte element nicht abgerufen werden, in der Warteschlange getelement Betrieb.
Tut es zählen als pseudocode, wenn es auch in C++? :p
Es ist kein Gültiger C++, da wäre alles private und Element keinen Konstruktor hat. Wenn ich zu faul bin zu schreiben richtigen code, ich nenne das Ergebnis pseudocode 🙂
Das ist gültiges C++. Es ist nicht eine vollständige linkable-Programm, aber es ist immer noch gültiges C++.
prio, Key elem; ist kein Gültiger C++, noch ist die Zuordnung int top_priority = 0; in der Klasse Körper.

InformationsquelleAutor Fred Foo
6

Wenn Sie nicht wissen, was eine Priorität ist, Fragen Sie. Wenn Sie nicht wissen, was ein stack ist, Fragen Sie. Wenn Sie nicht verstehen, die Frage, der Fragen. Jetzt sollte man hoffentlich in der Lage sein, einen Adapter wie den folgenden erforderlich ist.
```
Stack :
    private:
      q : MaxPriorityQueue
      counter : 0

    public:
      push(x) : q.add(x, counter++)
      pop() : q.remove()
```
InformationsquelleAutor OrangeDog
2

Solche Fragen verlangen, dass Sie denken, ein bisschen tiefer( aber nicht so tief mit diesem).

Die Erklärung für diese Antwort ist, anstelle von einfügen jedes element mit den Werten als Schlüssel, sollten Sie wickeln Sie Sie in ein Objekt, und weisen Sie um als Attribut. Sie sollten diesen Auftrag als Schlüssel.

Beispiel-C-Code:
```
struct MyNode
{
  DataPacket dataPacket;
  int order;
};
```
Sie bedeuten zu sagen, wir müssen die Umsetzung der stack als verkettete Liste und jeder Knoten, der mit drei Feldern, ich.e nächste Zeiger,Schlüssel(Priorität),element.Und jetzt das einfügen neuer Knoten am Anfang, die höchste Priorität haben, und auch das entfernen von Knoten mit der höchsten Priorität ich.e der erste Knoten in der Liste.
Nicht eine link-Liste, eine PriorityQueue. Datenpaket enthält die Daten, die nur eine ganze Zahl sein.

InformationsquelleAutor Shamim Hafiz

Hier ist die java-Implementierung für diese Frage.

public class StackPriorityQueue {

PriorityQueue<StackElement> queue = new PriorityQueue<>(10, new Comparator<StackElement>() {
    @Override
    public int compare(StackElement o1, StackElement o2) {
        return o2.key - o1.key;
    }
});

int order = 1;

public void push(int val){
    StackElement element = new StackElement(order++,val);
    queue.add(element);
}

public Integer pop(){
    if(queue.isEmpty()){
        System.out.println("Stack Underflow");
        return null;
    }
    return queue.poll().value;
}

public static void main(String... args){
    StackPriorityQueue q = new StackPriorityQueue();
    q.push(5);
    q.push(10);
    q.push(1);
    q.push(3);
    q.push(50);
    q.push(500);
    q.push(60);
    q.push(30);
    q.push(40);
    q.push(23);
    q.push(34);

    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());
    System.out.println(q.pop());

   }

}

class StackElement {
  int key;
  int value;

  public StackElement(int key, int value) {
    this.key = key;
    this.value = value;
  }

}

perfekt arbeiten. vielen Dank.

InformationsquelleAutor shalvi_pandita

-1

Implementieren Sie einen stack mit einem priority queue( z.B. PQ) mit min-heap. Sie benötigen eine extra integer-variable (sagen wir t). 't' verwendet werden, wie die Priorität beim einfügen/löschen von Elementen aus PQ.

Müssen Sie initialisieren t (sagen wir t=100) auf einen Wert ab.
```
push(int element){
PQ.insert(t,element);
t--;           //decrease priority value(less priority will be popped first)
}

pop(){
return PQ.deleteMin();
}

peek(){
return PQ.min();
}
```
Hinweis: Sie können auch die system-Zeit, push-Elemente nach der Priorität.
```
push(int element){
PQ.insert(-getTime(),element);   //negative of sys time(less priority will be popped first)
}
```
InformationsquelleAutor Prateek Joshi

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.