Wie implementiere ich eine Warteschlange mit zwei Stapeln?

394

Angenommen, wir haben zwei Stapel und keine andere temporäre Variable.

Ist es möglich, eine Warteschlangendatenstruktur nur mit den beiden Stapeln zu "konstruieren"?

Nitin
quelle

Antworten:

701

Behalte 2 Stapel, nennen wir sie inboxund outbox.

Enqueue :

  • Schieben Sie das neue Element auf inbox

Warteschlange :

  • Wenn outboxes leer ist, füllen Sie inboxes wieder auf, indem Sie jedes Element herausnehmen und darauf schiebenoutbox

  • Pop und geben Sie das oberste Element von zurück outbox

Bei dieser Methode befindet sich jedes Element genau einmal in jedem Stapel. Dies bedeutet, dass jedes Element zweimal gedrückt und zweimal gepoppt wird, was zu amortisierten Operationen mit konstanter Zeit führt.

Hier ist eine Implementierung in Java:

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}
Dave L.
quelle
13
Die Zeitkomplexität im ungünstigsten Fall ist immer noch O (n). Ich sage dies weiterhin, weil ich hoffe, dass keine Schüler da draußen (dies klingt nach einer Hausaufgabe / Bildungsfrage) denken, dass dies ein akzeptabler Weg ist, eine Warteschlange zu implementieren.
Tyler
26
Es ist wahr, dass die Worst-Case-Zeit für eine einzelne Pop-Operation O (n) ist (wobei n die aktuelle Größe der Warteschlange ist). Die Worst-Case-Zeit für eine Folge von n Warteschlangenoperationen ist jedoch auch O (n), was uns die amortisierte konstante Zeit gibt. Ich würde eine Warteschlange nicht auf diese Weise implementieren, aber es ist nicht so schlimm.
Dave L.
1
@ Tyler Wenn Ihr Stack wie die meisten Array-basiert ist, erhalten Sie immer O (n) Worst Case für eine einzelne Operation.
Thomas Ahle
2
@ Tyler: Überprüfen Sie sgi.com/tech/stl/Deque.html . Deque "unterstützt den wahlfreien Zugriff auf Elemente". Daher sind sowohl Deque als auch Stack Array-basiert. Dies liegt daran, dass Sie eine bessere Referenzlokalität erhalten und daher in der Praxis schneller sind.
Thomas Ahle
13
@Newtang a) Warteschlange 1,2,3 => Posteingang [3,2,1] / Postausgang [] . b) Warteschlange. Postausgang ist leer, also nachfüllen => Posteingang [] / Postausgang [1,2,3] . Pop aus dem Postausgang, Rückgabe 1 => Posteingang [] / Postausgang [2,3] . c) Warteschlange 4,5 => Posteingang [5,4] / Postausgang [2,3] . d) Warteschlange. Der Postausgang ist nicht leer. Verlassen Sie den Postausgang und geben Sie 2 => Posteingang [5,4] / Postausgang [3] zurück . Ist das sinnvoller?
Dave L.
226

A - So kehren Sie einen Stapel um

Um zu verstehen, wie eine Warteschlange mit zwei Stapeln erstellt wird, sollten Sie wissen, wie Sie einen Stapel kristallklar umkehren. Denken Sie daran, wie der Stapel funktioniert. Er ist dem Geschirrstapel in Ihrer Küche sehr ähnlich. Das zuletzt gewaschene Gericht befindet sich oben auf dem sauberen Stapel, der als L ast I n F irst O bezeichnet wird in der Informatik ut (LIFO) bezeichnet wird.

Stellen wir uns unseren Stapel wie eine Flasche vor;

Geben Sie hier die Bildbeschreibung ein

Wenn wir die Ganzzahlen 1,2,3 drücken, befindet sich 3 oben auf dem Stapel. Da 1 zuerst gedrückt wird, wird 2 oben auf 1 gesetzt. Zuletzt wird 3 oben auf den Stapel gelegt, und der letzte Status unseres Stapels, der als Flasche dargestellt wird, ist wie folgt.

Geben Sie hier die Bildbeschreibung ein

Jetzt haben wir unseren Stapel so dargestellt, dass eine Flasche mit den Werten 3,2,1 gefüllt ist. Und wir wollen den Stapel umkehren, so dass das obere Element des Stapels 1 und das untere Element des Stapels 3 ist. Was können wir tun? Wir können die Flasche nehmen und sie verkehrt herum halten, damit sich alle Werte in der Reihenfolge umkehren?

Geben Sie hier die Bildbeschreibung ein

Ja, das können wir, aber das ist eine Flasche. Um den gleichen Prozess durchzuführen, benötigen wir einen zweiten Stapel, in dem die ersten Stapelelemente in umgekehrter Reihenfolge gespeichert werden. Lassen Sie uns unseren bestückten Stapel links und unseren neuen leeren Stapel rechts platzieren. Um die Reihenfolge der Elemente umzukehren, werden wir jedes Element vom linken Stapel entfernen und auf den rechten Stapel verschieben. Sie können auf dem Bild unten sehen, was passiert, wenn wir dies tun.

Geben Sie hier die Bildbeschreibung ein

Wir wissen also, wie man einen Stapel umkehrt.

B - Verwenden von zwei Stapeln als Warteschlange

Im vorherigen Teil habe ich erklärt, wie wir die Reihenfolge der Stapelelemente umkehren können. Dies war wichtig, da die Ausgabe genau in umgekehrter Reihenfolge einer Warteschlange erfolgt, wenn Elemente in den Stapel verschoben und eingefügt werden. Lassen Sie uns anhand eines Beispiels das Array von Ganzzahlen {1, 2, 3, 4, 5}auf einen Stapel verschieben. Wenn wir die Elemente {5, 4, 3, 2, 1}einfügen und drucken, bis der Stapel leer ist, erhalten wir das Array in der umgekehrten Reihenfolge der Push-Reihenfolge. Beachten Sie, dass bei derselben Eingabe die Ausgabe in die Warteschlange gestellt wird, bis die Warteschlange leer ist wird sein {1, 2, 3, 4, 5}. Es ist also offensichtlich, dass bei derselben Eingabereihenfolge von Elementen die Ausgabe der Warteschlange genau umgekehrt ist wie die Ausgabe eines Stapels. Da wir wissen, wie man einen Stapel mit einem zusätzlichen Stapel umkehrt, können wir eine Warteschlange mit zwei Stapeln erstellen.

Unser Warteschlangenmodell besteht aus zwei Stapeln. Ein Stapel wird für die enqueueOperation verwendet (Stapel Nr. 1 links wird als Eingabestapel bezeichnet), ein anderer Stapel wird für die dequeueOperation verwendet (Stapel Nr. 2 rechts wird als Ausgabestapel bezeichnet). Schauen Sie sich das Bild unten an.

Geben Sie hier die Bildbeschreibung ein

Unser Pseudocode ist wie folgt;


Warteschlangenbetrieb

Push every input element to the Input Stack

Warteschlangenbetrieb

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and push them to the Output Stack until Input Stack is Empty

pop from Output Stack

Lassen Sie uns die Ganzzahlen in die Warteschlange stellen {1, 2, 3}. Ganzzahlen werden auf den Eingangsstapel ( Stapel Nr. 1 ) auf der linken Seite verschoben.

Geben Sie hier die Bildbeschreibung ein

Was passiert dann, wenn wir eine Dequeue-Operation ausführen? Immer wenn eine Dequeue-Operation ausgeführt wird, prüft die Warteschlange, ob der Ausgabestapel leer ist oder nicht (siehe Pseudocode oben). Wenn der Ausgabestapel leer ist, wird der Eingabestapel in der Ausgabe extrahiert, damit die Elemente des Eingangsstapels wird umgekehrt. Vor der Rückgabe eines Werts lautet der Status der Warteschlange wie folgt:

Geben Sie hier die Bildbeschreibung ein

Überprüfen Sie die Reihenfolge der Elemente im Ausgabestapel (Stapel 2). Es ist offensichtlich, dass wir die Elemente aus dem Ausgabestapel entfernen können, sodass die Ausgabe dieselbe ist, als ob wir uns aus einer Warteschlange entfernt hätten. Wenn wir also zwei Dequeue-Operationen ausführen, erhalten wir {1, 2}jeweils zuerst. Dann ist Element 3 das einzige Element des Ausgabestapels, und der Eingabestapel ist leer. Wenn wir die Elemente 4 und 5 in die Warteschlange stellen, lautet der Status der Warteschlange wie folgt:

Geben Sie hier die Bildbeschreibung ein

Jetzt ist der Ausgabestapel nicht leer, und wenn wir eine Dequeue-Operation ausführen, werden nur 3 aus dem Ausgabestapel entfernt. Dann wird der Zustand wie folgt gesehen;

Geben Sie hier die Bildbeschreibung ein

Wenn wir zwei weitere Dequeue-Operationen ausführen, prüft die Warteschlange bei der ersten Dequeue-Operation erneut, ob der Ausgabestapel leer ist, was wahr ist. Ziehen Sie dann die Elemente des Eingabestapels heraus und verschieben Sie sie in den Ausgabestapel, bis der Eingabestapel leer ist. Der Status der Warteschlange lautet dann wie folgt.

Geben Sie hier die Bildbeschreibung ein

Leicht zu sehen ist die Ausgabe der beiden Dequeue-Operationen {4, 5}

C - Implementierung einer Warteschlange mit zwei Stapeln

Hier ist eine Implementierung in Java. Ich werde die vorhandene Implementierung von Stack nicht verwenden, daher wird das Beispiel hier das Rad neu erfinden.

C - 1) MyStack-Klasse: Eine einfache Stack-Implementierung

public class MyStack<T> {

    // inner generic Node class
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head;
    private int size;

    public void push(T e) {
        Node<T> newElem = new Node(e);

        if(head == null) {
            head = newElem;
        } else {
            newElem.next = head;
            head = newElem;     // new elem on the top of the stack
        }

        size++;
    }

    public T pop() {
        if(head == null)
            return null;

        T elem = head.data;
        head = head.next;   // top of the stack is head.next

        size--;

        return elem;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printStack() {
        System.out.print("Stack: ");

        if(size == 0)
            System.out.print("Empty !");
        else
            for(Node<T> temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

        System.out.printf("\n");
    }
}

C - 2) MyQueue-Klasse: Warteschlangenimplementierung mit zwei Stapeln

public class MyQueue<T> {

    private MyStack<T> inputStack;      // for enqueue
    private MyStack<T> outputStack;     // for dequeue
    private int size;

    public MyQueue() {
        inputStack = new MyStack<>();
        outputStack = new MyStack<>();
    }

    public void enqueue(T e) {
        inputStack.push(e);
        size++;
    }

    public T dequeue() {
        // fill out all the Input if output stack is empty
        if(outputStack.isEmpty())
            while(!inputStack.isEmpty())
                outputStack.push(inputStack.pop());

        T temp = null;
        if(!outputStack.isEmpty()) {
            temp = outputStack.pop();
            size--;
        }

        return temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

}

C - 3) Demo-Code

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();

        // enqueue integers 1..3
        for(int i = 1; i <= 3; i++)
            queue.enqueue(i);

        // execute 2 dequeue operations 
        for(int i = 0; i < 2; i++)
            System.out.println("Dequeued: " + queue.dequeue());

        // enqueue integers 4..5
        for(int i = 4; i <= 5; i++)
            queue.enqueue(i);

        // dequeue the rest
        while(!queue.isEmpty())
            System.out.println("Dequeued: " + queue.dequeue());
    }

}

C - 4) Probenausgabe

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
Levent Divilioglu
quelle
18
Ich würde dies den ganzen Tag +1 tun, wenn ich könnte. Ich konnte nicht verstehen, wie es konstante Zeit amortisiert wurde. Ihre Illustrationen haben die Dinge wirklich geklärt, insbesondere den Teil, bei dem die verbleibenden Elemente auf dem Ausgabestapel belassen und erst nachgefüllt werden, wenn sie geleert sind.
Shane McQuillan
1
Dies hat wirklich dazu beigetragen, die Timeout-Fehler zu vermeiden, die ich beim Pop bekam. Ich habe die Elemente wieder in den ursprünglichen Stapel gelegt, aber das war nicht nötig. Ein großes Lob!
Pranit Bankar
2
Alle Kommentare sollten diesem nachempfunden sein.
lolololol ol
4
Ich brauchte wirklich keine Lösung dafür, nur stöbern ... Aber wenn ich eine Antwort wie diese sehe, verliebe ich mich einfach. Tolle Antwort !!!
Maverick
80

Sie können sogar eine Warteschlange mit nur einem Stapel simulieren. Der zweite (temporäre) Stapel kann durch den Aufrufstapel rekursiver Aufrufe der Einfügemethode simuliert werden.

Das Prinzip bleibt beim Einfügen eines neuen Elements in die Warteschlange gleich:

  • Sie müssen Elemente von einem Stapel auf einen anderen temporären Stapel übertragen, um ihre Reihenfolge umzukehren.
  • Schieben Sie dann das neue einzufügende Element auf den temporären Stapel
  • Übertragen Sie dann die Elemente zurück auf den ursprünglichen Stapel
  • Das neue Element befindet sich am unteren Rand des Stapels und das älteste Element befindet sich oben (zuerst zu knallen).

Eine Warteschlangenklasse, die nur einen Stapel verwendet, lautet wie folgt:

public class SimulatedQueue<E> {
    private java.util.Stack<E> stack = new java.util.Stack<E>();

    public void insert(E elem) {
        if (!stack.empty()) {
            E topElem = stack.pop();
            insert(elem);
            stack.push(topElem);
        }
        else
            stack.push(elem);
    }

    public E remove() {
        return stack.pop();
    }
}
Pythonquick
quelle
51
Vielleicht sieht der Code elegant aus, ist aber sehr ineffizient (O (n ** 2) einfügen) und hat immer noch zwei Stapel, einen im Heap und einen im Aufrufstapel, wie @pythonquick hervorhebt. Bei einem nicht rekursiven Algorithmus können Sie immer einen "zusätzlichen" Stapel aus dem Aufrufstapel in Sprachen abrufen, die die Rekursion unterstützen.
Antti Huima
1
@ antti.huima Und würdest du erklären, wie dies eine quadratische Einfügung sein könnte?! Soweit ich weiß, führt insert n Pop- und n Push-Operationen aus, sodass es sich um einen perfekt linearen O (n) -Algorithmus handelt.
LP_
1
@LP_ es dauert quadratische Zeit O (n ^ 2), um unter n itemsVerwendung der obigen Datenstruktur in die Warteschlange einzufügen . die Summe (1 + 2 + 4 + 8 + .... + 2(n-1))ergibt ~O(n^2). Ich hoffe du verstehst, worum es geht.
Ankit Kumar
1
@ antti.huima Sie haben über die Komplexität der Einfügefunktion gesprochen (Sie sagten "O (n 2) Einfügen" - Sie meinten wahrscheinlich "O (n 2) Füllen"). Konventionell ist "die Komplexitätseinfügung" die Zeit, die eine Einfügung benötigt, was hier linear in der Anzahl der bereits vorhandenen Elemente ist. Wenn wir in der Zeit gesprochen haben, die zum Einfügen benötigt wird sprechen würden, n Elementen benötigt wird, würden wir sagen, dass eine Hashtabelle eine lineare Einfügung hat. Welches ist nicht der Fall.
LP_
2
Sie verwenden den Stapel im Wesentlichen als Stapel. Dies bedeutet, dass bei einer großen Anzahl von Elementen im Stapel ein Stapelüberlauf auftreten kann - es ist fast so, als ob die Lösung für diese Site entwickelt wurde!
UKMonkey
11

Die zeitliche Komplexität wäre jedoch schlimmer. Eine gute Warteschlangenimplementierung erledigt alles in konstanter Zeit.

Bearbeiten

Ich bin mir nicht sicher, warum meine Antwort hier abgelehnt wurde. Wenn wir programmieren, ist uns die Zeitkomplexität wichtig, und die Verwendung von zwei Standardstapeln zum Erstellen einer Warteschlange ist ineffizient. Es ist ein sehr gültiger und relevanter Punkt. Wenn jemand anderes das Bedürfnis hat, dies weiter abzustimmen, würde mich interessieren, warum.

Ein bisschen mehr Details : Warum die Verwendung von zwei Stapeln schlechter ist als nur eine Warteschlange: Wenn Sie zwei Stapel verwenden und jemand die Warteschlange aufruft, während der Postausgang leer ist, benötigen Sie eine lineare Zeit, um zum Ende des Posteingangs zu gelangen (wie Sie sehen können) in Daves Code).

Sie können eine Warteschlange als einfach verknüpfte Liste implementieren (jedes Element zeigt auf das nächst eingefügte Element), wobei Sie einen zusätzlichen Zeiger auf das zuletzt eingefügte Element für Pushs behalten (oder es zu einer zyklischen Liste machen). Das Implementieren von Warteschlangen und Warteschlangen in dieser Datenstruktur ist in konstanter Zeit sehr einfach. Das ist im schlimmsten Fall eine konstante Zeit, die nicht abgeschrieben wird. Und da die Kommentare nach dieser Klarstellung zu fragen scheinen, ist die konstante Zeit im ungünstigsten Fall strikt besser als die amortisierte konstante Zeit.

Tyler
quelle
Nicht im Durchschnitt. Brians Antwort beschreibt eine Warteschlange, die konstante Warteschlangen- und Warteschlangenoperationen amortisiert hätte.
Daniel Spiewak
Das stimmt. Sie haben die gleiche durchschnittliche Komplexität von Fall und amortisierter Zeit. Der Standardwert ist jedoch normalerweise der Worst-Case-Vorgang pro Operation. Dies ist O (n), wobei n die aktuelle Größe der Struktur ist.
Tyler
1
Der schlimmste Fall kann auch abgeschrieben werden. Beispielsweise wird normalerweise angenommen, dass veränderbare dynamische Arrays (Vektoren) eine konstante Einfügungszeit haben, obwohl von Zeit zu Zeit ein teurer Vorgang zum Ändern der Größe und zum Kopieren erforderlich ist.
Daniel Spiewak
1
"Worst-Case" und "Amortized" sind zwei verschiedene Arten von Zeitkomplexität. Es ist nicht sinnvoll zu sagen, dass "Worst-Case amortisiert werden kann" - wenn Sie den Worst-Case = Amortized machen könnten, wäre dies eine signifikante Verbesserung; Sie würden nur über den schlimmsten Fall ohne Mittelwertbildung sprechen.
Tyler
Ich bin mir nicht sicher, was Sie damit meinen, dass O (1) Worst-Case "streng besser" ist als eine Kombination aus O (1) Average Case und O (n) Worst Case. Konstante Skalierungsfaktoren sind wichtig. Eine Datenstruktur, die, wenn sie N Elemente enthält, möglicherweise nach N Operationen zu einem Zeitpunkt von N Mikrosekunden neu gepackt werden muss und ansonsten eine Mikrosekunde pro Operation benötigt, kann weitaus nützlicher sein als eine, die für jede Operation sogar eine Millisekunde benötigt wenn die Datengröße auf Millionen von Elementen erweitert wird (was bedeutet, dass einige einzelne Vorgänge mehrere Sekunden dauern würden).
Supercat
8

Die zu implementierende Warteschlange sei q und die zur Implementierung von q verwendeten Stapel seien Stapel1 und Stapel2.

q kann auf zwei Arten implementiert werden:

Methode 1 (indem der enQueue-Betrieb teuer wird)

Diese Methode stellt sicher, dass sich das neu eingegebene Element immer oben in Stapel 1 befindet, sodass die deQueue-Operation nur aus Stapel 1 angezeigt wird. Um das Element oben auf Stapel1 zu platzieren, wird Stapel2 verwendet.

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

Methode 2 (Durch kostspielige DeQueue-Operation)

Bei dieser Methode wird im En-Queue-Betrieb das neue Element oben in Stapel1 eingegeben. Wenn im De-Queue-Betrieb Stapel2 leer ist, werden alle Elemente nach Stapel2 verschoben und schließlich wird der Anfang von Stapel2 zurückgegeben.

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

Methode 2 ist definitiv besser als Methode 1. Methode 1 verschiebt alle Elemente zweimal in der enQueue-Operation, während Methode 2 (in der deQueue-Operation) die Elemente einmal verschiebt und Elemente nur verschiebt, wenn stack2 leer ist.

Rahul Gandhi
quelle
Keine der Lösungen, die ich verstanden habe, außer Ihrer Methode 2. Ich mag die Art und Weise, wie Sie sie mit der Enqueue- und Dequeue-Methode mit den Schritten erklären.
TheGreenCabbage
1
google.com/…
saß am
3

Eine Lösung in c #

public class Queue<T> where T : class
{
    private Stack<T> input = new Stack<T>();
    private Stack<T> output = new Stack<T>();
    public void Enqueue(T t)
    {
        input.Push(t);
    }

    public T Dequeue()
    {
        if (output.Count == 0)
        {
            while (input.Count != 0)
            {
                output.Push(input.Pop());
            }
        }

        return output.Pop();
    }
}
Santhosh
quelle
2

Zwei Stapel in der Warteschlange sind als Stapel1 und Stapel2 definiert .

Enqueue: Die euqueued-Elemente werden immer in stack1 verschoben

Dequeue: Die Oberseite von stack2 kann herausspringen, da es das erste Element ist, das in die Warteschlange eingefügt wird, wenn stack2 nicht leer ist. Wenn stack2 leer ist, werden alle Elemente aus entfernt stack1 entfernt und einzeln in stack2 verschoben . Das erste Element in einer Warteschlange wird in den unteren Bereich von Stack1 verschoben . Es kann direkt nach dem Poppen und Drücken herausspringen, da es sich oben auf Stapel2 befindet .

Das Folgende ist der gleiche C ++ - Beispielcode:

template <typename T> class CQueue
{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const T& node); 
    T deleteHead();                 

private:
    stack<T> stack1;
    stack<T> stack2;
};

template<typename T> void CQueue<T>::appendTail(const T& element) {
    stack1.push(element);
} 

template<typename T> T CQueue<T>::deleteHead() {
    if(stack2.size()<= 0) {
        while(stack1.size()>0) {
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }


    if(stack2.size() == 0)
        throw new exception("queue is empty");


    T head = stack2.top();
    stack2.pop();


    return head;
}

Diese Lösung ist ausgeliehen von meinem Blog . Eine detailliertere Analyse mit schrittweisen Betriebssimulationen finden Sie auf meiner Blog-Webseite.

Harry He
quelle
2

Sie müssen alles vom ersten Stapel entfernen, um das untere Element zu erhalten. Legen Sie sie dann bei jeder "Dequeue" -Operation alle wieder auf den zweiten Stapel.

user11055
quelle
3
Ja, du hast recht. Ich frage mich, wie Sie so viele Abstimmungen erhalten haben. Ich habe Ihre Antwort
positiv
Es ist gruselig zu sehen, dass dies seine letzte Antwort war und seitdem ein Jahrzehnt vergangen ist.
Shanu Gupta
2

Für C # -Entwickler ist hier das komplette Programm:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueueImplimentationUsingStack
{
    class Program
    {
        public class Stack<T>
        {
            public int size;
            public Node<T> head;
            public void Push(T data)
            {
                Node<T> node = new Node<T>();
                node.data = data;
                if (head == null)
                    head = node;
                else
                {
                    node.link = head;
                    head = node;
                }
                size++;
                Display();
            }
            public Node<T> Pop()
            {
                if (head == null)
                    return null;
                else
                {
                    Node<T> temp = head;
                    //temp.link = null;
                    head = head.link;
                    size--;
                    Display();
                    return temp;
                }
            }
            public void Display()
            {
                if (size == 0)
                    Console.WriteLine("Empty");
                else
                {
                    Console.Clear();
                    Node<T> temp = head;
                    while (temp!= null)
                    {
                        Console.WriteLine(temp.data);
                        temp = temp.link;
                    }
                }
            }
        }

        public class Queue<T>
        {
            public int size;
            public Stack<T> inbox;
            public Stack<T> outbox;
            public Queue()
            {
                inbox = new Stack<T>();
                outbox = new Stack<T>();
            }
            public void EnQueue(T data)
            {
                inbox.Push(data);
                size++;
            }
            public Node<T> DeQueue()
            {
                if (outbox.size == 0)
                {
                    while (inbox.size != 0)
                    {
                        outbox.Push(inbox.Pop().data);
                    }
                }
                Node<T> temp = new Node<T>();
                if (outbox.size != 0)
                {
                    temp = outbox.Pop();
                    size--;
                }
                return temp;
            }

        }
        public class Node<T>
        {
            public T data;
            public Node<T> link;
        }

        static void Main(string[] args)
        {
            Queue<int> q = new Queue<int>();
            for (int i = 1; i <= 3; i++)
                q.EnQueue(i);
           // q.Display();
            for (int i = 1; i < 3; i++)
                q.DeQueue();
            //q.Display();
            Console.ReadKey();
        }
    }
}
Jaydeep Shil
quelle
2

Implementieren Sie die folgenden Operationen einer Warteschlange mithilfe von Stapeln.

push (x) - Schieben Sie das Element x in den hinteren Bereich der Warteschlange.

pop () - Entfernt das Element vor der Warteschlange.

peek () - Holen Sie sich das vordere Element.

empty () - Gibt zurück, ob die Warteschlange leer ist.

Geben Sie hier die Bildbeschreibung ein

class MyQueue {

  Stack<Integer> input;
  Stack<Integer> output;

  /** Initialize your data structure here. */
  public MyQueue() {
    input = new Stack<Integer>();
    output = new Stack<Integer>();
  }

  /** Push element x to the back of queue. */
  public void push(int x) {
    input.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
    peek();
    return output.pop();
  }

  /** Get the front element. */
  public int peek() {
    if(output.isEmpty()) {
        while(!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
  }

  /** Returns whether the queue is empty. */
  public boolean empty() {
    return input.isEmpty() && output.isEmpty();
  }
}
Girish Rathi
quelle
1
// Two stacks s1 Original and s2 as Temp one
    private Stack<Integer> s1 = new Stack<Integer>();
    private Stack<Integer> s2 = new Stack<Integer>();

    /*
     * Here we insert the data into the stack and if data all ready exist on
     * stack than we copy the entire stack s1 to s2 recursively and push the new
     * element data onto s1 and than again recursively call the s2 to pop on s1.
     * 
     * Note here we can use either way ie We can keep pushing on s1 and than
     * while popping we can remove the first element from s2 by copying
     * recursively the data and removing the first index element.
     */
    public void insert( int data )
    {
        if( s1.size() == 0 )
        {
            s1.push( data );
        }
        else
        {
            while( !s1.isEmpty() )
            {
                s2.push( s1.pop() );
            }
            s1.push( data );
            while( !s2.isEmpty() )
            {
                s1.push( s2.pop() );
            }
        }
    }

    public void remove()
    {
        if( s1.isEmpty() )
        {
            System.out.println( "Empty" );
        }
        else
        {
            s1.pop();

        }
    }
imvp
quelle
1

Eine Implementierung einer Warteschlange mit zwei Stapeln in Swift:

struct Stack<Element> {
    var items = [Element]()

    var count : Int {
        return items.count
    }

    mutating func push(_ item: Element) {
        items.append(item)
    }

    mutating func pop() -> Element? {
        return items.removeLast()
    }

    func peek() -> Element? {
        return items.last
    }
}

struct Queue<Element> {
    var inStack = Stack<Element>()
    var outStack = Stack<Element>()

    mutating func enqueue(_ item: Element) {
        inStack.push(item)
    }

    mutating func dequeue() -> Element? {
        fillOutStack() 
        return outStack.pop()
    }

    mutating func peek() -> Element? {
        fillOutStack()
        return outStack.peek()
    }

    private mutating func fillOutStack() {
        if outStack.count == 0 {
            while inStack.count != 0 {
                outStack.push(inStack.pop()!)
            }
        }
    }
}
Davejlin
quelle
1

Sie erhalten zwar viele Beiträge zum Implementieren einer Warteschlange mit zwei Stapeln: 1. Entweder indem Sie den enQueue-Prozess viel teurer machen. 2. Oder indem Sie den deQueue-Prozess viel teurer machen

https://www.geeksforgeeks.org/queue-using-stacks/

Ein wichtiger Weg, den ich aus dem obigen Beitrag herausgefunden habe, war das Erstellen einer Warteschlange mit nur der Stapeldatenstruktur und dem Rekursionsaufrufstapel.

Man kann zwar argumentieren, dass buchstäblich immer noch zwei Stapel verwendet werden, aber im Idealfall wird nur eine Stapeldatenstruktur verwendet.

Nachfolgend finden Sie die Erklärung des Problems:

  1. Deklarieren Sie einen einzelnen Stapel zum Aktivieren und Deaktivieren der Daten und verschieben Sie die Daten in den Stapel.

  2. Während deQueueing eine Grundbedingung hat, bei der das Element des Stapels eingeblendet wird, wenn die Größe des Stapels 1 beträgt. Dadurch wird sichergestellt, dass während der deQueue-Rekursion kein Stapelüberlauf auftritt.

  3. Während des DeQueueing werden zuerst die Daten vom oberen Rand des Stapels eingeblendet. Idealerweise ist dieses Element das Element, das sich oben auf dem Stapel befindet. Rufen Sie nun rekursiv die Funktion deQueue auf und schieben Sie das oben platzierte Element zurück in den Stapel.

Der Code sieht wie folgt aus:

if (s1.isEmpty())
System.out.println("The Queue is empty");
        else if (s1.size() == 1)
            return s1.pop();
        else {
            int x = s1.pop();
            int result = deQueue();
            s1.push(x);
            return result;

Auf diese Weise können Sie eine Warteschlange mithilfe einer einzelnen Stack-Datenstruktur und des Rekursionsaufrufstapels erstellen.

Radioaktiv
quelle
1

Unten finden Sie die Lösung in Javascript-Sprache mit ES6-Syntax.

Stack.js

//stack using array
class Stack {
  constructor() {
    this.data = [];
  }

  push(data) {
    this.data.push(data);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }

  size(){
    return this.data.length;
  }
}

export { Stack };

QueueUsingTwoStacks.js

import { Stack } from "./Stack";

class QueueUsingTwoStacks {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }

  enqueue(data) {
    this.stack1.push(data);
  }

  dequeue() {
    //if both stacks are empty, return undefined
    if (this.stack1.size() === 0 && this.stack2.size() === 0)
      return undefined;

    //if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
    if (this.stack2.size() === 0) {
      while (this.stack1.size() !== 0) {
        this.stack2.push(this.stack1.pop());
      }
    }

    //pop and return the element from stack 2
    return this.stack2.pop();
  }
}

export { QueueUsingTwoStacks };

Unten ist die Verwendung:

index.js

import { StackUsingTwoQueues } from './StackUsingTwoQueues';

let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");

console.log(que.dequeue());  //output: "A"
Jyoti Prasad Pal
quelle
Das ist fehlerhaft. Wenn Sie nach dem Entreihen weitere Elemente in die Warteschlange stellen, werden diese eingefügt stack1. Wenn Sie erneut zu gehen dequeue, verschieben Sie sie in Elemente stack2und stellen sie vor das, was bereits vorhanden war.
Alexander - Reinstate Monica
0

Ich werde diese Frage in Go beantworten, da Go nicht viele Sammlungen in seiner Standardbibliothek hat.

Da ein Stack sehr einfach zu implementieren ist, dachte ich, ich würde versuchen, zwei Stacks zu verwenden, um eine Warteschlange mit zwei Enden zu erstellen. Um besser zu verstehen, wie ich zu meiner Antwort gekommen bin, habe ich die Implementierung in zwei Teile geteilt. Der erste Teil ist hoffentlich leichter zu verstehen, aber unvollständig.

type IntQueue struct {
    front       []int
    back        []int
}

func (q *IntQueue) PushFront(v int) {
    q.front = append(q.front, v)
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[0]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        q.back = q.back[1:]
    }
}

func (q *IntQueue) PushBack(v int) {
    q.back = append(q.back, v)
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[0]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        q.front = q.front[1:]
    }
}

Es sind im Grunde zwei Stapel, bei denen wir zulassen, dass der Boden der Stapel voneinander manipuliert wird. Ich habe auch die STL-Namenskonventionen verwendet, bei denen die traditionellen Push-, Pop- und Peek-Operationen eines Stapels ein Front / Back-Präfix haben, unabhängig davon, ob sie sich auf die Vorder- oder Rückseite der Warteschlange beziehen.

Das Problem mit dem obigen Code ist, dass er den Speicher nicht sehr effizient nutzt. Tatsächlich wächst es endlos, bis Ihnen der Platz ausgeht. Das ist wirklich schlimm. Die Lösung hierfür besteht darin, den unteren Rand des Stapelbereichs nach Möglichkeit einfach wiederzuverwenden. Wir müssen einen Versatz einführen, um dies zu verfolgen, da ein Slice in Go nach dem Schrumpfen nicht mehr vorne wachsen kann.

type IntQueue struct {
    front       []int
    frontOffset int
    back        []int
    backOffset  int
}

func (q *IntQueue) PushFront(v int) {
    if q.backOffset > 0 {
        i := q.backOffset - 1
        q.back[i] = v
        q.backOffset = i
    } else {
        q.front = append(q.front, v)
    }
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[q.backOffset]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        if len(q.back) > 0 {
            q.backOffset++
        } else {
            panic("Cannot pop front of empty queue.")
        }
    }
}

func (q *IntQueue) PushBack(v int) {
    if q.frontOffset > 0 {
        i := q.frontOffset - 1
        q.front[i] = v
        q.frontOffset = i
    } else {
        q.back = append(q.back, v)
    }
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[q.frontOffset]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        if len(q.front) > 0 {
            q.frontOffset++
        } else {
            panic("Cannot pop back of empty queue.")
        }
    }
}

Es sind viele kleine Funktionen, aber von den 6 Funktionen sind 3 nur Spiegel der anderen.

John Leidegren
quelle
Sie verwenden hier Arrays. Ich sehe nicht, wo deine Stapel sind.
Melpomene
@melpomene OK, wenn Sie genauer hinschauen, werden Sie feststellen, dass die einzigen Operationen, die ich ausführe, das Hinzufügen / Entfernen des letzten Elements im Array sind. Mit anderen Worten, schieben und knallen. Für alle Absichten und Zwecke sind dies Stapel, die jedoch mithilfe von Arrays implementiert werden.
John Leidegren
@melpomene Eigentlich ist das nur halb richtig, ich gehe von doppelendigen Stapeln aus. Ich erlaube, dass der Stapel unter bestimmten Bedingungen auf nicht standardmäßige Weise von unten nach oben geändert wird.
John Leidegren
0

Hier ist meine Lösung in Java mit Linkedlist.

class queue<T>{
static class Node<T>{
    private T data;
    private Node<T> next;
    Node(T data){
        this.data = data;
        next = null;
    }
}
Node firstTop;
Node secondTop;

void push(T data){
    Node temp = new Node(data);
    temp.next = firstTop;
    firstTop = temp;
}

void pop(){
    if(firstTop == null){
        return;
    }
    Node temp = firstTop;
    while(temp != null){
        Node temp1 = new Node(temp.data);
        temp1.next = secondTop;
        secondTop = temp1;
        temp = temp.next;
    }
    secondTop = secondTop.next;
    firstTop = null;
    while(secondTop != null){
        Node temp3 = new Node(secondTop.data);
        temp3.next = firstTop;
        firstTop = temp3;
        secondTop = secondTop.next;
    }
}

}}

Hinweis: In diesem Fall ist der Pop-Vorgang sehr zeitaufwändig. Daher werde ich nicht vorschlagen, eine Warteschlange mit zwei Stapeln zu erstellen.

Irshad ck
quelle
0

Mit O(1) dequeue(), was der Antwort von Pythonquick entspricht :

// time: O(n), space: O(n)
enqueue(x):
    if stack.isEmpty():
        stack.push(x)
        return
    temp = stack.pop()
    enqueue(x)
    stack.push(temp)

// time: O(1)
x dequeue():
    return stack.pop()

Mit O(1) enqueue()(dies wird in diesem Beitrag nicht erwähnt, also diese Antwort), das auch Backtracking verwendet, um das unterste Element in die Luft zu sprudeln und zurückzugeben.

// O(1)
enqueue(x):
    stack.push(x)

// time: O(n), space: O(n)
x dequeue():
    temp = stack.pop()
    if stack.isEmpty():
        x = temp
    else:
        x = dequeue()
        stack.push(temp)
    return x

Offensichtlich ist es eine gute Codierungsübung, da sie ineffizient, aber dennoch elegant ist.

hIpPy
quelle
0

** Einfache JS-Lösung **

  • Hinweis: Ich habe Ideen von anderen Personen kommentiert

/*

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

*/
class myQueue {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    push(item) {
        this.stack1.push(item)
    }

    remove() {
        if (this.stack1.length == 0 && this.stack2.length == 0) {
            return "Stack are empty"
        }

        if (this.stack2.length == 0) {

            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }
        return this.stack2.pop()
    }


    peek() {
        if (this.stack2.length == 0 && this.stack1.length == 0) {
            return 'Empty list'
        }

        if (this.stack2.length == 0) {
            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }

        return this.stack2[0]
    }

    isEmpty() {
        return this.stack2.length === 0 && this.stack1.length === 0;
    }

}

const q = new myQueue();
q.push(1);
q.push(2);
q.push(3);
q.remove()

console.log(q)

ASHISH RANJAN
quelle
-1
public class QueueUsingStacks<T>
{
    private LinkedListStack<T> stack1;
    private LinkedListStack<T> stack2;

    public QueueUsingStacks()
    {
        stack1=new LinkedListStack<T>();
        stack2 = new LinkedListStack<T>();

    }
    public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
    {
        while(source.Head!=null)
        {
            dest.Push(source.Head.Data);
            source.Head = source.Head.Next;
        }
    }
    public void Enqueue(T entry)
    {

       stack1.Push(entry);
    }
    public T Dequeue()
    {
        T obj;
        if (stack2 != null)
        {
            Copy(stack1, stack2);
             obj = stack2.Pop();
            Copy(stack2, stack1);
        }
        else
        {
            throw new Exception("Stack is empty");
        }
        return obj;
    }

    public void Display()
    {
        stack1.Display();
    }


}

Für jede Enqueue-Operation fügen wir oben im Stapel1 hinzu. Für jede Warteschlange leeren wir den Inhalt von Stapel1 in Stapel2 und entfernen das Element oben im Stapel. Die Zeitkomplexität beträgt O (n) für die Warteschlange, da wir den Stapel1 in Stapel2 kopieren müssen. Die zeitliche Komplexität der Warteschlange entspricht der eines regulären Stapels

PradGar
quelle
Dieser Code ist ineffizient (unnötiges Kopieren) und fehlerhaft: if (stack2 != null)ist immer wahr, weil er stack2im Konstruktor instanziiert wird.
Melpomene
-2

Warteschlangenimplementierung mit zwei java.util.Stack-Objekten:

public final class QueueUsingStacks<E> {

        private final Stack<E> iStack = new Stack<>();
        private final Stack<E> oStack = new Stack<>();

        public void enqueue(E e) {
            iStack.push(e);
        }

        public E dequeue() {
            if (oStack.isEmpty()) {
                if (iStack.isEmpty()) {
                    throw new NoSuchElementException("No elements present in Queue");
                }
                while (!iStack.isEmpty()) {
                    oStack.push(iStack.pop());
                }
            }
            return oStack.pop();
        }

        public boolean isEmpty() {
            if (oStack.isEmpty() && iStack.isEmpty()) {
                return true;
            }
            return false;
        }

        public int size() {
            return iStack.size() + oStack.size();
        }

}
realPK
quelle
3
Dieser Code ist funktional identisch mit der Antwort von Dave L. Er fügt nichts Neues hinzu, nicht einmal eine Erklärung.
Melpomene
Es werden die Methoden isEmpty () und size () zusammen mit der grundlegenden Ausnahmebehandlung hinzugefügt. Ich werde bearbeiten, um eine Erklärung hinzuzufügen.
RealPK
1
Niemand fragte , für diese zusätzliche Methoden, und sie sind trivial (jeweils eine Zeile): return inbox.isEmpty() && outbox.isEmpty()und return inbox.size() + outbox.size(), respectively. Der Code von Dave L. löst bereits eine Ausnahme aus, wenn Sie sich aus einer leeren Warteschlange entfernen. Die ursprüngliche Frage betraf nicht einmal Java. Es ging um Datenstrukturen / Algorithmen im Allgemeinen. Die Java-Implementierung war nur eine zusätzliche Illustration.
Melpomene
1
Dies ist eine großartige Quelle für Leute, die verstehen möchten, wie man eine Warteschlange aus zwei Stapeln erstellt. Die Diagramme haben mir definitiv mehr geholfen, als Daves Antwort zu lesen.
Kemal Tezer Dilsiz
@melpomene: Es geht nicht darum, dass Methoden trivial sind, sondern notwendig. Die Warteschlangenschnittstelle in Java erweitert diese Methoden von der Sammlungsschnittstelle, da sie benötigt werden.
RealPK