Załóżmy, że mamy dwa stosy i żadnej innej zmiennej tymczasowej.

Czy możliwe jest „skonstruowanie” struktury danych kolejki przy użyciu tylko dwóch stosów?

Zachowaj 2 stosy, nazwijmy je inboxi outbox.

Kolejkuj :

• Wciśnij nowy element na inbox

Dequeue :

• Jeśli outboxjest pusty, uzupełnij go, wyskakując z każdego elementu inboxi popychając gooutbox

• Pop i zwróć najwyższy element z outbox

Korzystając z tej metody, każdy element znajdzie się w każdym stosie dokładnie jeden raz - co oznacza, że ​​każdy element zostanie popchnięty dwa razy i wyskakiwany dwukrotnie, dając zamortyzowane operacje o stałym czasie.

Oto implementacja w Javie:

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

}

A - Jak odwrócić stos

Aby zrozumieć, jak zbudować kolejkę przy użyciu dwóch stosów, powinieneś zrozumieć, jak odwrócić stos krystalicznie czysty. Pamiętaj, jak działa stos, jest bardzo podobny do stosu naczyń w kuchni. Ostatni myte naczynia będzie na górze stosu czystą, co nazywa się L AST I N F IRST O UT (LIFO) w informatyce.

Wyobraźmy sobie nasz stos jak butelkę jak poniżej;

Jeśli popchniemy odpowiednio liczby całkowite 1,2,3, wówczas 3 będzie na górze stosu. Ponieważ 1 zostanie popchnięty jako pierwszy, następnie 2 zostaną umieszczone na górze 1. Na koniec 3 zostaną umieszczone na górze stosu, a najnowszy stan naszego stosu przedstawiony jako butelka będzie wyglądał jak poniżej;

Teraz mamy nasz stos reprezentowany jako butelka wypełniona wartościami 3,2,1. I chcemy odwrócić stos, aby górny element stosu wynosił 1, a dolny element stosu wynosił 3. Co możemy zrobić? Możemy wziąć butelkę i trzymać ją do góry nogami, aby wszystkie wartości odwróciły się w kolejności?

Tak, możemy to zrobić, ale to jest butelka. Aby wykonać ten sam proces, musimy mieć drugi stos, który będzie przechowywać pierwsze elementy stosu w odwrotnej kolejności. Umieśćmy nasz zaludniony stos po lewej, a nasz nowy pusty stos po prawej. Aby odwrócić kolejność elementów, wyskakujemy z każdego elementu z lewego stosu i popychamy je do prawego stosu. Możesz zobaczyć, co się dzieje, kiedy to robimy, na poniższym obrazku;

Wiemy więc, jak odwrócić stos.

B - Używanie dwóch stosów jako kolejki

W poprzedniej części wyjaśniłem, w jaki sposób możemy odwrócić kolejność elementów stosu. Było to ważne, ponieważ jeśli popchniemy i pop elementy do stosu, dane wyjściowe będą dokładnie w odwrotnej kolejności w kolejce. Myśląc o przykładzie, pchnijmy tablicę liczb całkowitych {1, 2, 3, 4, 5}na stos. Jeśli wstawimy elementy i wydrukujemy je, aż stos będzie pusty, otrzymamy tablicę w odwrotnej kolejności wypychania, co będzie {5, 4, 3, 2, 1}Zapamiętaj, że dla tego samego wejścia, jeśli usuniemy kolejkę z kolejki, aż kolejka będzie pusta, wynik będzie {1, 2, 3, 4, 5}. Jest więc oczywiste, że dla tej samej kolejności wprowadzania elementów wynik kolejki jest dokładnie odwrotny niż wynik stosu. Ponieważ wiemy, jak odwrócić stos przy użyciu dodatkowego stosu, możemy zbudować kolejkę przy użyciu dwóch stosów.

Nasz model kolejek będzie składał się z dwóch stosów. Jeden stos zostanie użyty do enqueueoperacji (stos nr 1 po lewej stronie, będzie nazywany jako stos wejściowy), inny stos zostanie użyty do dequeueoperacji (stos nr 2 po prawej, będzie nazywany stosem wyjściowym). Sprawdź obraz poniżej;

Nasz pseudo-kod jest jak poniżej;

Kolejkuj operację

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

Kolejkujmy {1, 2, 3}odpowiednio liczby całkowite . Liczby całkowite będą wypychane na stos wejściowy ( stos nr 1 ), który znajduje się po lewej stronie;

Co stanie się, jeśli wykonamy operację usuwania kolejki? Za każdym razem, gdy wykonywana jest operacja usuwania kolejki, kolejka sprawdzi, czy stos wyjściowy jest pusty, czy nie (patrz pseudo-kod powyżej). Jeśli stos wyjściowy jest pusty, stos wejściowy zostanie wyodrębniony na wyjściu, więc elementy stosu wejściowego zostanie odwrócony. Przed zwróceniem wartości stan kolejki będzie taki jak poniżej;

Sprawdź kolejność elementów w stosie wyjściowym (stos nr 2). Oczywiste jest, że możemy wstawić elementy ze stosu wyjściowego, aby dane wyjściowe były takie same, jakbyśmy usunęli kolejkę z kolejki. Zatem jeśli wykonamy dwie operacje usuwania kolejki, najpierw otrzymamy {1, 2}odpowiednio. Wówczas element 3 będzie jedynym elementem stosu wyjściowego, a stos wejściowy będzie pusty. Jeśli kolejkujemy elementy 4 i 5, wówczas stan kolejki będzie następujący;

Teraz stos wyjściowy nie jest pusty, a jeśli wykonamy operację usuwania kolejki, tylko 3 zostaną wyskakujące ze stosu wyjściowego. Wtedy stan będzie widoczny jak poniżej;

Ponownie, jeśli wykonamy dwie kolejne operacje usuwania z kolejki, podczas pierwszej operacji usuwania z kolejki kolejka sprawdzi, czy stos wyjściowy jest pusty, co jest prawdą. Następnie wyskakuj z elementów stosu wejściowego i popchnij je do stosu wyjściowego, aż stos wejściowy będzie pusty, a następnie stan kolejki będzie następujący:

Łatwo zauważyć, że wynik dwóch operacji usuwania w kolejce będzie {4, 5}

C - Implementacja kolejki zbudowanej z dwóch stosów

Oto implementacja w Javie. Nie zamierzam używać istniejącej implementacji Stack, więc przykład tutaj wymyśli na nowo koło;

C - 1) Klasa MyStack: prosta implementacja stosu

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) Klasa MyQueue: Implementacja kolejki przy użyciu dwóch stosów

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) Kod demonstracyjny

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) Wyjście próbki

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5

Możesz nawet symulować kolejkę, używając tylko jednego stosu. Drugi (tymczasowy) stos może być symulowany przez stos wywołań rekurencyjnych wywołań metody wstawiania.

Zasada pozostaje taka sama przy wstawianiu nowego elementu do kolejki:

• Musisz przenieść elementy z jednego stosu na inny stos tymczasowy, aby odwrócić ich kolejność.
• Następnie wepchnij nowy element do wstawienia na stos tymczasowy
• Następnie przenieś elementy z powrotem do oryginalnego stosu
• Nowy element będzie na dole stosu, a najstarszy element będzie na wierzchu (najpierw zostanie usunięty)

Klasa kolejki korzystająca tylko z jednego stosu wyglądałaby następująco:

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

Złożoność czasu byłaby jednak gorsza. Dobra implementacja kolejki robi wszystko w stałym czasie.

Edytować

Nie jestem pewien, dlaczego moja odpowiedź została tutaj zanotowana. Jeśli programujemy, dbamy o złożoność czasu, a używanie dwóch standardowych stosów do tworzenia kolejki jest nieefektywne. To bardzo ważny i istotny punkt. Jeśli ktoś jeszcze odczuwa potrzebę dalszego głosowania za tym, chciałbym wiedzieć, dlaczego.

Trochę więcej szczegółów : dlaczego użycie dwóch stosów jest gorsze niż kolejka: jeśli użyjesz dwóch stosów i ktoś wywoła dequeue, gdy skrzynka nadawcza jest pusta, potrzebujesz liniowego czasu, aby dostać się do dolnej części skrzynki odbiorczej (jak widać w kodzie Dave'a).

Możesz zaimplementować kolejkę jako pojedynczo połączoną listę (każdy element wskazuje na następny wstawiany element), zachowując dodatkowy wskaźnik do ostatnio wstawionego elementu dla wypychań (lub tworząc z niego cykliczną listę). Implementowanie kolejki i usuwania z kolejki w tej strukturze danych jest bardzo łatwe do wykonania w stałym czasie. To najgorszy możliwy stały czas, nie amortyzowany. A ponieważ komentarze wydają się prosić o to wyjaśnienie, stały najgorszy przypadek jest zdecydowanie lepszy niż stały zamortyzowany czas.

Niech kolejką do implementacji będzie q, a stosy użyte do implementacji q będą stos1 i stos2.

q można zaimplementować na dwa sposoby:

Metoda 1 (przez uczynienie operacji enQueue kosztowną)

Ta metoda zapewnia, że ​​nowo wprowadzony element zawsze znajduje się na górze stosu 1, dzięki czemu operacja deQueue wyskakuje ze stosu1. Aby umieścić element na górze stosu1, stosuje się stos2.

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.

Metoda 2 (przez uczynienie operacji deQueue kosztowną)

W tej metodzie w operacji kolejkowania nowy element jest wprowadzany na górze stosu1. W operacji usuwania z kolejki, jeśli stos2 jest pusty, wówczas wszystkie elementy są przenoszone na stos2 i na końcu zwracana jest góra stosu2.

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.

Metoda 2 jest zdecydowanie lepsza niż metoda 1. Metoda 1 przenosi wszystkie elementy dwukrotnie w operacji enQueue, podczas gdy metoda 2 (w operacji deQueue) przesuwa elementy raz i przenosi elementy tylko wtedy, gdy stos2 jest pusty.

Rozwiązanie w 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();
    }
}

Dwa stosy w kolejce są zdefiniowane jako stos1 i stos2 .

Kolejka: Wymienione elementy są zawsze wypychane na stos1

Dequeue: Górną część stosu2 można wysunąć, ponieważ jest to pierwszy element wstawiany do kolejki, gdy stos2 nie jest pusty. Kiedy stos2 jest pusty, usuwamy wszystkie elementy ze stosu 1 i pchamy je kolejno do stosu 2 . Pierwszy element w kolejce jest wypychany na spód stosu1 . Można go wyskoczyć bezpośrednio po operacji popping i push, ponieważ znajduje się na górze stosu2 .

Poniższy przykładowy kod C ++:

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

To rozwiązanie zostało zapożyczone z mojego bloga . Bardziej szczegółowa analiza z symulacjami operacji krok po kroku jest dostępna na mojej stronie blogu.

Musisz usunąć wszystko z pierwszego stosu, aby uzyskać dolny element. Następnie umieść je wszystkie z powrotem na drugim stosie dla każdej operacji „usuwania”.

dla programisty c # tutaj jest kompletny program:

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

Zaimplementuj następujące operacje w kolejce, używając stosów.

push (x) - Wciśnij element x na tył kolejki.

pop () - Usuwa element z przodu kolejki.

peek () - Pobierz przedni element.

empty () - Zwraca, czy kolejka jest pusta.

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

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

        }
    }

Implementacja kolejki przy użyciu dwóch stosów w 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()!)
            }
        }
    }
}

Otrzymasz wiele postów związanych z implementacją kolejki z dwoma stosami: 1. Albo przez uczynienie procesu enQueue znacznie droższym 2. Lub przez uczynienie procesu deQueue znacznie droższym

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

Jednym z ważnych sposobów, jakie dowiedziałem się z powyższego postu, było zbudowanie kolejki z samą strukturą danych stosu i stosem wywołań rekurencyjnych.

Chociaż można argumentować, że dosłownie nadal używa dwóch stosów, ale idealnie jest to tylko jedna struktura danych stosu.

Poniżej znajduje się wyjaśnienie problemu:

1. Zadeklaruj pojedynczy stos do enQueuing i deQueing danych i wepchnij dane do stosu.

2. podczas gdy deQueueing ma warunek podstawowy, w którym element stosu jest wyskakujący, gdy rozmiar stosu wynosi 1. Zapewni to, że nie nastąpi przepełnienie stosu podczas rekurencji deQueue.

3. Podczas deQueueing najpierw pop dane z góry stosu. Idealnie ten element będzie elementem znajdującym się na górze stosu. Teraz, gdy to zrobisz, rekurencyjnie wywołaj funkcję deQueue, a następnie wepchnij element wyskakujący powyżej z powrotem do stosu.

Kod będzie wyglądał jak poniżej:

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;

W ten sposób można utworzyć kolejkę przy użyciu struktury danych z jednym stosem i stosu wywołań rekurencyjnych.

Poniżej znajduje się rozwiązanie w języku javascript wykorzystujące składnię ES6.

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

Poniżej jest użycie:

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"

Odpowiem na to pytanie w Go, ponieważ Go nie ma bogatej kolekcji w swojej standardowej bibliotece.

Ponieważ stos jest naprawdę łatwy do wdrożenia, pomyślałem, że spróbuję użyć dwóch stosów, aby uzyskać podwójnie zakończoną kolejkę. Aby lepiej zrozumieć, w jaki sposób doszedłem do mojej odpowiedzi, podzieliłem implementację na dwie części, pierwsza część jest, mam nadzieję, łatwiejsza do zrozumienia, ale jest niepełna.

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:]
    }
}

W zasadzie są to dwa stosy, w których pozwalamy sobie na manipulowanie dnem stosów. Użyłem również konwencji nazewnictwa STL, w której tradycyjne operacje stosu push, pop i peek mają przedrostek przód / tył, niezależnie od tego, czy odnoszą się do przodu, czy do tyłu kolejki.

Problem z powyższym kodem polega na tym, że nie wykorzystuje on bardzo skutecznie pamięci. W rzeczywistości rośnie bez końca, dopóki nie zabraknie ci miejsca. To naprawdę źle. Rozwiązaniem tego problemu jest ponowne użycie dolnej części stosu, gdy tylko jest to możliwe. Musimy wprowadzić przesunięcie, aby to śledzić, ponieważ kawałek Go nie może rosnąć z przodu po zmniejszeniu.

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.")
        }
    }
}

To wiele małych funkcji, ale spośród 6 funkcji 3 z nich są tylko zwierciadłami drugiej.

oto moje rozwiązanie w Javie za pomocą 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;
    }
}

}

Uwaga: w tym przypadku operacja pop jest bardzo czasochłonna. Więc nie będę sugerował tworzenia kolejki przy użyciu dwóch stosów.

Z O(1) dequeue(), co odpowiada odpowiedzi pythonquicka :

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

Z O(1) enqueue()(nie jest to wspomniane w tym poście, więc ta odpowiedź), która również używa cofania, aby utworzyć bąbelki i zwrócić najniższy element.

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

Oczywiście jest to dobre ćwiczenie kodowania, ponieważ jest nieefektywne, ale mimo to eleganckie.

** Łatwe rozwiązanie JS **

• Uwaga: Wziąłem pomysły od komentarzy innych osób

/*

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)

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


}

Do każdej operacji kolejkowania dodajemy na górę stosu1. Przy każdym usuwaniu z kolejki opróżniamy zawartość stosu1 do stosu2 i usuwamy element u góry stosu. Czas złożoności wynosi O (n) dla usuwania z kolejki, ponieważ musimy skopiować stos1 na stos2. złożoność czasowa kolejki jest taka sama jak w przypadku zwykłego stosu

Implementacja kolejki przy użyciu dwóch obiektów java.util.Stack:

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

}