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?

Mantenha 2 pilhas, vamos chamá-las de inbox e outbox .

Enfileirar :

  • Empurre o novo elemento na inbox

Dequeue :

  • Se a outbox estiver vazia, recarregue-a, colocando cada elemento da inbox de inbox e empurrando-o para a outbox

  • Estale e retorne o elemento principal da outbox 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 { private Stack inbox = new Stack(); private Stack outbox = new Stack(); 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 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 de L ast I n F nst O ut (LIFO) em ciência da computação.

Vamos imaginar nossa pilha como uma garrafa como abaixo;

insira a descrição da imagem aqui

Se nós empurrarmos 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;

insira a descrição da imagem aqui

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?

insira a descrição da imagem aqui

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 para a esquerda e nossa nova pilha vazia para a 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 o fazemos na imagem abaixo;

insira a descrição da imagem aqui

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 nós empurrarmos e inserirmos 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 nós 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 disso para a mesma input, se Dequeue 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 input de elementos, a saída da fila é exatamente 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 operação de enqueue (pilha nº 1 à esquerda, será chamada como Pilha de input), outra pilha será usada para a operação de dequeue (pilha nº 2 à direita, será chamada de Pilha de saída). Veja a imagem abaixo;

insira a descrição da imagem aqui

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 na pilha de input ( pilha # 1 ) que está localizada à esquerda;

insira a descrição da imagem aqui

Então, o que acontecerá se executarmos uma operação de desenfileiramento? 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 input 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á como abaixo;

insira a descrição da imagem aqui

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 input estará vazia. Se enfileirarmos os elementos 4 e 5, o estado da fila será o seguinte;

insira a descrição da imagem aqui

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;

insira a descrição da imagem aqui

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 e, em seguida, o estado da Fila será o seguinte;

insira a descrição da imagem aqui

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 { // inner generic Node class private class Node { T data; Node next; public Node(T data) { this.data = data; } } private Node head; private int size; public void push(T e) { Node 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 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 { private MyStack inputStack; // for enqueue private MyStack 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 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é 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 sua ordem.
  • 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 está no topo (primeiro a ser estourado)

Uma class de fila usando apenas uma pilha seria a seguinte:

 public class SimulatedQueue { private java.util.Stack stack = new java.util.Stack(); 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 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 o porquê.

Um pouco mais detalhadamente : por que usar duas pilhas é pior do que apenas uma fila: se você usar duas pilhas e alguém chamar dequeue enquanto a checkbox de saída estiver vazia, você precisará de tempo linear para chegar à parte inferior da checkbox de input 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.

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

q pode ser implementado de duas maneiras:

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 seja exibida apenas a partir da 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 retirada da fila, 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.

Uma solução em c #

  public class Queue where T : class { private Stack input = new Stack(); private Stack output = new Stack(); 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 euqueued são sempre colocados na pilha1

Dequeue: O topo da stack2 pode ser retirado, já que é o primeiro elemento inserido na fila quando a stack2 não está vazia. Quando a pilha 2 está vazia, nós colocamos todos os elementos da pilha 1 e os colocamos na pilha 2, um por um. O primeiro elemento em uma fila é colocado na parte inferior da pilha1 . Ele pode ser exibido diretamente após as operações de popping e push, já que está no topo da stack2 .

O seguinte é o mesmo código de exemplo C ++:

 template  class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack stack1; stack stack2; }; template void CQueue::appendTail(const T& element) { stack1.push(element); } template T CQueue::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ções passo a passo está disponível na página do meu blog.

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

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 { public int size; public Node head; public void Push(T data) { Node node = new Node(); node.data = data; if (head == null) head = node; else { node.link = head; head = node; } size++; Display(); } public Node Pop() { if (head == null) return null; else { Node 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 temp = head; while (temp!= null) { Console.WriteLine(temp.data); temp = temp.link; } } } } public class Queue { public int size; public Stack inbox; public Stack outbox; public Queue() { inbox = new Stack(); outbox = new Stack(); } public void EnQueue(T data) { inbox.Push(data); size++; } public Node DeQueue() { if (outbox.size == 0) { while (inbox.size != 0) { outbox.Push(inbox.Pop().data); } } Node temp = new Node(); if (outbox.size != 0) { temp = outbox.Pop(); size--; } return temp; } } public class Node { public T data; public Node link; } static void Main(string[] args) { Queue q = new Queue(); 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(); } } } 
 // Two stacks s1 Original and s2 as Temp one private Stack s1 = new Stack(); private Stack s2 = new Stack(); /* * 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 { 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 { var inStack = Stack() var outStack = Stack() 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 dispendioso

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 recursion.

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 empurre os dados para a 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 recursion 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 function deQueue e, em seguida, empurre o elemento mostrado acima de volta para a 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 recursion.

 public class QueueUsingStacks { private LinkedListStack stack1; private LinkedListStack stack2; public QueueUsingStacks() { stack1=new LinkedListStack(); stack2 = new LinkedListStack(); } public void Copy(LinkedListStack source,LinkedListStack 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 de tempo é 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

Vou responder a essa pergunta no Go porque o Go não possui muitas collections 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 de push, pop e espiada de uma pilha têm um prefixo de frente / verso, quer se refiram à frente ou ao verso da fila.

O problema com o código acima é que ele não usa memory 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 deslocamento 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.

aqui está a minha solução em java usando a lista de links.

 class queue{ static class Node{ private T data; private Node 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.

Com O(1) dequeue() , que é igual à 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, 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, no entanto ineficiente, mas elegante.

Implementação de fila usando dois objects java.util.Stack:

 public final class QueueUsingStacks { private final Stack iStack = new Stack<>(); private final Stack 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(); } }