Warteschlange verwendet einen Stack

Ich bin nicht einverstanden mit dem vorhandenen Antwort. In der Regel, eine Warteschlange First In First Out, während ein stack ist offensichtlich Last In, First Out. Ich kann mir nur denken, dass der eine Implementierung mit zwei stacks, knallen die ganze Sache und das hinzufügen alle, aber der Letzte Punkt auf den zweiten Stapel.

Scheint wie eine dumme Sache zu tun, aber ich denke, es ist für die Sache der übung. Wie unten kommentiert, ist es auch möglich, in abgeschrieben O(1), weil der zweite Stapel in der richtigen Reihenfolge. Sie können nur Elemente aus dem zweiten Stapel, bis Sie laufen aus, die Sie verschieben alles, was aus den ursprünglichen Stapel zu dem zweiten Stapel.

Einer FIFO-Warteschlange würde einfach sein, einen Stapel mit Enqueue wird Push und Dequeue wird Pop. Das macht keinen Sinn als übung, also ich würde auf jeden Fall davon ausgehen, eine FIFO-Warteschlange vorgesehen war.

Bearbeiten: Hinzugefügt einige links, etwas nicht einfach auf mein Handy 🙂

Warteschlange die privaten Daten muss ein Stack. Mit, nur Sie können natürlich trivial
implementieren Sie eine LIFO-Warteschlange nur für eine FIFO-Warteschlange müssen Sie ZWEI Stapel -- zu zitieren
Hinweis für übung 10 in dieser hervorragenden Seite, "Hinweis: Wenn Sie push-Elemente auf einen stack und dann knallen Sie alle, erscheinen Sie in umgekehrter Reihenfolge. Wenn Sie wiederholen Sie diesen Prozess, Sie sind jetzt wieder in Ordnung."...

Warteschlange mit stack? Sie benötigen 2-stacks, natürlich, das wäre ein O(n) queue-Implementierung.

Ich vermute, dass die Absicht der Frage ist zunächst die Definition einer Klasse Stack wie du haben, die hat die Kapazität zum speichern von int-Werten.

dann deklarieren Sie eine Klasse geerbt von stack, Queue genannt, die der eigenen addtoqueue und servefromqueue Funktionen, verwendet aber die gleiche Speicher-Mechanismus als Stack.

Gegeben, Ihre Umsetzung mag dies ein wenig seltsam, aber die haben wohl gedacht, eine Art verkettete Liste-Implementierung von stack (was den Vorteil hat, dass Sie nicht mit einer vordefinierten Obergrenze), in dem Fall die Warteschlange geerbt von stack-klar macht Sinn für design.

Wenn Sie wirklich wollen, implementieren Sie eine Warteschlange mit einem stack könnte man hinzufügen, eine Stack member-variable Queue Klasse. Die Methoden werden dann implementiert, wie dieses:

void Queue::enqueue(int value) {
  stack.push(value);
}

int Queue::dequeue() {
  //TODO: Check for empty queue.
  Stack tempStack;
  do {
    tempStack.push(stack.pop());
  } while (!stack.empty());
  int value = tempStack.pop();
  while (!tempStack.empty()) {
    stack.push(tempStack.pop());
  }
  return value;
}

Ist es eine sehr ineffiziente Umsetzung.

Gibt es verschiedene Typen von Warteschlangen:

• First in - First out (FIFO -) queues
• Last in - first out (LIFO) - Warteschlangen

Wenn Ihr queue ist eine LIFO-queue, als es wird lediglich eine Fassade aus einem Stapel, wo enque/deque Karte, um push/pop.

Wenn Sie möchten, eine FIFO-Warteschlange müssen Sie zwei Stapel und schieben Sie die Elemente von einem zum anderen, um zu bekommen, um das erste element, wenn es enqued, dann können Sie deque von oben auf dem zweiten Stapel (in umgekehrter Reihenfolge), soweit nichts anderes ist enqued. wenn das passiert, ned shift alles wieder auf den ersten Stapel... Nicht sehr effizient ist, aber vielleicht erkennen, dass ist der Sinn der übung...

NB: möchten Sie vielleicht, um zumindest die max Kapazität der stack konfigurierbar bei der Bauzeit. So dass es völlig dynamisch ist wahrscheinlich aus dem Rahmen der übung, die Sie versuchen zu lösen.