Suponha que tenhamos duas pilhas e nenhuma outra variável temporária.

É possível "construir" uma estrutura de dados da fila usando apenas as duas pilhas?

Mantenha 2 pilhas, vamos chamá-las inboxe outbox.

Enfileirar :

• Empurre o novo elemento para inbox

Retirar da fila :

• Se outboxestiver vazio, reabasteça inboxcolocando cada elemento e empurrando-o paraoutbox

• Pop e retorne o elemento top de outbox

Usando esse método, cada elemento estará em cada pilha exatamente uma vez - o que significa que cada elemento será pressionado duas vezes e exibido duas vezes, fornecendo operações de tempo constante amortizadas.

Aqui está uma implementação em 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();
    }

}

A - Como reverter uma pilha

Para entender como construir uma fila usando duas pilhas, você deve entender como reverter uma pilha cristalina. Lembre-se de como a pilha funciona, é muito semelhante à pilha de pratos da sua cozinha. O último prato lavado estará no topo da pilha limpo, o que é chamado como L ast eu n F irst O ut (LIFO) em informática.

Vamos imaginar nossa pilha como uma garrafa como abaixo;

Se pressionarmos os números inteiros 1,2,3, respectivamente, então 3 estará no topo da pilha. Como 1 será pressionado primeiro, depois 2 serão colocados no topo de 1. Por fim, 3 serão colocados no topo da pilha e o estado mais recente da nossa pilha representado como uma garrafa será como abaixo;

Agora temos nossa pilha representada como uma garrafa é preenchida com valores 3,2,1. E queremos inverter a pilha para que o elemento superior da pilha seja 1 e o elemento inferior da pilha seja 3. O que podemos fazer? Podemos pegar a garrafa e segurá-la de cabeça para baixo, para que todos os valores sejam revertidos em ordem?

Sim, podemos fazer isso, mas isso é uma garrafa. Para fazer o mesmo processo, precisamos ter uma segunda pilha que armazene os primeiros elementos da pilha na ordem inversa. Vamos colocar nossa pilha preenchida à esquerda e nossa nova pilha vazia à direita. Para inverter a ordem dos elementos, vamos exibir cada elemento da pilha esquerda e empurrá-los para a pilha direita. Você pode ver o que acontece como fazemos na imagem abaixo;

Então, sabemos como reverter uma pilha.

B - Usando duas pilhas como uma fila

Na parte anterior, expliquei como podemos reverter a ordem dos elementos da pilha. Isso foi importante, porque se empurrarmos e colocarmos elementos na pilha, a saída será exatamente na ordem inversa de uma fila. Pensando em um exemplo, vamos enviar a matriz de números inteiros {1, 2, 3, 4, 5}para uma pilha. Se popularmos os elementos e os imprimirmos até que a pilha esteja vazia, obteremos a matriz na ordem inversa da ordem de envio, que será {5, 4, 3, 2, 1}lembre-se de que, para a mesma entrada, se retirarmos a fila da fila até que a fila esteja vazia, a saída será {1, 2, 3, 4, 5}. Portanto, é óbvio que, para a mesma ordem de entrada de elementos, a saída da fila é exatamente o inverso da saída de uma pilha. Como sabemos como reverter uma pilha usando uma pilha extra, podemos construir uma fila usando duas pilhas.

Nosso modelo de fila consistirá em duas pilhas. Uma pilha será usada para enqueueoperação (a pilha nº 1, à esquerda, será chamada como Pilha de Entrada), outra pilha será usada para a dequeueoperação (a pilha nº 2, à direita, será chamada como Pilha de Saída). Veja a imagem abaixo;

Nosso pseudo-código é como abaixo;

Operação de enfileiramento

Push every input element to the Input Stack

Operação de desenfileiramento

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

Vamos enfileirar os números inteiros, {1, 2, 3}respectivamente. Os números inteiros serão pressionados na pilha de entrada ( pilha nº 1 ), localizada à esquerda;

Então, o que acontecerá se executarmos uma operação de desenfileiramento? Sempre que uma operação de desenfileiramento é executada, a fila verifica se a pilha de saída está vazia ou não (consulte o pseudocódigo acima) Se a pilha de saída estiver vazia, a pilha de entrada será extraída na saída para que os elementos Pilha de entrada será revertida. Antes de retornar um valor, o estado da fila será o seguinte;

Confira a ordem dos elementos na pilha de saída (pilha 2). É óbvio que podemos exibir os elementos da pilha de saída para que a saída seja a mesma que se desenfileirássemos de uma fila. Assim, se executarmos duas operações de desenfileiramento, primeiro obteremos {1, 2}respectivamente. O elemento 3 será o único elemento da pilha de saída e a pilha de entrada ficará vazia. Se enfileirarmos os elementos 4 e 5, o estado da fila será o seguinte;

Agora a pilha de saída não está vazia e, se executarmos uma operação de desenfileiramento, apenas 3 serão salvas da pilha de saída. Então o estado será visto como abaixo;

Novamente, se executarmos mais duas operações de desenfileiramento, na primeira operação de desenfileiramento, a fila verificará se a pilha de saída está vazia, o que é verdadeiro. Em seguida, retire os elementos da pilha de entrada e empurre-os para a pilha de saída até que a pilha de entrada esteja vazia; o estado da fila será o seguinte;

Fácil de ver, a saída das duas operações de desenfileiramento será {4, 5}

C - Implementação da fila construída com duas pilhas

Aqui está uma implementação em Java. Não vou usar a implementação existente do Stack, por isso o exemplo aqui vai reinventar a roda;

C - 1) Classe MyStack: Uma Implementação Simples de Pilha

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) Classe MyQueue: Implementação de Filas Usando Duas Pilhas

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) Código Demo

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) Saída de amostra

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

Você pode até simular uma fila usando apenas uma pilha. A segunda pilha (temporária) pode ser simulada pela pilha de chamadas recursivas para o método de inserção.

O princípio permanece o mesmo ao inserir um novo elemento na fila:

• Você precisa transferir elementos de uma pilha para outra pilha temporária, para reverter sua ordem.
• Em seguida, empurre o novo elemento a ser inserido na pilha temporária
• Em seguida, transfira os elementos de volta para a pilha original
• O novo elemento estará na parte inferior da pilha e o elemento mais antigo estará em cima (o primeiro a ser exibido)

Uma classe Queue usando apenas uma pilha seria a seguinte:

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

As complexidades do tempo seriam piores, no entanto. Uma boa implementação de fila faz tudo em tempo constante.

Editar

Não sei por que minha resposta foi votada aqui. Se programarmos, nos preocupamos com a complexidade do tempo, e o uso de duas pilhas padrão para criar uma fila é ineficiente. É um ponto muito válido e relevante. Se alguém sentir mais a necessidade de diminuir o voto, eu estaria interessado em saber o porquê.

Um pouco mais de detalhe : por que usar duas pilhas é pior do que apenas uma fila: se você usa duas pilhas e alguém chama de desenfileirar enquanto a caixa de saída está vazia, você precisa de tempo linear para chegar ao fundo da caixa de entrada (como você pode ver no código de Dave).

Você pode implementar uma fila como uma lista vinculada individualmente (cada elemento aponta para o próximo elemento inserido), mantendo um ponteiro extra para o último elemento inserido para envio (ou transformando-o em uma lista cíclica). Implementar fila e desenfileirar nessa estrutura de dados é muito fácil de executar em tempo constante. Esse é o pior caso, tempo constante, não amortizado. E, como os comentários parecem pedir esse esclarecimento, o tempo constante do pior caso é estritamente melhor que o tempo constante amortizado.

Seja q a fila a ser implementada e as pilhas usadas para implementar q sejam pilha1 e pilha2.

q pode ser implementado de duas maneiras:

Método 1 (tornando a operação enQueue cara)

Este método garante que o elemento recém-inserido esteja sempre no topo da pilha 1, para que a operação deQueue saia da pilha1. Para colocar o elemento no topo da pilha1, a pilha2 é usada.

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.

Método 2 (tornando a operação deQueue cara)

Nesse método, na operação em fila, o novo elemento é inserido na parte superior da pilha1. Na operação de remoção da fila, se a pilha2 estiver vazia, todos os elementos serão movidos para a pilha2 e, finalmente, o topo da pilha2 será retornado.

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.

O método 2 é definitivamente melhor que o método 1. O método 1 move todos os elementos duas vezes na operação enQueue, enquanto o método 2 (na operação deQueue) move os elementos uma vez e move os elementos apenas se a pilha2 estiver vazia.

Uma solução em 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();
    }
}

Duas pilhas na fila são definidas como pilha1 e pilha2 .

Enfileirar: os elementos em fila são sempre empurrados para a pilha1

Retirar da fila: A parte superior da pilha2 pode ser removida , pois é o primeiro elemento inserido na fila quando a pilha2 não está vazia. Quando a pilha2 está vazia, exibimos todos os elementos da pilha1 e os empurramos para a pilha2, um por um. O primeiro elemento de uma fila é colocado na parte inferior da pilha1 . Ele pode ser destacado diretamente após operações de popping e push, uma vez que está no topo da pilha2 .

A seguir está o mesmo código de exemplo 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;
}

Esta solução é emprestada do meu blog . Uma análise mais detalhada com simulações de operação passo a passo está disponível na página do meu blog.

Você precisará extrair tudo da primeira pilha para obter o elemento inferior. Em seguida, coloque-os de volta na segunda pilha para cada operação de "desenfileirar".

para desenvolvedor de c #, aqui está o programa completo:

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

Implemente as seguintes operações de uma fila usando pilhas.

push (x) - empurre o elemento x para o fundo da fila.

pop () - Remove o elemento da frente da fila.

peek () - Pega o elemento da frente.

empty () - Retorna se a fila está vazia.

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

        }
    }

Uma implementação de uma fila usando duas pilhas no 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()!)
            }
        }
    }
}

Embora você receba muitas postagens relacionadas à implementação de uma fila com duas pilhas: 1. Tornando o processo enQueue muito mais caro 2. Ou tornando o processo deQueue muito mais caro

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

Uma maneira importante que descobri no post acima foi construir a fila com apenas a estrutura de dados da pilha e a pilha de chamadas de recursão.

Embora se possa argumentar que literalmente isso ainda está usando duas pilhas, mas, idealmente, isso está usando apenas uma estrutura de dados da pilha.

Abaixo está a explicação do problema:

1. Declare uma única pilha para enQueuing e deQueing os dados e envie-os para a pilha.

2. enquanto o deQueueing possui uma condição básica em que o elemento da pilha é exibido quando o tamanho da pilha é 1. Isso garantirá que não haja excesso de pilha durante a recursão do deQueue.

3. Enquanto o DeQueueing, primeiro pop, os dados do topo da pilha. Idealmente, esse elemento será o elemento que está presente no topo da pilha. Agora que isso for feito, chame recursivamente a função deQueue e empurre o elemento exibido acima de volta para a pilha.

O código será semelhante abaixo:

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;

Dessa forma, você pode criar uma fila usando uma única estrutura de dados da pilha e a pilha de chamadas de recursão.

Abaixo está a solução na linguagem javascript usando a sintaxe 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 };

Abaixo está o uso:

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"

Responderei a essa pergunta no Go porque o Go não possui muitas coleções em sua biblioteca padrão.

Como uma pilha é realmente fácil de implementar, pensei em tentar usar duas pilhas para realizar uma fila dupla. Para entender melhor como cheguei à minha resposta, dividi a implementação em duas partes, espero que a primeira parte seja mais fácil de entender, mas está incompleta.

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

São basicamente duas pilhas onde nós permitimos que o fundo das pilhas seja manipulado um pelo outro. Também usei as convenções de nomenclatura STL, nas quais as operações tradicionais push, pop, peek de uma pilha têm um prefixo de frente / verso, quer se refiram à frente ou atrás da fila.

O problema com o código acima é que ele não usa a memória com muita eficiência. Na verdade, cresce infinitamente até você ficar sem espaço. Isso é muito ruim. A correção para isso é simplesmente reutilizar a parte inferior do espaço da pilha sempre que possível. Temos que introduzir um deslocamento para rastrear isso, pois uma fatia no Go não pode crescer na frente depois que ela encolher.

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

São muitas funções pequenas, mas das 6 funções, 3 delas são apenas espelhos da outra.

Aqui está a minha solução em java usando o linklist.

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

}

Nota: Nesse caso, a operação pop consome muito tempo. Portanto, não vou sugerir a criação de uma fila usando duas pilhas.

With O(1) dequeue(), que é o mesmo que a resposta do pythonquick :

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

Com O(1) enqueue()(isso não é mencionado neste post, portanto, esta resposta), que também usa o retorno para fazer bolhas e retornar o item mais baixo.

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

Obviamente, é um bom exercício de codificação, pois é ineficiente, mas elegante.

** Solução JS fácil **

• Nota: tirei ideias de outras pessoas comentando

/*

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


}

Para cada operação de enfileiramento, adicionamos ao topo da pilha1. Para cada desenfileiramento, esvaziamos o conteúdo da pilha1 na pilha2 e removemos o elemento na parte superior da pilha. A complexidade de tempo é O (n) para desenfileirar, pois precisamos copiar a pilha1 para a pilha2. A complexidade temporal do enfileiramento é igual a uma pilha comum

Implementação de fila usando dois objetos 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();
        }

}