it-swarm-pt.tech

Como implementar uma fila usando duas pilhas?

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

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

362
Nitin

Mantenha 2 stacks, vamos chamá-los de inbox e outbox.

Enfileirar :

  • Empurre o novo elemento para inbox

Dequeue :

  • Se outbox estiver vazio, preencha-o colocando cada elemento de inbox e empurrando-o para outbox

  • Estale e retorne o elemento principal 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 estourado 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();
    }

}
665
Dave L.

A - Como inverter uma pilha

Para entender como construir uma fila usando duas pilhas, você deve entender como inverter uma pilha com clareza. Lembre-se de como a pilha funciona, é muito semelhante à pilha de pratos da sua cozinha. O último prato lavado estará no topo da pilha limpa, que é chamado como L ast I n F primeiro Ot ut (LIFO) em ciência da computação.

Vamos imaginar nossa pilha como uma garrafa como abaixo;

enter image description here

Se nós empurrar inteiros 1,2,3 respectivamente, então 3 estará no topo da pilha. Como 1 será empurrado primeiro, 2 serão colocados no topo de 1. Por último, 3 serão colocados no topo da pilha e o último estado de nossa pilha representado como uma garrafa será como abaixo;

enter image description here

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?

enter image description here

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 populada à esquerda e nossa nova pilha vazia à direita. Para inverter a ordem dos elementos, vamos estourar cada elemento da pilha da esquerda e empurrá-los para a pilha da direita. Você pode ver o que acontece quando fazemos isso na imagem abaixo;

enter image description here

Então, sabemos como reverter uma pilha.

B - Usando duas pilhas como fila

Na parte anterior, expliquei como podemos inverter a ordem dos elementos da pilha. Isso foi importante porque, se pressionarmos e colocarmos elementos na pilha, a saída será exatamente na ordem inversa de uma fila. Pensando em um exemplo, vamos empurrar a matriz de inteiros {1, 2, 3, 4, 5} para uma pilha. Se estourarmos os elementos e os imprimirmos até que a pilha esteja vazia, obteremos o array na ordem inversa da ordem de empilhamento, que será {5, 4, 3, 2, 1}. Lembre-se que para a mesma entrada, se desquequeamos a 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 a inversa 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 a operação enqueue (pilha # 1 à esquerda, será chamada como Pilha de Entrada), outra pilha será usada para a operação dequeue (pilha # 2 à direita, será chamada de Pilha de Saída). Veja a imagem abaixo;

enter image description here

Nosso pseudo-código é como abaixo;


Operação de Enfileiramento

Push every input element to the Input Stack

Operação de Dequeue

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 inteiros {1, 2, 3} respectivamente. Inteiros serão empurrados no Input Stack (Stack # 1) que está localizado à esquerda;

enter image description here

Então, o que acontecerá se executarmos uma operação de retirada? Sempre que uma operação de desenfileiramento for executada, a fila verificará se a Pilha de saída está vazia ou não (consulte o pseudo-código acima) Se a Pilha de saída estiver vazia, a Pilha de entrada será extraída na saída para que os elementos da Pilha de Entradas será invertida. Antes de retornar um valor, o estado da fila será o seguinte;

enter image description here

Confira a ordem dos elementos na pilha de saída (pilha nº 2). É óbvio que podemos estourar os elementos da Pilha de Saída para que a saída seja a mesma que se estivéssemos desenfileirados de uma fila. Assim, se executarmos duas operações de desenfileiramento, primeiro obteremos {1, 2} respectivamente. Então, o elemento 3 será o único elemento da Pilha de saída e a Pilha de entrada estará vazia. Se nós enfileirarmos os elementos 4 e 5, o estado da fila será o seguinte;

enter image description here

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

enter image description here

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 Entradas e Empurre-os para a Pilha de Saída até que a Pilha de Entradas esteja vazia, então o estado da Fila será como abaixo;

enter image description here

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

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

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

C - 1) MyStack class: 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 Fila 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
185
Levent Divilioglu

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

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 seu pedido. 
  • Em seguida, empurre o novo elemento a ser inserido, para a 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á no topo (primeiro a ser estourado)

Uma classe de fila 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();
    }
}
79
pythonquick

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

Editar

Não tenho certeza porque minha resposta foi downvoted aqui. Se programamos, nos preocupamos com a complexidade do tempo e usando duas pilhas padrão para tornar uma fila ineficiente. É um ponto muito válido e relevante. Se alguém sentir a necessidade de diminuir isso mais, eu estaria interessado em saber por quê.

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

Você pode implementar uma fila como uma lista unida (cada elemento aponta para o próximo elemento inserido), mantendo um ponteiro extra para o último elemento inserido para empurra (ou tornando-se uma lista cíclica). A implementação de fila e dequeue nesta estrutura de dados é muito fácil de fazer em tempo constante. Este é o pior horário constante, não amortizado. E, como os comentários parecem solicitar essa clarificação, o tempo constante no pior caso é estritamente melhor que o tempo constante amortizado.

11
Tyler

Deixe a fila a ser implementada como q e as pilhas usadas para implementar q sejam stack1 e stack2. 

q pode ser implementado em two ways:

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

Esse método garante que o elemento recém-inserido esteja sempre no topo da pilha 1, de modo que a operação deQueue simplesmente seja exibida na pilha1. Para colocar o elemento no topo da pilha1, 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)

Neste método, na operação en-queue, o novo elemento é inserido no topo da pilha1. Na operação da fila de espera, se a pilha 2 estiver vazia, todos os elementos serão movidos para a pilha 2 e, finalmente, a parte superior da pilha 2 será retornada.

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 stack2 estiver vazio.

7
Rahul Gandhi

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

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

2
user11055

para c # developer aqui é 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();
        }
    }
}
2
Jaydeep Shil

Duas pilhas na fila são definidas como stack1stack2.

Enfileirar: Os elementos euqueued são sempre empurrados para stack1

Dequeue: O topo da stack2 pode ser retirado desde que é o primeiro elemento inserido na fila quando stack2 não está vazio. Quando stack2 está vazio, nós pop todos os elementos de stack1 e empurre-os para stack2 um por um. O primeiro elemento em uma fila é empurrado para a parte inferior stack1. Ele pode ser exibido diretamente após as operações de popping e push, já que ele está no topo stack2.

O seguinte é 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 de meu blog . Uma análise mais detalhada com simulações de operações passo a passo está disponível na página do meu blog.

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

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

Enquanto você vai ter um monte de posts relacionados à implementação de uma fila com duas pilhas: 1. Ou tornando o processo enQueue muito mais caro 2. Ou fazendo o processo deQueue muito mais caro

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

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

Enquanto alguém pode argumentar que, literalmente, isso ainda está usando duas pilhas, mas, idealmente, isso está usando apenas uma estrutura de dados de pilha.

Abaixo está a explicação do problema:

  1. Declare uma única pilha para enQueuing e deQueing os dados e insira os dados na pilha.

  2. enquanto deQueueing tem uma condição base em que o elemento da pilha é exibido quando o tamanho da pilha é 1. Isso garantirá que não haja estouro de pilha durante a recursão deQueue.

  3. Enquanto deQueueing primeiro pop os dados do topo da pilha. Idealmente, este elemento será o elemento que está presente no topo da pilha. Agora, uma vez feito isso, chame recursivamente a função deQueue e, em seguida, pressione o elemento estourado acima de volta na pilha.

O código será parecido com 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 de pilha e a pilha de chamadas de recursão.

1
Radioactive

aqui está a minha solução em Java usando a lista vinculada.

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: Neste caso, a operação pop é muito demorada. Então eu não vou sugerir criar uma fila usando duas pilhas. 

0
Irshad ck

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

Como uma pilha é realmente fácil de implementar, pensei em tentar usar duas pilhas para realizar uma fila com duas extremidades. 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 permitimos que a parte inferior das pilhas seja manipulada uma pela outra. Também usei as convenções de nomenclatura STL, em que as operações tradicionais Push, pop e peek de uma pilha têm um prefixo de frente/verso, sejam referentes à frente ou ao verso da fila.

O problema com o código acima é que ele não usa memória de maneira muito eficiente. 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. Nós temos que introduzir um offset para rastrear isso, já que uma fatia no Go não pode crescer na frente uma vez encolhida.

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

É um monte de pequenas funções, mas das 6 funções 3 delas são apenas espelhos do outro.

0
John Leidegren

Abaixo está a solução em 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"
0
Jyoti Prasad Pal
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 de stack1 em stack2 e removemos o elemento no topo da stack. A complexidade temporal é O(n) para o dequeue, já que temos que copiar o stack1 para stack2. complexidade de tempo de enfileiramento é o mesmo que uma pilha regular

0
PradGar

Com O(1)dequeue(), que é o mesmo do answer 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, então esta resposta), que também usa backtracking para borbulhar e retornar o item mais inferior.

// 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, por ser ineficiente, mas elegante.

0
hIpPy