¿Cómo implementar una cola usando dos pilas?

394

Supongamos que tenemos dos pilas y ninguna otra variable temporal.

¿Es posible "construir" una estructura de datos de cola usando solo las dos pilas?

Nitina
fuente

Respuestas:

701

Mantenga 2 pilas, llamémoslas inboxy outbox.

Poner en cola :

  • Empuje el nuevo elemento sobre inbox

Dequeue :

  • Si outboxestá vacío, rellénelo sacando cada elemento inboxy empujándolo haciaoutbox

  • Pop y devolver el elemento superior de outbox

Usando este método, cada elemento estará en cada pila exactamente una vez, lo que significa que cada elemento se empujará dos veces y se abrirá dos veces, dando operaciones de tiempo constante amortizado.

Aquí hay una implementación en 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();
    }

}
Dave L.
fuente
13
La complejidad del tiempo en el peor de los casos sigue siendo O (n). Insisto en decir esto porque espero que ningún alumno (esto suene como una tarea / pregunta educativa) piense que esta es una forma aceptable de implementar una cola.
Tyler
26
Es cierto que el peor momento para una sola operación emergente es O (n) (donde n es el tamaño actual de la cola). Sin embargo, el peor momento para una secuencia de n operaciones en cola también es O (n), lo que nos da el tiempo constante amortizado. No implementaría una cola de esta manera, pero no es tan malo.
Dave L.
1
@Tyler Si su pila está basada en una matriz, como la mayoría, siempre obtendrá O (n) peor caso para una sola operación.
Thomas Ahle
2
@ Tyler: Verifique sgi.com/tech/stl/Deque.html . Deque "admite acceso aleatorio a elementos". Por lo tanto, tanto deque como stack están basados ​​en una matriz. Esto se debe a que le brinda una mejor localidad de referencia y, por lo tanto, es más rápido en la práctica.
Thomas Ahle
13
@Newtang a) cola 1,2,3 => Bandeja de entrada [3,2,1] / Bandeja de salida [] . b) decaer. la bandeja de salida está vacía, así que rellene => Bandeja de entrada [] / Bandeja de salida [1,2,3] . Salir de la bandeja de salida, devolver 1 => Bandeja de entrada [] / Bandeja de salida [2,3] . c) cola 4,5 => Bandeja de entrada [5,4] / Bandeja de salida [2,3] . d) decaer. la bandeja de salida no está vacía, así que salga de la bandeja de salida, devuelva 2 => Bandeja de entrada [5,4] / Bandeja de salida [3] . ¿Eso tiene más sentido?
Dave L.
226

A - Cómo revertir una pila

Para entender cómo construir una cola usando dos pilas, debes entender cómo revertir una pila cristalina. Recuerde cómo funciona la pila, es muy similar a la pila de platos en su cocina. El último plato lavado estará en la parte superior de la pila limpia, que se llama L ast I n F firstst O ut (LIFO) en informática.

Imaginemos nuestra pila como una botella como se muestra a continuación;

ingrese la descripción de la imagen aquí

Si empujamos enteros 1,2,3 respectivamente, entonces 3 estará en la parte superior de la pila. Como 1 será empujado primero, luego 2 se colocará en la parte superior de 1. Por último, 3 se colocará en la parte superior de la pila y el último estado de nuestra pila representado como una botella será el siguiente;

ingrese la descripción de la imagen aquí

Ahora tenemos nuestra pila representada como una botella que se rellena con valores 3,2,1. Y queremos invertir la pila para que el elemento superior de la pila sea 1 y el elemento inferior de la pila sea 3. ¿Qué podemos hacer? ¿Podemos tomar la botella y mantenerla boca abajo para que todos los valores se inviertan en orden?

ingrese la descripción de la imagen aquí

Sí, podemos hacer eso, pero eso es una botella. Para hacer el mismo proceso, necesitamos tener una segunda pila que almacene los primeros elementos de la pila en orden inverso. Pongamos nuestra pila poblada a la izquierda y nuestra nueva pila vacía a la derecha. Para invertir el orden de los elementos, vamos a hacer estallar cada elemento de la pila izquierda y empujarlos a la pila derecha. Puedes ver lo que sucede mientras lo hacemos en la imagen a continuación;

ingrese la descripción de la imagen aquí

Entonces sabemos cómo invertir una pila.

B - Usando dos pilas como una cola

En la parte anterior, he explicado cómo podemos invertir el orden de los elementos de la pila. Esto era importante, porque si empujamos y sacamos elementos a la pila, el resultado será exactamente en orden inverso al de una cola. Pensando en un ejemplo, empujemos la matriz de enteros {1, 2, 3, 4, 5}a una pila. Si hacemos estallar los elementos e imprimimos hasta que la pila esté vacía, obtendremos la matriz en el orden inverso al orden de inserción, que será {5, 4, 3, 2, 1}Recuerde que para la misma entrada, si retiramos la cola hasta que la cola esté vacía, la salida será {1, 2, 3, 4, 5}. Por lo tanto, es obvio que para el mismo orden de entrada de elementos, la salida de la cola es exactamente inversa a la salida de una pila. Como sabemos cómo invertir una pila usando una pila adicional, podemos construir una cola usando dos pilas.

Nuestro modelo de cola consistirá en dos pilas. Una pila se usará para la enqueueoperación (la pila # 1 a la izquierda, se llamará como Pila de entrada), otra pila se usará para la dequeueoperación (la pila # 2 a la derecha, se llamará como Pila de salida). Mira la imagen a continuación;

ingrese la descripción de la imagen aquí

Nuestro pseudocódigo es el siguiente;


Operación en cola

Push every input element to the Input Stack

Operación en espera

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

Pongamos en cola los enteros {1, 2, 3}respectivamente. Los enteros se insertarán en la Pila de entrada ( Pila # 1 ) que se encuentra a la izquierda;

ingrese la descripción de la imagen aquí

Entonces, ¿qué sucederá si ejecutamos una operación de retirada de cola? Cada vez que se ejecuta una operación de extracción, la cola verificará si la Pila de salida está vacía o no (consulte el pseudocódigo anterior) Si la Pila de salida está vacía, la Pila de entrada se extraerá en la salida para que los elementos de la pila de entrada se invertirá. Antes de devolver un valor, el estado de la cola será el siguiente;

ingrese la descripción de la imagen aquí

Verifique el orden de los elementos en la Pila de salida (Pila # 2). Es obvio que podemos extraer los elementos de la Pila de salida para que la salida sea la misma que si saliéramos de una cola. Por lo tanto, si ejecutamos dos operaciones en cola, primero obtendremos {1, 2}respectivamente. Entonces el elemento 3 será el único elemento de la Pila de salida, y la Pila de entrada estará vacía. Si ponemos en cola los elementos 4 y 5, entonces el estado de la cola será el siguiente;

ingrese la descripción de la imagen aquí

Ahora la pila de salida no está vacía, y si ejecutamos una operación de retirada de la cola, solo 3 saldrán de la pila de salida. Entonces el estado se verá como a continuación;

ingrese la descripción de la imagen aquí

Nuevamente, si ejecutamos dos operaciones más de cola, en la primera operación de cola, la cola verificará si la Pila de Salida está vacía, lo cual es cierto. Luego extraiga los elementos de la Pila de entrada y empújelos a la Pila de salida hasta que la Pila de entrada esté vacía, luego el estado de la Cola será el siguiente;

ingrese la descripción de la imagen aquí

Fácil de ver, la salida de las dos operaciones de eliminación de cola será {4, 5}

C - Implementación de la cola construida con dos pilas

Aquí hay una implementación en Java. No voy a usar la implementación existente de Stack, así que el ejemplo aquí va a reinventar la rueda;

C - 1) Clase MyStack: una implementación de pila simple

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) Clase MyQueue: Implementación de cola usando dos pilas

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 de demostración

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) Salida de muestra

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
Levent Divilioglu
fuente
18
Haría +1 esto todo el día si pudiera. No podía entender cómo se amortizaba el tiempo constante. Sus ilustraciones realmente aclararon las cosas, especialmente la parte de dejar los elementos restantes en la pila de salida y solo rellenar cuando se vacía.
Shane McQuillan
1
Esto realmente ayudó a evitar los errores de tiempo de espera que recibía durante el pop. Estaba volviendo a colocar los elementos en la pila original, pero no había necesidad de hacerlo. ¡Prestigio!
Pranit Bankar
2
Todos los comentarios deben ser modelados después de este.
lolololol ol
44
Realmente no necesitaba una solución para esto, solo buscaba ... Pero cuando veo una respuesta como esta simplemente me enamoro ... ¡¡¡Excelente respuesta !!!
Maverick
80

Incluso puede simular una cola usando solo una pila. La segunda pila (temporal) se puede simular mediante la pila de llamadas de llamadas recursivas al método de inserción.

El principio permanece igual al insertar un nuevo elemento en la cola:

  • Necesita transferir elementos de una pila a otra pila temporal, para invertir su orden.
  • Luego empuje el nuevo elemento a insertar, en la pila temporal
  • Luego transfiere los elementos nuevamente a la pila original
  • El nuevo elemento estará en la parte inferior de la pila, y el elemento más antiguo estará en la parte superior (el primero en aparecer)

Una clase de cola que usa solo una pila, sería la siguiente:

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();
    }
}
pythonquick
fuente
51
Tal vez el código se ve elegante pero es muy ineficiente (inserción O (n ** 2)) y todavía tiene dos pilas, una en el montón y otra en la pila de llamadas, como señala @pythonquick. Para un algoritmo no recursivo, siempre puede obtener una pila "extra" de la pila de llamadas en idiomas que admitan la recursividad.
Antti Huima
1
@ antti.huima ¿Y explicaría cómo podría ser un inserto cuadrático? Por lo que entiendo, insert hace n pop y n operaciones push, por lo que es un algoritmo O (n) perfectamente lineal.
LP_
1
@LP_ toma tiempo cuadrático O (n ^ 2) para insertar n itemsen la cola usando la estructura de datos anterior. la suma (1 + 2 + 4 + 8 + .... + 2(n-1))resulta en ~O(n^2). Espero que entiendas el punto.
Ankit Kumar
1
@ antti.huima Estabas hablando de la complejidad de la función de inserción (dijiste "O (n 2) insert" - probablemente quisiste decir "O (n 2) fill"). Por convención , "el inserto de complejidad" es el tiempo que lleva una inserción, que aquí es lineal en el número de elementos ya presentes. Si hablamos en el tiempo necesario para insertar n elementos, diríamos que una tabla hash tiene inserción lineal. Que no es el caso.
LP_
2
Básicamente estás usando la pila, como una pila. Esto significa que si hay una gran cantidad de elementos en la pila, puede terminar con un desbordamiento de la pila: ¡es casi como si la solución estuviera diseñada para este sitio!
UKMonkey
11

Sin embargo, la complejidad del tiempo sería peor. Una buena implementación de la cola hace todo en tiempo constante.

Editar

No estoy seguro de por qué mi respuesta ha sido rechazada aquí. Si programamos, nos preocupamos por la complejidad del tiempo, y el uso de dos pilas estándar para hacer una cola es ineficiente. Es un punto muy válido y relevante. Si alguien más siente la necesidad de menospreciar esto, me interesaría saber por qué.

Un poco más de detalle : sobre por qué usar dos pilas es peor que solo una cola: si usa dos pilas y alguien llama a la espera mientras la bandeja de salida está vacía, necesita tiempo lineal para llegar al fondo de la bandeja de entrada (como puede ver en el código de Dave).

Puede implementar una cola como una lista enlazada individualmente (cada elemento apunta al siguiente elemento insertado), manteniendo un puntero adicional al último elemento insertado para los empujes (o haciéndolo una lista cíclica). Implementar cola y cola en esta estructura de datos es muy fácil de hacer en tiempo constante. Ese es el peor tiempo constante, no amortizado. Y, como los comentarios parecen pedir esta aclaración, el tiempo constante en el peor de los casos es estrictamente mejor que el tiempo constante amortizado.

Tyler
fuente
No en el caso promedio. La respuesta de Brian describe una cola que habría amortizado las operaciones constantes de cola y cola .
Daniel Spiewak
Es verdad. Tiene una complejidad promedio de caso y tiempo amortizado igual. Pero el valor predeterminado suele ser el peor de los casos por operación, y esto es O (n) donde n es el tamaño actual de la estructura.
Tyler
1
El peor de los casos también se puede amortizar. Por ejemplo, generalmente se considera que las matrices dinámicas mutables (vectores) tienen un tiempo de inserción constante, a pesar de que de vez en cuando se requiere una costosa operación de cambio de tamaño y copia.
Daniel Spiewak
1
"El peor de los casos" y "amortizado" son dos tipos diferentes de complejidad temporal. No tiene sentido decir que "el peor de los casos se puede amortizar": si pudiera hacer el peor de los casos = el amortizado, entonces esto sería una mejora significativa; solo hablarías del peor de los casos, sin promedios.
Tyler
No estoy seguro de qué quiere decir que O (1) en el peor de los casos sea "estrictamente mejor" que una combinación de O (1) caso promedio y O (n) en el peor de los casos. Los factores de escala constantes son importantes. Una estructura de datos que, si contiene N elementos, puede necesitar ser reempacada después de N operaciones en un momento de N microsegundos, y de lo contrario toma un microsegundo por operación, puede ser mucho más útil que una que toma un milisegundo para cada operación, incluso si el tamaño de los datos se expandirá a millones de elementos (lo que implica que algunas operaciones individuales tomarían varios segundos).
supercat
8

Deje que la cola a implementar sea q y las pilas utilizadas para implementar q sean stack1 y stack2.

q se puede implementar de dos maneras:

Método 1 (haciendo que la operación enQueue sea costosa)

Este método asegura que el elemento recién ingresado esté siempre en la parte superior de la pila 1, de modo que la operación deQueue simplemente aparezca en la pila1. Para colocar el elemento en la parte superior de stack1, se utiliza stack2.

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 (haciendo que la operación deQueue sea costosa)

En este método, en la operación en cola, el nuevo elemento se ingresa en la parte superior de stack1. En la operación de eliminación de la cola, si stack2 está vacío, todos los elementos se mueven a stack2 y finalmente se devuelve la parte superior de stack2.

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.

El método 2 es definitivamente mejor que el método 1. El método 1 mueve todos los elementos dos veces en la operación enQueue, mientras que el método 2 (en la operación deQueue) mueve los elementos una vez y mueve los elementos solo si stack2 está vacío.

Rahul Gandhi
fuente
Ninguna de las soluciones que entendí, excepto su método 2. Me encanta la forma en que la explica con el método en cola y de cola con los pasos.
theGreenCabbage
1
google.com/…
sábado
3

Una solución en 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();
    }
}
Santhosh
fuente
2

Dos pilas en la cola se definen como stack1 y stack2 .

Poner en cola: los elementos euqueued siempre se insertan en stack1

Dequeue: la parte superior de stack2 se puede extraer ya que es el primer elemento insertado en la cola cuando stack2 no está vacío. Cuando stack2 está vacío, sacamos todos los elementos de stack1 y los empujamos a stack2 uno por uno. El primer elemento de una cola se inserta en la parte inferior de stack1 . Se puede extraer directamente después de explotar y empujar operaciones ya que está en la parte superior de stack2 .

El siguiente es el mismo código de muestra de 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 solución está tomada de mi blog . Un análisis más detallado con simulaciones de operación paso a paso está disponible en la página web de mi blog.

Harry He
fuente
2

Tendrás que sacar todo de la primera pila para obtener el elemento inferior. Luego, vuelva a colocarlos en la segunda pila para cada operación de "eliminación de cola".

usuario11055
fuente
3
Sí, tiene usted razón. Me pregunto cómo obtuviste tantos votos negativos. He votado tu respuesta
Binita Bharati
Es espeluznante ver que esta fue su última respuesta y ha pasado una década desde entonces.
Shanu Gupta
2

para el desarrollador de c # aquí está el 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();
        }
    }
}
Jaydeep Shil
fuente
2

Implemente las siguientes operaciones de una cola usando pilas.

push (x): empuja el elemento x hacia el final de la cola.

pop () - Elimina el elemento delante de la cola.

peek () - Obtiene el elemento frontal.

empty () - Devuelve si la cola está vacía.

ingrese la descripción de la imagen aquí

class MyQueue {

  Stack<Integer> input;
  Stack<Integer> output;

  /** Initialize your data structure here. */
  public MyQueue() {
    input = new Stack<Integer>();
    output = new Stack<Integer>();
  }

  /** Push element x to the back of queue. */
  public void push(int x) {
    input.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
    peek();
    return output.pop();
  }

  /** Get the front element. */
  public int peek() {
    if(output.isEmpty()) {
        while(!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
  }

  /** Returns whether the queue is empty. */
  public boolean empty() {
    return input.isEmpty() && output.isEmpty();
  }
}
Rathi Girish
fuente
1
// 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();

        }
    }
imvp
fuente
1

Una implementación de una cola usando dos pilas en 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()!)
            }
        }
    }
}
davejlin
fuente
1

Si bien obtendrá muchas publicaciones relacionadas con la implementación de una cola con dos pilas: 1. O bien haciendo que el proceso enQueue sea mucho más costoso 2. O haciendo que el proceso deQueue sea mucho más costoso

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

Una forma importante que descubrí en la publicación anterior fue construir una cola con solo la estructura de datos de la pila y la pila de llamadas de recursión.

Si bien uno puede argumentar que, literalmente, esto todavía está usando dos pilas, pero idealmente esto está usando solo una estructura de datos de pila.

A continuación se muestra la explicación del problema:

  1. Declare una sola pila para enQueuing y deQueuing de los datos e inserte los datos en la pila.

  2. mientras que la eliminación de la cola tiene una condición básica en la que el elemento de la pila se apila cuando el tamaño de la pila es 1. Esto asegurará que no haya desbordamiento de la pila durante la recursión deQueue.

  3. Mientras se quita la cola, primero saque los datos de la parte superior de la pila. Idealmente, este elemento será el elemento que está presente en la parte superior de la pila. Ahora, una vez hecho esto, llame de forma recursiva a la función deQueue y luego empuje el elemento que aparece arriba nuevamente en la pila.

El código se verá a continuación:

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;

De esta manera, puede crear una cola utilizando una estructura de datos de una sola pila y la pila de llamadas de recursión.

Radioactivo
fuente
1

A continuación se muestra la solución en lenguaje javascript usando la sintaxis 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 };

A continuación se muestra el 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"
Jyoti Prasad Pal
fuente
Esto está molesto. Si coloca más elementos en la cola después de la extracción, los colocará stack1. Cuando vayas de dequeuenuevo, los moverás a elementos stack2, colocándolos por delante de lo que ya estaba allí.
Alexander - Restablece a Mónica el
0

Contestaré esta pregunta en Go porque Go no tiene muchas colecciones ricas en su biblioteca estándar.

Como una pila es realmente fácil de implementar, pensé en intentar usar dos pilas para lograr una cola de doble finalización. Para comprender mejor cómo llegué a mi respuesta, he dividido la implementación en dos partes, espero que la primera parte sea más fácil de entender, pero 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:]
    }
}

Básicamente son dos pilas donde permitimos que la parte inferior de las pilas sea manipulada entre sí. También utilicé las convenciones de nomenclatura STL, donde las operaciones tradicionales de inserción, extracción y peek de una pila tienen un prefijo frontal / posterior, ya sea que se refieran al frente o al reverso de la cola.

El problema con el código anterior es que no usa la memoria de manera muy eficiente. En realidad, crece sin cesar hasta que te quedas sin espacio. Es realmente malo. La solución para esto es simplemente reutilizar la parte inferior del espacio de la pila siempre que sea posible. Tenemos que introducir un desplazamiento para rastrear esto, ya que un segmento en Go no puede crecer en el frente una vez encogido.

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

Son muchas funciones pequeñas, pero de las 6 funciones, 3 de ellas son solo espejos de la otra.

John Leidegren
fuente
Estás usando matrices aquí. No veo dónde están tus pilas.
melpomene
@melpomene OK, si miras más de cerca notarás que las únicas operaciones que estoy realizando es agregar / eliminar el último elemento de la matriz. En otras palabras, empujando y haciendo estallar. Para todos los efectos, son pilas pero se implementan utilizando matrices.
John Leidegren
@melpomene En realidad, eso es solo la mitad, supongo que las pilas de doble punta. Estoy permitiendo que la pila se modifique de una manera no estándar de abajo hacia arriba bajo ciertas condiciones.
John Leidegren
0

Aquí está mi solución en Java usando Linkedlist.

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: En este caso, la operación pop lleva mucho tiempo. Por lo tanto, no sugeriré crear una cola con dos pilas.

Irshad ck
fuente
0

Con O(1) dequeue(), que es lo mismo que la respuesta de 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()

Con O(1) enqueue()(esto no se menciona en esta publicación, por lo que esta respuesta), que también utiliza el retroceso para burbujear y devolver el elemento más 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, es un buen ejercicio de codificación, ya que es ineficiente pero elegante.

FELICIDAD
fuente
0

** Solución JS fácil **

  • Nota: tomé ideas del comentario de otras personas

/*

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

*/
class myQueue {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    push(item) {
        this.stack1.push(item)
    }

    remove() {
        if (this.stack1.length == 0 && this.stack2.length == 0) {
            return "Stack are empty"
        }

        if (this.stack2.length == 0) {

            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }
        return this.stack2.pop()
    }


    peek() {
        if (this.stack2.length == 0 && this.stack1.length == 0) {
            return 'Empty list'
        }

        if (this.stack2.length == 0) {
            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }

        return this.stack2[0]
    }

    isEmpty() {
        return this.stack2.length === 0 && this.stack1.length === 0;
    }

}

const q = new myQueue();
q.push(1);
q.push(2);
q.push(3);
q.remove()

console.log(q)

RANJAN CENIZO
fuente
-1
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 operación en cola, agregamos a la parte superior de la pila1. Para cada dequeue, vaciamos el contenido de stack1 en stack2, y eliminamos el elemento en la parte superior de la pila. La complejidad del tiempo es O (n) para dequeue, ya que tenemos que copiar el stack1 a stack2. La complejidad temporal de la cola es la misma que la de una pila normal

PradGar
fuente
Este código es ineficiente (copia innecesaria) y está roto: if (stack2 != null)siempre es cierto porque stack2se crea una instancia en el constructor.
melpomene
-2

Implementación de cola usando dos objetos java.util.Stack:

public final class QueueUsingStacks<E> {

        private final Stack<E> iStack = new Stack<>();
        private final Stack<E> oStack = new Stack<>();

        public void enqueue(E e) {
            iStack.push(e);
        }

        public E dequeue() {
            if (oStack.isEmpty()) {
                if (iStack.isEmpty()) {
                    throw new NoSuchElementException("No elements present in Queue");
                }
                while (!iStack.isEmpty()) {
                    oStack.push(iStack.pop());
                }
            }
            return oStack.pop();
        }

        public boolean isEmpty() {
            if (oStack.isEmpty() && iStack.isEmpty()) {
                return true;
            }
            return false;
        }

        public int size() {
            return iStack.size() + oStack.size();
        }

}
realPK
fuente
3
Este código es funcionalmente idéntico a la respuesta de Dave L. No agrega nada nuevo, ni siquiera una explicación.
melpomene
Agrega los métodos isEmpty () y size () junto con el manejo básico de excepciones. Lo editaré para agregar una explicación.
realPK
1
Nadie pidió esos métodos adicionales, y son triviales (una línea cada uno): return inbox.isEmpty() && outbox.isEmpty()y return inbox.size() + outbox.size(), respectivamente. El código de Dave L. ya arroja una excepción cuando se retira de una cola vacía. La pregunta original ni siquiera era sobre Java; se trataba de estructuras de datos / algoritmos en general. La implementación de Java fue solo una ilustración adicional.
melpomene
1
Esta es una gran fuente para las personas que buscan entender cómo construir colas a partir de dos pilas, los diagramas definitivamente me ayudaron más que leer la respuesta de Dave.
Kemal Tezer Dilsiz
@melpomene: no se trata de métodos triviales sino de necesidad. La interfaz de cola en Java extiende esos métodos desde la interfaz de Colección porque son necesarios.
realPK