Implementar pilha usando duas filas

142

Uma pergunta semelhante foi perguntado mais cedo , mas a questão aqui é o inverso disso, usando duas filas como uma pilha. A questão...

Dadas duas filas com suas operações padrão ( enqueue, dequeue, isempty, size), implementar uma pilha com suas operações padrão ( pop, push, isempty, size).

Deve haver duas versões da solução.

  • Versão A : A pilha deve ser eficiente ao empurrar um item; e
  • Versão B : a pilha deve ser eficiente ao exibir um item.

Estou interessado no algoritmo mais do que em qualquer implementação de linguagem específica. No entanto, saúdo as soluções expressas em idiomas que eu conheço (,,,,,)

TechTravelThink
fonte
6
Claro que é! CLRS - 10.1-6 ( tinyurl.com/clrs-ex-10-1-6 )
rampion
1
Uma pilha, duas filas fornece uma solução elegante na qual Popfunciona em $ O (1) $ e Pushfunciona em $ O (\ sqrt {n}) $ tempo amortizado.
Hengxin
1
@rampion Agora seu CLRS - 10.1-7. :)
nSane
Post relacionado. Esse é outro problema interessante para implementar a pilha usando apenas uma fila aqui .
RBT

Respostas:

194

Versão A (envio eficiente):

  • empurrar:
    • enfileirar na fila1
  • pop:
    • enquanto o tamanho da fila1 for maior que 1, canalize os itens desenfileirados da fila1 para a fila2
    • desenfileire e retorne o último item da fila1 e, em seguida, alterne os nomes da fila1 e da fila2

Versão B (pop eficiente):

  • empurrar:
    • enfileirar na fila2
    • enfileire todos os itens da fila1 na fila2 e, em seguida, alterne os nomes da fila1 e da fila2
  • pop:
    • deqeue da fila1
Svante
fonte
4
A versão B parece estar com problema: você quer enfileirar todos os itens da fila2 para a fila1, exceto o último elemento (depois alterne os nomes de q1 e q2)?
Icerman
O comentário de Icerman faz sentido para mim. A versão B da resposta precisa de uma edição. Eu não tenho permissões de edição. Alguém poderia editar esta resposta?
eeerahul
2
@eeerahul: verifiquei novamente e a resposta está correta. No momento, o Icerman parece querer enfileirar todos os itens da fila2 na fila1, a fila2 consiste apenas no novo item, portanto o comentário não faz sentido.
Svante
A versão A está correta? aperte 1, aperte 2, aperte 3, aperte 4. pop 4. aperte 5, aperte 6, aperte 7, aperte 8. pop 8. pop 7. Parece que esse algoritmo estará aparecendo 3 em vez de 7. Seu algoritmo parece correto à primeira vista, porque podemos pensar como: basicamente, você sempre estará exibindo o último elemento na fila 1. Na fila 1. Mas esse é o último elemento enviado apenas se você tiver feito uma fila anteriormente. Se você pulou várias vezes seguidas, isso não precisa ser verdade.
usar o seguinte comando
1
@ user127.0.0.1: Parece que você esqueceu de mudar as filas no final de cada pop. Existe um invariante que, após cada push e pop, todos os itens estão na fila1, enquanto a fila2 está vazia.
26412 Svante
68

A maneira mais fácil (e talvez única) de fazer isso é empurrar novos elementos para a fila vazia e, em seguida, desenfileirar o outro e entrar na fila anteriormente vazia. Dessa maneira, o mais recente está sempre na frente da fila. Essa seria a versão B, para a versão A, você acabou de reverter o processo desenfileirando os elementos na segunda fila, exceto a última.

Etapa 0:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Passo 1:

"Stack"
+---+---+---+---+---+
| 1 |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Passo 2:

"Stack"
+---+---+---+---+---+
| 2 | 1 |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  | 2 | 1 |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Etapa 3:

"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+
Samuel
fonte
1
A lógica para isso não faz nenhum sentido. Passe da Etapa 2 para a Etapa 3. Quando eu "pressiono" 3, como posso desenfileirar elementos na Fila B de modo a obter 3 2 1 na Fila A? Se eu desenfileirar B para enfileirar A, só posso obter elementos na ordem 2, 1. Se eu adicionar 3, receberei a ordem 3, 1, 2. Se eu pressionar primeiro e depois desenfileirar / enfileirar, recebo 1, 2, 3.
tsurantino 11/09/2015
por que não tornar a operação de deque cara do que a de enfileiramento?
Divij Sehgal 28/11
49

Podemos fazer isso com uma fila:

empurrar:

  1. enfileirar novo elemento.
  2. Se nfor o número de elementos na fila, remova e insira as n-1horas do elemento .

pop:

  1. desenfileirar

.

push 1


front                     
+----+----+----+----+----+----+
| 1  |    |    |    |    |    |    insert 1
+----+----+----+----+----+----+


push2

front                     
+----+----+----+----+----+----+
| 1  | 2  |    |    |    |    |    insert 2
+----+----+----+----+----+----+

     front                     
+----+----+----+----+----+----+
|    | 2  |  1 |    |    |    |    remove and insert 1
+----+----+----+----+----+----+




 insert 3


      front                     
+----+----+----+----+----+----+
|    | 2  |  1 |  3 |    |    |    insert 3
+----+----+----+----+----+----+

           front                     
+----+----+----+----+----+----+
|    |    |  1 |  3 |  2 |    |    remove and insert 2
+----+----+----+----+----+----+

                front                     
+----+----+----+----+----+----+
|    |    |    |  3 |  2 |  1 |    remove and insert 1
+----+----+----+----+----+----+

Exemplo de implementação:

int stack_pop (queue_data *q)
{
  return queue_remove (q);
}

void stack_push (queue_data *q, int val)
{
  int old_count = queue_get_element_count (q), i;

  queue_insert (q, val);
  for (i=0; i<old_count; i++)
  {
    queue_insert (q, queue_remove (q));
  }
}
phoxis
fonte
9
import java.util.*;

/**
 *
 * @author Mahmood
 */
public class StackImplUsingQueues {

    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();

    public int pop() {
        if (q1.peek() == null) {
            System.out.println("The stack is empty, nothing to return");
            int i = 0;
            return i;
        } else {
            int pop = q1.remove();
            return pop;
        }
    }

    public void push(int data) {

        if (q1.peek() == null) {
            q1.add(data);
        } else {
            for (int i = q1.size(); i > 0; i--) {
                q2.add(q1.remove());
            }
            q1.add(data);
            for (int j = q2.size(); j > 0; j--) {
                q1.add(q2.remove());
            }

        }
    }

    public static void main(String[] args) {
        StackImplUsingQueues s1 = new StackImplUsingQueues();
        //       Stack s1 = new Stack();
        s1.push(1);
        s1.push(2);
        s1.push(3);
        s1.push(4);
        s1.push(5);
        s1.push(6);
        s1.push(7);
        s1.push(8);
        s1.push(9);
        s1.push(10);
        // s1.push(6);
        System.out.println("1st = " + s1.pop());
        System.out.println("2nd = " + s1.pop());
        System.out.println("3rd = " + s1.pop());
        System.out.println("4th = " + s1.pop());
        System.out.println("5th = " + s1.pop());
        System.out.println("6th = " + s1.pop());
        System.out.println("7th = " + s1.pop());
        System.out.println("8th = " + s1.pop());
        System.out.println("9th = " + s1.pop());
        System.out.println("10th= " + s1.pop());
    }
}
Mahmood Akhtar
fonte
Alguém poderia explicar o login por trás do método push no código acima? Até onde eu entendi, o primeiro loop for é remover todos os elementos no q2 até q1 ter um elemento restante. Por favor corrija-me se eu estiver errado.
John
4

Podemos apenas usar uma fila para implementar uma pilha? Posso usar duas filas, mas considerar a fila única seria mais eficiente. Aqui está o código:

    public void Push(T val)
    {
        queLower.Enqueue(val);
    }

    public  T Pop()
    {

        if (queLower.Count == 0 )
        {
            Console.Write("Stack is empty!");
            return default(T);

         }
        if (queLower.Count > 0)
        {
            for (int i = 0; i < queLower.Count - 1;i++ )
            {
                queLower.Enqueue(queLower.Dequeue ());
           }
                    }

        return queLower.Dequeue();

    }
Min Zhou
fonte
Eu acho que no método pop, a condição do loop for deve ser i <queLower.Count - 2, pois você está inicializando a variável i com 0.
vignesh
3
queue<int> q1, q2;
int i = 0;

void push(int v) {
  if( q1.empty() && q2.empty() ) {
     q1.push(v);
     i = 0;
  }
  else {
     if( i == 0 ) {
        while( !q1.empty() ) q2.push(q1.pop());
        q1.push(v);
        i = 1-i;
     }
     else {
        while( !q2.empty() ) q1.push(q2.pop());
        q2.push(v);
        i = 1-i;
     }
  }
}

int pop() {
   if( q1.empty() && q2.empty() ) return -1;
   if( i == 1 ) {
      if( !q1.empty() )
           return q1.pop();
      else if( !q2.empty() )
           return q2.pop();
   }
   else {
      if( !q2.empty() )
           return q2.pop();
      else if( !q1.empty() )
           return q1.pop();
   }
}
hiddenboy
fonte
2

Aqui está a minha resposta - onde o 'pop' é ineficiente. Parece que todos os algoritmos que vêm imediatamente à mente têm complexidade N, onde N é o tamanho da lista: se você escolhe trabalhar no 'pop' ou no 'push'

O algoritmo em que as listas são negociadas de volta e a quarta pode ser melhor, pois não é necessário um cálculo de tamanho, embora você ainda precise fazer um loop e comparar com vazio.

você pode provar que esse algoritmo não pode ser gravado mais rápido que N, observando que as informações sobre o último elemento de uma fila estão disponíveis apenas através do conhecimento do tamanho da fila e que você deve destruir os dados para chegar a esse elemento, daí a segunda fila .

A única maneira de tornar isso mais rápido é não usar filas em primeiro lugar.

from data_structures import queue

class stack(object):
    def __init__(self):
        q1= queue 
        q2= queue #only contains one item at most. a temp var. (bad?)

    def push(self, item):
        q1.enque(item) #just stick it in the first queue.

    #Pop is inefficient
    def pop(self):
        #'spin' the queues until q1 is ready to pop the right value. 
        for N 0 to self.size-1
            q2.enqueue(q1.dequeue)
            q1.enqueue(q2.dequeue)
        return q1.dequeue()

    @property
    def size(self):
        return q1.size + q2.size

    @property
    def isempty(self):
        if self.size > 0:
           return True
        else
           return False
FlipMcF
fonte
2

Aqui está a minha solução que funciona para O (1) em média. Existem duas filas: ine out. Veja pseudocódigo abaixo:

PUSH(X) = in.enqueue(X)

POP: X =
  if (out.isEmpty and !in.isEmpty)
    DUMP(in, out)
  return out.dequeue

DUMP(A, B) =
  if (!A.isEmpty)
    x = A.dequeue()
    DUMP(A, B)
    B.enqueue(x)
Vladimir Kostyukov
fonte
2
Lá você está usando 2 filas e 1 pilha para simular 1 pilha!
BeniBela
Você quer dizer pilha de recursão implícita?
Vladimir Kostyukov 22/02
1

Como já foi mencionado, uma única fila não funcionaria? Provavelmente é menos prático, mas é um pouco mais lento.

push(x):
enqueue(x)
for(queueSize - 1)
   enqueue(dequeue())

pop(x):
dequeue()
dhackner
fonte
1

Aqui está um pseudo-código simples, push é O (n), pop / peek é O (1):

Qpush = Qinstance()
Qpop = Qinstance()

def stack.push(item):
    Qpush.add(item)
    while Qpop.peek() != null: //transfer Qpop into Qpush
        Qpush.add(Qpop.remove()) 
    swap = Qpush
    Qpush = Qpop
    Qpop = swap

def stack.pop():
    return Qpop.remove()

def stack.peek():
    return Qpop.peek()
dansalmo
fonte
1

Seja S1 e S2 as duas pilhas a serem usadas na implementação de filas.

struct Stack 
{ struct Queue *Q1;
  struct Queue *Q2;
}

Garantimos que uma fila esteja sempre vazia.

Operação push: qualquer fila que não estiver vazia, insira o elemento nela.

  • Verifique se a fila Q1 está vazia ou não. Se Q1 estiver vazio, enfileire o elemento nele.
  • Caso contrário, EnQueue o elemento em Q1.

Push (struct Stack *S, int data) { if(isEmptyQueue(S->Q1) EnQueue(S->Q2, data); else EnQueue(S->Q1, data); }

Complexidade de tempo: O (1)

Operação pop: transfira os elementos n-1 para outra fila e exclua o último da fila para executar a operação pop.

  • Se a fila Q1 não estiver vazia, transfira n-1 elementos de Q1 para Q2 e, deQueueue o último elemento de Q1 e retorne-o.
  • Se a fila Q2 não estiver vazia, transfira os elementos n-1 de Q2 para Q1 e, então, DeQueue o último elemento de Q2 e retorne-o.

`

int Pop(struct Stack *S){
int i, size;
if(IsEmptyQueue(S->Q2)) 
{
size=size(S->Q1);
i=0;
while(i<size-1)
{ EnQueue(S->Q2, Dequeue(S->Q1)) ;
  i++;
}
return DeQueue(S->Q1);  
}
else{
size=size(S->Q2);
while(i<size-1)
EnQueue(S->Q1, Dequeue(S->Q2)) ;
i++;
}
return DeQueue(S->Q2);
} }

Complexidade do tempo: tempo de execução da operação pop é O (n), cada vez que a pop é chamada, estamos transferindo todos os elementos de uma fila para outro.

Rahul Gandhi
fonte
1
Q1 = [10, 15, 20, 25, 30]
Q2 = []

exp:
{   
    dequeue n-1 element from Q1 and enqueue into Q2: Q2 == [10, 15, 20, 25]

    now Q1 dequeue gives "30" that inserted last and working as stack
}

swap Q1 and Q2 then GOTO exp
Ankur Lathiya
fonte
1
import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    Queue<Integer> queue1 = new LinkedList<Integer>();
    Queue<Integer> queue2 = new LinkedList<Integer>();

    // Push element x onto stack.
    public void push(int x) {
        if(isEmpty()){
            queue1.offer(x);
        }else{
            if(queue1.size()>0){
                queue2.offer(x);
                int size = queue1.size();
                while(size>0){
                    queue2.offer(queue1.poll());
                    size--;
                }
            }else if(queue2.size()>0){
                queue1.offer(x);
                int size = queue2.size();
                while(size>0){
                    queue1.offer(queue2.poll());
                    size--;
                }
            }
        }
    }

    // Removes the element on top of the stack.
    public void pop() {
        if(queue1.size()>0){
            queue1.poll();
        }else if(queue2.size()>0){
            queue2.poll();
        }
    }

    // Get the top element. You can make it more perfect just example
    public int top() {
       if(queue1.size()>0){
            return queue1.peek();
        }else if(queue2.size()>0){
            return queue2.peek();
        }
        return 0;
    }

    // Return whether the stack is empty.
    public boolean isEmpty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
Swapnil Gangrade
fonte
0

Aqui está mais uma solução:

para PUSH: -Adicione o primeiro elemento na fila 1.-Ao adicionar o segundo elemento e assim por diante, enfileire o elemento na fila 2 primeiro e depois copie todo o elemento da fila 1 para a fila2. -para o POP apenas desenfileirar o elemento da fila de você inseriu o último elemento.

Assim,

public void push(int data){
if (queue1.isEmpty()){
    queue1.enqueue(data);
}  else {
queue2.enqueue(data);
while(!queue1.isEmpty())
Queue2.enqueue(queue1.dequeue());
//EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2

}}

public int pop(){
int popItem=queue2.dequeue();
return popItem;
}'

Há um problema, não consigo descobrir, como renomear as filas ???

Vince
fonte
0
#include <bits/stdc++.h>
using namespace std;
queue<int>Q;
stack<int>Stk;
void PRINT(stack<int>ss , queue<int>qq) {
    while( ss.size() ) {
        cout << ss.top() << " " ;
        ss.pop();
    }
    puts("");
    while( qq.size() ) {
        cout << qq.front() << " " ;
        qq.pop();
    }
    puts("\n----------------------------------");
}
void POP() {
    queue<int>Tmp ;
    while( Q.size() > 1 ) {
        Tmp.push( Q.front()  );
        Q.pop();
    }
    cout << Q.front() << " " << Stk.top() << endl;
    Q.pop() , Stk.pop() ;
    Q = Tmp ;
}
void PUSH(int x ) {
    Q.push(x);
    Stk.push(x);
}
int main() {
    while( true ) {
        string typ ;
        cin >> typ ;
        if( typ == "push" ) {
            int x ;
            cin >> x;
            PUSH(x);
        } else POP();
        PRINT(Stk,Q);
    }
}
Rezwan4029
fonte
1
Por favor, algumas palavras, explicando o que este código é aproximadamente, e como esta coisa é capaz de ajudar o OP em resolver sua / seu problema, será muito apreciada, juntamente com o exemplo de código :-)
Vaca agradável
0

Código Python usando apenas uma fila

 class Queue(object):
    def __init__(self):
        self.items=[]
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        if(not self.isEmpty()):
            return  self.items.pop()
    def isEmpty(self):
        return  self.items==[]
    def size(self):
        return len(self.items)



class stack(object):
        def __init__(self):
            self.q1= Queue()


        def push(self, item):
            self.q1.enqueue(item) 


        def pop(self):
            c=self.q1.size()
            while(c>1):
                self.q1.enqueue(self.q1.dequeue())
                c-=1
            return self.q1.dequeue()



        def size(self):
            return self.q1.size() 


        def isempty(self):
            if self.size > 0:
               return True
            else:
               return False
Amol Sinha
fonte
1
Tente evitar apenas despejar um código como resposta e tente explicar o que ele faz e por quê. Seu código pode não ser óbvio para pessoas que não têm a experiência de codificação relevante.
Frits 18/07
0

aqui está o código completo de trabalho em c #:

Foi implementado com fila única,

empurrar:

1. add new element.
2. Remove elements from Queue (totalsize-1) times and add back to the Queue

pop:

normal remove





 using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace StackImplimentationUsingQueue
    {
        class Program
        {
            public class Node
            {
                public int data;
                public Node link;
            }
            public class Queue
            {
                public Node rear;
                public Node front;
                public int size = 0;
                public void EnQueue(int data)
                {
                    Node n = new Node();
                    n.data = data;
                    n.link = null;
                    if (rear == null)
                        front = rear = n;
                    else
                    {
                        rear.link = n;
                        rear = n;
                    }
                    size++;
                    Display();
                }
                public Node DeQueue()
                {
                    Node temp = new Node();
                    if (front == null)
                        Console.WriteLine("Empty");
                    else
                    {
                        temp = front;
                        front = front.link;
                        size--;
                    }
                    Display();
                    return temp;
                }
                public void Display()
                {
                    if (size == 0)
                        Console.WriteLine("Empty");
                    else
                    {
                        Console.Clear();
                        Node n = front;
                        while (n != null)
                        {
                            Console.WriteLine(n.data);
                            n = n.link;
                        }
                    }
                }
            }
            public class Stack
            {
                public Queue q;
                public int size = 0;
                public Node top;
                public Stack()
                {
                    q = new Queue();
                }
                public void Push(int data)
                {
                    Node n = new Node();
                    n.data = data;
                    q.EnQueue(data);
                    size++;
                    int counter = size;
                    while (counter > 1)
                    {
                        q.EnQueue(q.DeQueue().data);
                        counter--;
                    }
                }
                public void Pop()
                {
                    q.DeQueue();
                    size--;
                }
            }
            static void Main(string[] args)
            {
                Stack s= new Stack();
                for (int i = 1; i <= 3; i++)
                    s.Push(i);
                for (int i = 1; i < 3; i++)
                    s.Pop();
                Console.ReadKey();
            }
        }
    }
Jaydeep Shil
fonte
Gostaria de comentar sobre o tempo (esperado / amortizado) exigido pela sua implementação em função dos elementos atualmente mantidos / soma de empurrões e pops?
22816
0

Aqui está uma solução muito simples que usa uma fila e fornece funcionalidades como a pilha.

public class CustomStack<T>
{
    Queue<T> que = new Queue<T>();

    public void push(T t) // STACK = LIFO / QUEUE = FIFO
    {

        if( que.Count == 0)
        {
            que.Enqueue(t);
        }
        else
        {
            que.Enqueue(t);
            for (int i = 0; i < que.Count-1; i++)
            {
                var data = que.Dequeue();

                que.Enqueue(data);
            }
        }

    }

    public void pop()
    {

        Console.WriteLine("\nStack Implementation:");
        foreach (var item in que)
        {
            Console.Write("\n" + item.ToString() + "\t");
        }

        var data = que.Dequeue();
        Console.Write("\n Dequeing :" + data);
    }

    public void top()
    {

        Console.Write("\n Top :" + que.Peek());
    }


}

Portanto, na classe acima denominada "CustomStack", o que estou fazendo é apenas verificar se há vazio na fila, se vazio, em seguida, insira um e a partir de então, insira e remova o inserto. Por essa lógica, o primeiro virá por último. Exemplo: Na fila, inseri 1 e agora estou tentando inserir 2. Na segunda vez, remova 1 e insira novamente para que fique na ordem inversa.

Obrigado.

Prityalok Raman
fonte
0

Abaixo está uma solução Java muito simples que suporta a operação push eficiente.

Algoritmo -

  1. Declare duas filas q1 e q2.

  2. Operação push - enfileirar o elemento na fila q1.

  3. Operação pop - Verifique se a fila q2 não está vazia. Se estiver vazio, desenfileire todos os elementos de q1, exceto o último elemento, e enfileire-o em q2, um por um. Retire da fila o último elemento de q1 e armazene-o como o elemento popped. Troque as filas q1 e q2. Retorne o elemento popped armazenado.

  4. Peek operation - Verifique se a fila q2 não está vazia. Se estiver vazio, desenfileire todos os elementos de q1, exceto o último elemento, e enfileire-o em q2, um por um. Retire da fila o último elemento de q1 e armazene-o como o elemento espiado. Coloque-o novamente na fila q2 e troque as filas q1 e q2. Retorne o elemento espiado armazenado.

Abaixo está o código do algoritmo acima -

class MyStack {

    java.util.Queue<Integer> q1;
    java.util.Queue<Integer> q2;
    int SIZE = 0;

    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();

    }

    /** Push element x onto stack. */
    public void push(int x) {
        q1.add(x);
        SIZE ++;

    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        ensureQ2IsNotEmpty();
        int poppedEle = q1.remove();
        SIZE--;
        swapQueues();
        return poppedEle;
    }

    /** Get the top element. */
    public int top() {
        ensureQ2IsNotEmpty();
        int peekedEle = q1.remove();
        q2.add(peekedEle);
        swapQueues();
        return peekedEle;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();

    }

    /** move all elements from q1 to q2 except last element */
    public void ensureQ2IsNotEmpty() {
        for(int i=0; i<SIZE-1; i++) {
            q2.add(q1.remove());
        }
    }

    /** Swap queues q1 and q2 */
    public void swapQueues() {
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
}
Hetal Rachh
fonte
-1

Aqui está a minha solução ..

Concept_Behind :: push(struct Stack* S,int data):: Essa função enfileira o primeiro elemento no Q1 e permanece no Q2 pop(struct Stack* S) :: se Q2 não estiver vazio, transfere todos os elem para Q1 e retorna o último elem em Q2, caso contrário, o que significa que Q2 está vazio retorna o último elem no primeiro trimestre

Efficiency_Behind :: push(struct Stack*S,int data):: O (1) // desde o enfileiramento único por dados pop(struct Stack* S):: O (n) //, pois transfere os piores dados n-1 por pop.

#include<stdio.h>
#include<stdlib.h>
struct Queue{
    int front;
    int rear;
    int *arr;
    int size;
    };
struct Stack {
    struct Queue *Q1;
    struct Queue *Q2;
    };
struct Queue* Qconstructor(int capacity)
{
    struct Queue *Q=malloc(sizeof(struct Queue));
    Q->front=Q->rear=-1;
    Q->size=capacity;
    Q->arr=malloc(Q->size*sizeof(int));
    return Q;
    }
int isEmptyQueue(struct Queue *Q)
{
    return (Q->front==-1);
    }
int isFullQueue(struct Queue *Q)
{
    return ((Q->rear+1) % Q->size ==Q->front);
    }
void enqueue(struct Queue *Q,int data)
{
    if(isFullQueue(Q))
        {
            printf("Queue overflow\n");
            return;}
    Q->rear=Q->rear+1 % Q->size;
    Q->arr[Q->rear]=data;
    if(Q->front==-1)
        Q->front=Q->rear;
        }
int dequeue(struct Queue *Q)
{
    if(isEmptyQueue(Q)){
        printf("Queue underflow\n");
        return;
        }
    int data=Q->arr[Q->front];
    if(Q->front==Q->rear)
        Q->front=-1;
    else
    Q->front=Q->front+1 % Q->size;
    return data;
    }
///////////////////////*************main algo****************////////////////////////
struct Stack* Sconstructor(int capacity)
{
    struct Stack *S=malloc(sizeof(struct Stack));
    S->Q1=Qconstructor(capacity);
    S->Q2=Qconstructor(capacity);
    return S;
}
void push(struct Stack *S,int data)
{
    if(isEmptyQueue(S->Q1))
        enqueue(S->Q1,data);
    else
        enqueue(S->Q2,data);
    }
int pop(struct Stack *S)
{
    int i,tmp;
    if(!isEmptyQueue(S->Q2)){
        for(i=S->Q2->front;i<=S->Q2->rear;i++){
            tmp=dequeue(S->Q2);
            if(isEmptyQueue(S->Q2))
                return tmp;
            else
                enqueue(S->Q1,tmp);
                }
            }
    else{
        for(i=S->Q1->front;i<=S->Q1->rear;i++){
            tmp=dequeue(S->Q1);
            if(isEmptyQueue(S->Q1))
                return tmp;
            else
                enqueue(S->Q2,tmp);
                }
            }
        }
////////////////*************end of main algo my algo************
///////////////*************push() O(1);;;;pop() O(n);;;;*******/////
main()
{
    int size;
    printf("Enter the number of elements in the Stack(made of 2 queue's)::\n");
    scanf("%d",&size);
    struct Stack *S=Sconstructor(size);
    push(S,1);
    push(S,2);
    push(S,3);
    push(S,4);
    printf("%d\n",pop(S));
    push(S,5);
    printf("%d\n",pop(S));
    printf("%d\n",pop(S));
    printf("%d\n",pop(S));
    printf("%d\n",pop(S));
    }
Dota2
fonte
-1
import java.util.LinkedList;
import java.util.Queue;


public class StackQueue {

    static Queue<Integer> Q1 = new LinkedList<Integer>();
    static Queue<Integer> Q2 = new LinkedList<Integer>();
    public static void main(String args[]) {



        push(24);
        push(34);
        push(4);
        push(10);
        push(1);
        push(43);
        push(21);
        System.out.println("Popped element is  "+pop());
        System.out.println("Popped element is  "+pop());
        System.out.println("Popped element is  "+pop());


    }

    public static void push(int data) {

        Q1.add(data);

    }

    public static int pop() {

        if(Q1.isEmpty()) {
        System.out.println("Cannot pop elements ,  Stack is Empty !!"); 
        return -1;
        }
        else
        {
        while(Q1.size() > 1) {
            Q2.add(Q1.remove());
        }
        int element = Q1.remove();
        Queue<Integer> temp = new LinkedList<Integer>();
        temp = Q1;
        Q1 = Q2;
        Q2 = temp;
        return element;
        }
    }
}
Rajnish Kumar Jha
fonte
Uma lista vinculada a Java funciona como um deque muito bem. Esta resposta não faz sentido.
Dfeuer # 23/15
-1
#include "stdio.h"
#include "stdlib.h"

typedef struct {
    int *q;
    int size;
    int front;
    int rear;
} Queue;
typedef struct {
    Queue *q1;
    Queue *q2;
} Stack;

int queueIsEmpty(Queue *q) {
    if (q->front == -1 && q->rear == -1) {
        printf("\nQUEUE is EMPTY\n");
        return 1;
    }
    return 0;
}
int queueIsFull(Queue *q) {
    if (q->rear == q->size-1) {
        return 1;
    }
    return 0;
}
int queueTop(Queue *q) {
    if (queueIsEmpty(q)) {
        return -1;
    }
    return q->q[q->front];
}
int queuePop(Queue *q) {
    if (queueIsEmpty(q)) {
        return -1;
    }
    int item = q->q[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    }
    else {
        q->front++;
    }
    return item;
}
void queuePush(Queue *q, int val) {
    if (queueIsFull(q)) {
        printf("\nQUEUE is FULL\n");
        return;
    }
    if (queueIsEmpty(q)) {
        q->front++;
        q->rear++;
    } else {
        q->rear++;
    }
    q->q[q->rear] = val;
}
Queue *queueCreate(int maxSize) {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = -1;
    q->size = maxSize;
    q->q = (int*)malloc(sizeof(int)*maxSize);
    return q;
}
/* Create a stack */
void stackCreate(Stack *stack, int maxSize) {
    Stack **s = (Stack**) stack;
    *s = (Stack*)malloc(sizeof(Stack));
    (*s)->q1 = queueCreate(maxSize);
    (*s)->q2 = queueCreate(maxSize);
}

/* Push element x onto stack */
void stackPush(Stack *stack, int element) {
    Stack **s = (Stack**) stack;
    queuePush((*s)->q2, element);
    while (!queueIsEmpty((*s)->q1)) {
        int item = queuePop((*s)->q1);
        queuePush((*s)->q2, item);
    }
    Queue *tmp = (*s)->q1;
    (*s)->q1 = (*s)->q2;
    (*s)->q2 = tmp;
}

/* Removes the element on top of the stack */
void stackPop(Stack *stack) {
    Stack **s = (Stack**) stack;
    queuePop((*s)->q1);
}

/* Get the top element */
int stackTop(Stack *stack) {
    Stack **s = (Stack**) stack;
    if (!queueIsEmpty((*s)->q1)) {
      return queueTop((*s)->q1);
    }
    return -1;
}

/* Return whether the stack is empty */
bool stackEmpty(Stack *stack) {
    Stack **s = (Stack**) stack;
    if (queueIsEmpty((*s)->q1)) {
        return true;
    }
    return false;
}

/* Destroy the stack */
void stackDestroy(Stack *stack) {
    Stack **s = (Stack**) stack;
    free((*s)->q1);
    free((*s)->q2);
    free((*s));
}

int main()
{
  Stack *s = NULL;
  stackCreate((Stack*)&s, 10);
  stackPush((Stack*)&s, 44);
  //stackPop((Stack*)&s);
  printf("\n%d", stackTop((Stack*)&s));
  stackDestroy((Stack*)&s);
  return 0;
}
seth
fonte
Uma parede de código sem comentários ou explicações é uma resposta ruim.
Richard