it-swarm-eu.dev

Wie implementiere ich eine Warteschlange mit zwei Stapeln?

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

Ist es möglich, eine Warteschlangendatenstruktur nur unter Verwendung der beiden Stapel zu "konstruieren"?

362
Nitin

Behalten Sie 2 Stapel, nennen wir sie inbox und outbox.

Enqueue :

  • Schieben Sie das neue Element auf inbox.

Dequeue :

  • Wenn outbox leer ist, füllen Sie jedes Element aus inbox und schieben Sie es auf outbox.

  • Pope und gib das oberste Element aus outbox zurück

Bei Verwendung dieser Methode befindet sich jedes Element genau einmal in jedem Stapel. Dies bedeutet, dass jedes Element zweimal gedrückt und zweimal geknackt wird, wodurch amortisierte Vorgänge mit konstanter Zeit erfolgen.

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

}
665
Dave L.

A - Wie storniere ich einen Stapel?

Um zu verstehen, wie eine Warteschlange mit zwei Stapeln erstellt wird, sollten Sie wissen, wie ein Stack-Crystal-Clear rückgängig gemacht wird. 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 zuerst O ut bezeichnet wird (LIFO) in der Informatik.

Stellen wir uns unseren Stapel wie eine Flasche vor;

 enter image description here

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

 enter image description here

Nun haben wir unseren Stapel als Flasche dargestellt mit Werten von 3,2,1. Und wir wollen den Stapel umkehren, so dass das oberste Element des Stapels 1 und das unterste Element des Stapels 3 ist. Was können wir tun? Wir können die Flasche nehmen und auf den Kopf stellen, damit sich alle Werte umkehren sollten?

 enter image description here

Ja, das können wir, aber das ist eine Flasche. Um den gleichen Vorgang auszuführen, benötigen wir einen zweiten Stapel, der die ersten Stapelelemente in umgekehrter Reihenfolge speichern soll. Lassen Sie uns unseren bestückten Stapel nach links und unseren neuen leeren Stapel nach rechts stellen. Um die Reihenfolge der Elemente umzukehren, wird jedes Element aus dem linken Stapel gezogen und zum rechten Stapel verschoben. Sie können auf dem Bild unten sehen, was passiert.

 enter image description here

Wir wissen also, wie man einen Stapel umkehrt.

B - Verwenden von zwei Stapeln als Warteschlange

Im vorigen Teil habe ich erklärt, wie wir die Reihenfolge der Stack-Elemente umkehren können. Dies war wichtig, denn wenn wir Elemente in den Stapel verschieben und platzieren, erfolgt die Ausgabe genau in umgekehrter Reihenfolge einer Warteschlange. Wenn wir uns ein Beispiel vorstellen, verschieben wir das Array der Ganzzahlen {1, 2, 3, 4, 5} auf einen Stapel. Wenn wir die Elemente platzieren und drucken, bis der Stapel leer ist, erhalten Sie das Array in umgekehrter Reihenfolge der Reihenfolge. Dies ist {5, 4, 3, 2, 1} Die Ausgabe wird {1, 2, 3, 4, 5} sein. Es ist daher offensichtlich, dass die Ausgabe der Warteschlange für die gleiche Eingabereihenfolge der Elemente genau die Ausgabe eines Stapels ist. 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 Stack wird für die enqueue-Operation verwendet (Stack # 1 links wird als Input Stack bezeichnet), ein anderer Stack wird für die dequeue-Operation verwendet (Stack # 2 rechts wird als Output Stack bezeichnet). Schauen Sie sich das Bild unten an.

 enter image description here

Unser Pseudo-Code lautet wie folgt;


Enqueue-Vorgang

Push every input element to the Input Stack

Dequeue-Operation

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 {1, 2, 3} einreihen. Ganzzahlen werden auf den Input Stack (Stack # 1) verschoben, der sich links befindet.

 enter image description here

Was passiert dann, wenn wir eine Dequeue-Operation ausführen? Immer wenn eine Warteschlangenoperation 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 über die Elemente der Ausgabe extrahiert des Eingangsstapels wird umgekehrt. Bevor Sie einen Wert zurückgeben, ist der Status der Warteschlange wie folgt.

 enter image description here

Überprüfen Sie die Reihenfolge der Elemente im Ausgabestapel (Stapel Nr. 2). Es ist offensichtlich, dass wir die Elemente aus dem Ausgabestapel entfernen können, so dass die Ausgabe dieselbe ist, als wären wir aus einer Warteschlange entfernt worden. Wenn wir also zwei Dequeue-Operationen ausführen, erhalten wir zuerst {1, 2}. Dann ist Element 3 das einzige Element des Ausgabestapels, und der Eingabestapel ist leer. Wenn wir die Elemente 4 und 5 einreihen, wird der Zustand der Warteschlange wie folgt sein:

 enter image description here

Nun ist der Ausgabestapel nicht leer, und wenn wir eine Warteschlangenoperation ausführen, werden nur 3 aus dem Ausgabestapel herausgenommen. Dann wird der Staat als unten betrachtet;

 enter image description here

Wenn wir zwei weitere Entqueue-Operationen ausführen, prüft die Warteschlange beim ersten Entqueue-Vorgang, ob der Ausgabestapel leer ist, was wahr ist. Entpacken Sie dann die Elemente des Eingabestapels und verschieben Sie sie in den Ausgabestapel, bis der Eingabestapel leer ist. Der Zustand der Warteschlange ist dann wie folgt.

 enter image description here

Es ist leicht zu sehen, dass die Ausgabe der beiden Entnahmeoperationen {4, 5} ist.

C - Implementierung einer Warteschlange mit zwei Stapeln

Hier ist eine Implementierung in Java. Ich werde die vorhandene Implementierung von Stack nicht verwenden, also wird das Rad hier neu erfunden;

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
185

Sie können sogar eine Warteschlange mit nur einem Stapel simulieren. Der zweite (temporäre) Stack kann durch den Aufrufstack von rekursiven Aufrufen der Insert-Methode simuliert werden. 

Das Prinzip bleibt dasselbe, wenn ein neues Element in die Warteschlange eingefügt wird: 

  • Sie müssen Elemente von einem Stapel auf einen anderen temporären Stapel übertragen, um ihre Reihenfolge umzukehren. 
  • Schieben Sie dann das neue Element, das eingefügt werden soll, 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 wird es geknackt).

Eine Warteschlangenklasse, die nur einen Stack 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();
    }
}
79
pythonquick

Die zeitlichen Komplexitäten wären jedoch schlimmer. Eine gute Warteschlangenimplementierung führt alles in konstanter Zeit aus.

Bearbeiten

Ich weiß nicht, warum meine Antwort hier abgelehnt wurde. Wenn wir programmieren, legen wir Wert auf Zeitkomplexität. 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 abzusprechen, würde ich gerne wissen, warum.

Etwas ausführlicher: Warum zwei Stacks schlechter sind als nur eine Warteschlange: Wenn Sie zwei Stacks verwenden und jemand die Warteschlange ruft, während der Postausgang leer ist, benötigen Sie eine lineare Zeit, um zum Posteingang zu gelangen ( wie man in Daves Code sehen kann.

Sie können eine Warteschlange als einfach verknüpfte Liste implementieren (jedes Element zeigt auf das als nächstes eingefügte Element), indem Sie einen zusätzlichen Zeiger auf das zuletzt eingefügte Element für Pushs (oder eine zyklische Liste) halten. Die Implementierung von Warteschlangen und Warteschlangen für diese Datenstruktur ist sehr einfach in konstanten Zeiten durchzuführen. Das ist im ungünstigsten Fall eine konstante Zeit, nicht amortisiert. Und da die Kommentare nach dieser Klarstellung zu fragen scheinen, ist die konstante Zeit im Worst-Case strikt besser als die amortisierte konstante Zeit.

11
Tyler

Die Warteschlange soll q sein, und die zum Implementieren von q verwendeten Stapel sind stack1 und stack2. 

q kann auf zwei Arten implementiert werden:

Methode 1 (durch aufwändige EnQueue-Operation)}

Diese Methode stellt sicher, dass sich das neu eingegebene Element immer an oberster Stelle von Stapel 1 befindet, sodass die deQueue-Operation nur aus Stapel1 hervorgeht. Um das Element auf Stack1 zu setzen, wird Stack2 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 (DeQueue-Vorgang kostspielig machen)

Bei dieser Methode wird das neue Element in der Warteschlangenoperation oben in stack1 eingegeben. Wenn in der Warteschlangenoperation stapel2 leer ist, werden alle Elemente zu 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 deQueue-Operation) die Elemente einmal verschiebt und Elemente nur verschiebt, wenn stack2 leer ist.

7
Rahul Gandhi

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

Sie müssen alles vom ersten Stapel entfernen, um das untere Element zu erhalten. Legen Sie sie dann für jede "Dequeue" -Operation auf den zweiten Stapel zurück.

2
user11055

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

Zwei Stapel in der Warteschlange sind als definiert stack1 und stack2.

Enqueue: Die euqueued-Elemente werden immer in gedrückt stack1

Dequeue: Die Oberseite von stack2 kann ausgefahren werden, da es das erste Element ist, das in die Warteschlange eingefügt wird stack2 ist nicht leer. Wann stack2 ist leer, wir schlagen alle Elemente aus stack1 und schieben Sie sie hinein stack2 Einer nach dem anderen. Das erste Element in einer Warteschlange wird in den unteren Bereich von verschoben stack1. Es kann direkt nach dem Popping- und Push-Vorgang ausgefahren werden, da es sich oben befindet stack2.

Folgendes ist derselbe 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 wird aus meinem Blog ausgeliehen. Eine ausführlichere Analyse mit Schritt-für-Schritt-Betriebssimulationen finden Sie auf meiner Blog-Webseite.

2
Harry He
// 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();

        }
    }
1
imvp

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()!)
            }
        }
    }
}
1
davejlin

Sie erhalten zwar eine Menge Posts, die sich auf die Implementierung einer Warteschlange mit zwei Stapeln beziehen: 1. Entweder indem Sie den enQueue-Prozess viel kostspieliger gestalten 2. Oder indem Sie den DeQueue-Prozess wesentlich teurer machen

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

Eine wichtige Methode, die ich aus dem obigen Beitrag herausfand, war das Erstellen einer Warteschlange mit nur der Stapeldatenstruktur und dem Rekursionsaufrufstapel.

Man kann argumentieren, dass dies buchstäblich immer noch zwei Stapel verwendet, im Idealfall jedoch nur eine Stapeldatenstruktur.

Unten ist die Erklärung des Problems:

  1. Deklarieren Sie einen einzelnen Stack zum EnQueuing und DeQueing der Daten und legen Sie die Daten in den Stack ab.

  2. deQueueing hat eine Basisbedingung, bei der das Element des Stapels eingeblendet wird, wenn der Stapel 1 ist. Dadurch wird sichergestellt, dass während der DeQueue-Rekursion kein Stapelüberlauf auftritt.

  3. Beim DeQueueing werden die Daten zuerst vom Stapel oben angezeigt. Idealerweise ist dieses Element das Element, das sich oben im Stapel befindet. Sobald dies geschehen ist, rufen Sie die Funktion deQueue rekursiv auf und schieben Sie das Element, das oben angezeigt wurde, 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 mit einer einzelnen Stack-Datenstruktur und dem Rekursions-Call-Stack erstellen.

1
Radioactive

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. Ich schlage also nicht vor, eine Warteschlange mit zwei Stapeln zu erstellen. 

0
Irshad ck

Ich beantworte diese Frage in Go, da Go nicht viele Sammlungen in seiner Standardbibliothek enthält.

Da ein Stapel sehr einfach zu implementieren ist, dachte ich, ich würde versuchen, zwei Stapel zu verwenden, um eine doppelseitige Warteschlange zu erreichen. Um besser zu verstehen, wie ich zu meiner Antwort gekommen bin, habe ich die Implementierung in zwei Teile aufgeteilt. Der erste Teil ist hoffentlich einfacher 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:]
    }
}

Im Grunde handelt es sich um zwei Stapel, bei denen die Unterseite der Stapel von einander manipuliert werden kann. Ich habe auch die STL-Namenskonventionen verwendet, bei denen die traditionellen Push-, Pop- und Peek-Operationen eines Stapels mit einem Vor/Zurück-Präfix versehen sind, unabhängig davon, ob sie sich auf die Vorder- oder Rückseite der Warteschlange beziehen.

Das Problem mit dem obigen Code ist, dass der Speicher nicht sehr effizient genutzt wird. Tatsächlich wächst es endlos, bis Sie keinen Platz mehr haben. Das ist wirklich schlimm. Um dieses Problem zu beheben, verwenden Sie einfach den unteren Teil des Stapelspeichers, wann immer dies möglich ist. Wir müssen einen Versatz einführen, um dies zu verfolgen, da ein Abschnitt in Go nicht in der Front wachsen kann, wenn er einmal geschrumpft ist.

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 gibt viele kleine Funktionen, aber von den 6 Funktionen sind 3 nur Spiegel der anderen.

0
John Leidegren

Nachfolgend finden Sie die Lösung in Javascript 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"
0
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 den Stack1 hinzu. Für jeden Dequeue leeren wir den Inhalt von stack1 in stack2 und entfernen das Element am oberen Rand des Stapels. Die Komplexität der Zeit ist O(n) für dequeue, da wir den stack1 nach stack2 kopieren müssen. Die zeitliche Komplexität von Enqueue ist dieselbe wie bei einem regulären Stack

0
PradGar

Mit O(1)dequeue(), das ist identisch mit Pythonquicks answer :

// 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, daher diese Antwort), die auch Backtracking verwendet, um das unterste Element aufzurufen.

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

Natürlich ist es eine gute Kodierungsübung, da es ineffizient ist, aber dennoch elegant ist.

0
hIpPy