Implementar pila usando dos colas

142

Una pregunta similar se hizo anteriormente allí , pero la pregunta aquí es lo contrario, usando dos colas como una pila. La pregunta...

Habida cuenta de dos colas con sus operaciones estándar ( enqueue, dequeue, isempty, size), implementar una pila con sus operaciones estándar ( pop, push, isempty, size).

Debería haber dos versiones de la solución.

  • Versión A : la pila debe ser eficiente al empujar un elemento; y
  • Versión B : la pila debe ser eficiente cuando aparece un elemento.

Estoy interesado en el algoritmo más que cualquier implementación de lenguaje específico. Sin embargo, agradezco las soluciones expresadas en idiomas que conozco (,,,,,)

TechTravelThink
fuente
66
¡Claro que lo es! CLRS - 10.1-6 ( tinyurl.com/clrs-ex-10-1-6 )
rampion
1
One Stack, Two Queues ofrece una solución elegante en la que Popfunciona en $ O (1) $ y Pushfunciona en $ O (\ sqrt {n}) $ tiempo amortizado.
hengxin
1
@rampion ahora es CLRS - 10.1-7. :)
nsane
Publicación relacionada. Este es otro problema interesante para implementar la pila usando solo una cola aquí .
RBT

Respuestas:

194

Versión A (empuje eficiente):

  • empujar:
    • poner en cola en la cola1
  • popular:
    • mientras que el tamaño de la cola1 es mayor que 1, canalice los elementos retirados de la cola1 a la cola2
    • poner en cola y devolver el último elemento de queue1, luego cambie los nombres de queue1 y queue2

Versión B (pop eficiente):

  • empujar:
    • poner en cola en la cola2
    • ponga en cola todos los elementos de la cola1 en la cola2, luego cambie los nombres de la cola1 y la cola2
  • popular:
    • Deqeue de queue1
Svante
fuente
44
La versión B parece tener problemas: ¿quiere decir poner en cola todos los elementos de la cola2 a la cola1 excepto el último elemento (luego cambie los nombres de q1 y q2)?
Icerman
El comentario de Icerman tiene sentido para mí. La versión B de la respuesta necesita una edición. No tengo permisos de edición. ¿Podría alguien editar esta respuesta?
eeerahul
2
@eeerahul: Lo he comprobado nuevamente y la respuesta es correcta. En el momento en que Icerman parece querer poner en cola todos los elementos de la cola2 en la cola1, la cola2 consiste solo en el nuevo elemento, por lo que el comentario no tiene sentido.
Svante
¿Es correcta la versión A? empuje 1, empuje 2, empuje 3, empuje 4. pop 4. empuje 5, empuje 6, empuje 7, empuje 8. pop 8. pop 7. Parece que ese algoritmo aparecerá 3 en lugar de 7. Su algoritmo parece correcto primera vista porque posiblemente podamos razonar como: básicamente, siempre estará haciendo estallar el último elemento en cola en la Cola 1. Pero ese es el último elemento insertado solo si había hecho cola anteriormente. Si apareciste varias veces seguidas, eso no tiene por qué ser cierto.
user127.0.0.1
1
@ user127.0.0.1: Parece que olvidó cambiar las colas al final de cada pop. Existe una invariante de que después de cada inserción y cada pop, todos los elementos están en la cola1, mientras que la cola2 está vacía.
Svante
68

La forma más fácil (y quizás la única) de hacer esto es empujando nuevos elementos a la cola vacía, y luego retirando al otro y pasando a la cola previamente vacía. De esta manera, lo último siempre está al frente de la cola. Esta sería la versión B, para la versión A simplemente invierte el proceso eliminando los elementos en la segunda cola, excepto la última.

Paso 0:

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

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

Paso 1:

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

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

Paso 2:

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

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

Paso 3:

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

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+
Samuel
fuente
1
La lógica para esto no tiene ningún sentido. Pase del Paso 2 al Paso 3. Cuando "empujo" 3, ¿cómo puedo eliminar elementos en la Cola B de manera que obtenga 3 2 1 en la Cola A? Si elimino B para colocar A, solo puedo obtener elementos en el orden 2, 1. Si luego agrego 3, obtendré el orden 3, 1, 2. Si pongo mi empuje primero, y luego elimino / agrego, obtengo 1, 2, 3.
tsurantino
¿por qué no hacer que la operación de eliminación sea costosa que hacer que la operación en cola sea costosa?
Divij Sehgal
49

Podemos hacer esto con una cola:

empujar:

  1. Encueue nuevo elemento.
  2. Si nes el número de elementos en la cola, elimine e inserte n-1tiempos de elementos .

popular:

  1. quitar

.

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

Implementación de muestra:

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));
  }
}
foxis
fuente
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
fuente
¿Alguien podría explicar el inicio de sesión detrás del método push en el código anterior? Según tengo entendido, el primer bucle for es eliminar todos los elementos en q2 hasta que q1 tenga un elemento restante. Por favor, corríjame si estoy equivocado.
John
4

¿Podemos usar una sola cola para implementar una pila? Puedo usar dos colas, pero considerar una sola cola sería más eficiente. Aquí está el 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
fuente
Supongo que en el método pop, la condición del bucle for debería ser i <queLower.Count - 2 ya que está inicializando la variable i con 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();
   }
}
chico escondido
fuente
2

Aquí está mi respuesta, donde el 'pop' es ineficiente. Parece que todos los algoritmos que vienen inmediatamente a la mente tienen N complejidad, donde N es el tamaño de la lista: si eliges trabajar en el 'pop' o trabajar en el 'push'

El algoritmo en el que las listas se intercambian hacia atrás y el cuarto puede ser mejor, ya que no es necesario un cálculo de tamaño, aunque aún necesita hacer un bucle y comparar con vacío.

puede probar que este algoritmo no se puede escribir más rápido que N al observar que la información sobre el último elemento en una cola solo está disponible al conocer el tamaño de la cola, y que debe destruir los datos para llegar a ese elemento, por lo tanto, la segunda cola .

La única forma de hacer esto más rápido es no usar colas en primer 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
fuente
2

Aquí está mi solución que funciona para O (1) en el caso promedio. Hay dos colas: iny out. Ver pseudocódigo a continuación:

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
fuente
2
¡Allí está utilizando 2 colas y 1 pila para simular 1 pila!
BeniBela
¿Te refieres a la pila de recursión implícita?
Vladimir Kostyukov
1

Como se ha mencionado, ¿no sería suficiente una sola cola? Probablemente sea menos práctico, pero es un poco más elegante.

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

pop(x):
dequeue()
dhackner
fuente
1

Aquí hay un pseudocódigo simple, push es O (n), pop / peek es 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
fuente
1

Deje que S1 y S2 sean las dos pilas que se utilizarán en la implementación de colas.

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

Nos aseguramos de que una cola esté vacía siempre.

Operación de inserción: cualquiera que sea la cola que no esté vacía, inserte el elemento en ella.

  • Compruebe si la cola Q1 está vacía o no. Si Q1 está vacío, coloque el elemento en él.
  • De lo contrario, agregue el elemento en Q1.

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

Complejidad de tiempo: O (1)

Operación pop: transfiera elementos n-1 a otra cola y elimine el último de la cola para realizar la operación pop.

  • Si la cola Q1 no está vacía, transfiera los elementos n-1 de Q1 a Q2 y luego, elimine el último elemento de Q1 y devuélvalo.
  • Si la cola Q2 no está vacía, transfiera los elementos n-1 de Q2 a Q1 y luego, elimine el último elemento de Q2 y devuélvalo.

``

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

Complejidad de tiempo: tiempo de ejecución de pop La operación es O (n) ya que cada vez que se llama pop, estamos transfiriendo todos los elementos de una cola a otra.

Rahul Gandhi
fuente
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
fuente
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
fuente
0

Aquí hay una solución más:

para PUSH: -Agregue el primer elemento en la cola 1. -Al agregar el segundo elemento y así sucesivamente, coloque primero el elemento en la cola 2 y luego copie todo el elemento de la cola 1 a la cola2. -para POP simplemente elimine el elemento de la cola desde que insertó el último elemento.

Entonces,

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

Hay un problema, no puedo entender, ¿cómo cambiar el nombre de las colas?

Vince
fuente
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
fuente
1
Por favor algunas palabras, explicando lo que este código se trata, y cómo esta cosita es capaz de ayudar a la OP en la solución de su / su problema, será muy apreciada, junto con el código de ejemplo :-)
Vaca Niza
0

Código Python usando solo una cola

 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
fuente
1
Intente evitar simplemente volcar un código como respuesta e intente explicar qué hace y por qué. Es posible que su código no sea obvio para las personas que no tienen la experiencia de codificación relevante.
Fritas
0

Aquí está el código de trabajo completo en C #:

Se ha implementado con Single Queue,

empujar:

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

popular:

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
fuente
¿Le gustaría comentar sobre el tiempo (esperado / amortizado) requerido por su implementación en función de los elementos actualmente guardados / suma de empujes y estallidos?
barba gris el
0

Aquí hay una solución muy simple que usa una cola y brinda funcionalidades como Stack.

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


}

Entonces, en la clase anterior llamada "CustomStack", lo que estoy haciendo es verificar si la cola está vacía, si está vacía, inserte una y, a partir de ese momento, inserte y luego elimine la inserción. Por esta lógica, primero vendrá el último. Ejemplo: en la cola inserté 1 y ahora trato de insertar 2. La segunda vez, elimine 1 y vuelva a insertar para que quede en orden inverso.

Gracias.

Prityalok Raman
fuente
0

A continuación se muestra una solución Java muy simple que admite la operación de inserción eficiente.

Algoritmo

  1. Declara dos colas q1 y q2.

  2. Operación de inserción: coloque el elemento en cola en la cola q1.

  3. Operación emergente: asegúrese de que la cola q2 no esté vacía. Si está vacío, elimine todos los elementos de q1 excepto el último elemento y póngalo en cola a q2 uno por uno. Elimine el último elemento de q1 y guárdelo como el elemento emergente. Intercambie las colas q1 y q2. Devuelve el elemento emergente almacenado.

  4. Operación Peek: asegúrese de que la cola q2 no esté vacía. Si está vacío, elimine todos los elementos de q1 excepto el último elemento y póngalo en cola a q2 uno por uno. Separe el último elemento de q1 y guárdelo como el elemento asomado. Vuelva a ponerla en la cola q2 e intercambie las colas q1 y q2. Devuelve el elemento peeked almacenado.

A continuación se muestra el código para el algoritmo anterior:

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
fuente
-1

Aquí está mi solución ...

Concept_Behind :: push(struct Stack* S,int data):: Esta función pone en cola el primer elemento en Q1 y descansa en Q2 pop(struct Stack* S):: si Q2 no está vacío, transfiere todos los elementos a Q1 y devuelve el último elemento en Q2 más (lo que significa que Q2 está vacío) transfiere todos los elementos a Q2 y devuelve el último elemento en Q1

Efficiency_Behind :: push(struct Stack*S,int data):: O (1) // desde una sola cola por datos pop(struct Stack* S):: O (n) // ya que transfiere los peores datos 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));
    }
Dota 2
fuente
-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
fuente
Una lista enlazada de Java funciona como una deque muy bien. Esta respuesta no tiene sentido.
dfeuer
-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
fuente
Una pared de código sin comentarios ni explicación es una respuesta pobre.
Richard