it-swarm-es.tech

¿Cómo implementar una cola usando dos pilas?

Supongamos que tenemos dos pilas y ninguna otra variable temporal.

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

372
Nitin

Mantén 2 pilas, llamémoslas inbox y outbox.

Encolar :

  • Empuje el nuevo elemento en inbox

Dequeue :

  • Si outbox está vacío, rellénelo haciendo estallar cada elemento de inbox y presionándolo sobre outbox

  • Pop y devuelve 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();
    }

}
673
Dave L.

A - Cómo invertir una pila

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

Imaginemos nuestra pila como una botella como abajo;

 enter image description here

Si presionamos enteros 1,2,3 respectivamente, entonces 3 estarán en la parte superior de la pila. Debido a que 1 será empujado primero, luego 2 se colocará en la parte superior de 1. Finalmente, 3 se colocará en la parte superior de la pila y el último estado de nuestra pila representada como una botella será la siguiente:

 enter image description here

Ahora tenemos nuestra pila representada ya que una botella 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?

 enter image description here

Sí podemos hacerlo, pero eso es una botella. Para hacer el mismo proceso, necesitamos tener una segunda pila que almacenará 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 a medida que lo hacemos en la imagen de abajo;

 enter image description here

Así que sabemos cómo revertir 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 pila. Esto fue importante, ya que si presionamos y colocamos elementos en la pila, la salida será exactamente en el orden inverso 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 empuje, que será {5, 4, 3, 2, 1} Recuerde que para la misma entrada, si sacamos la cola de 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 la inversa de la salida de una pila. Como sabemos cómo invertir una pila usando una pila extra, podemos construir una cola usando dos pilas.

Nuestro modelo de cola constará de dos pilas. Se utilizará una pila para la operación enqueue (pila n. ° 1 a la izquierda, se llamará como pila de entrada), otra pila se utilizará para la operación dequeue (pila n. ° 2 a la derecha, se llamará como pila de salida). Echa un vistazo a la imagen de abajo;

 enter image description here

Nuestro pseudo-código es el siguiente;


Operación en cola

Push every input element to the Input Stack

Operación Dequeue

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and Push them to the Output Stack until Input Stack is Empty

pop from Output Stack

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

 enter image description here

Entonces, ¿qué sucederá si ejecutamos una operación de salida? Cada vez que se ejecuta una operación de salida de cola, la cola comprobará si la Pila de salida está vacía o no (vea el pseudo-código arriba) Si la Pila de salida está vacía, entonces 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;

 enter image description here

Verifique el orden de los elementos en la pila de salida (pila n. ° 2). Es obvio que podemos extraer los elementos de la pila de salida para que la salida sea la misma que si se sacara de la cola. Por lo tanto, si ejecutamos dos operaciones de salida de 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;

 enter image description here

Ahora, la Pila de salida no está vacía, y si ejecutamos una operación de salida de cola, solo 3 saldrán de la Pila de salida. Entonces el estado será visto como abajo;

 enter image description here

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

 enter image description here

Fácil de ver, la salida de las dos operaciones de salida de la 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, por lo 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
195
Levent Divilioglu

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

El principio sigue siendo el mismo cuando se inserta un nuevo elemento en la cola:

  • Necesitas transferir elementos de una pila a otra pila temporal para revertir su orden.
  • Luego, empuje el nuevo elemento a insertar, en la pila temporal
  • Luego transfiere los elementos 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 que se abrirá)

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

Sin embargo, las complejidades del tiempo serían peores. Una buena implementación de cola hace todo en tiempo constante.

Editar

No estoy seguro de por qué mi respuesta ha sido rechazada aquí. Si programamos, nos preocupa 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 votar más abajo, me gustarí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 cola de salida cuando la bandeja de salida está vacía, necesita tiempo lineal para llegar al final bandeja de entrada (como se 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 convirtiéndolo en una lista cíclica). Implementar la cola y la cola de espera en esta estructura de datos es muy fácil de hacer en un tiempo constante. Ese es el peor de los casos en 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.

11
Tyler

Deje que la cola a ser implementada sea q y las pilas utilizadas para implementar q sean pila1 y pila2.

q se puede implementar en dos maneras:

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

Este método se asegura de que el elemento recién ingresado esté siempre en la parte superior de la pila 1, de modo que la operación de DEQueue simplemente salga de la pila1. Para poner el elemento en la parte superior de stack1, se usa 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 de 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 cola de espera, si la pila2 está vacía, todos los elementos se mueven a la pila2 y finalmente se devuelve la parte superior de la pila2.

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 la pila2 está vacía.

7
Rahul Gandhi

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

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 "salida de cola".

2
user11055

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

Dos pilas en la cola se definen como pila1pila2.

En cola: Los elementos euqueued siempre se insertan en pila1

Dequeue: La parte superior de pila2 puede ser desplegado ya que es el primer elemento insertado en la cola cuando pila2 no está vacío. Cuando pila2 está vacío, sacamos todos los elementos de pila1 y empujarlos en pila2 uno a uno. El primer elemento de una cola se inserta en la parte inferior de pila1. Se puede desplegar directamente después de las operaciones de popping y push ya que está en la parte superior de pila2.

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

2
Harry He
// Two stacks s1 Original and s2 as Temp one
    private Stack<Integer> s1 = new Stack<Integer>();
    private Stack<Integer> s2 = new Stack<Integer>();

    /*
     * Here we insert the data into the stack and if data all ready exist on
     * stack than we copy the entire stack s1 to s2 recursively and Push the new
     * element data onto s1 and than again recursively call the s2 to pop on s1.
     * 
     * Note here we can use either way ie We can keep pushing on s1 and than
     * while popping we can remove the first element from s2 by copying
     * recursively the data and removing the first index element.
     */
    public void insert( int data )
    {
        if( s1.size() == 0 )
        {
            s1.Push( data );
        }
        else
        {
            while( !s1.isEmpty() )
            {
                s2.Push( s1.pop() );
            }
            s1.Push( data );
            while( !s2.isEmpty() )
            {
                s1.Push( s2.pop() );
            }
        }
    }

    public void remove()
    {
        if( s1.isEmpty() )
        {
            System.out.println( "Empty" );
        }
        else
        {
            s1.pop();

        }
    }
1
imvp

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

Si bien obtendrá una gran cantidad de publicaciones relacionadas con la implementación de una cola con dos acumulaciones: 1. Haciendo que el proceso de enQueue sea mucho más costoso 2. O haciendo que el proceso de 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 se puede argumentar que, literalmente, esto todavía está usando dos pilas, pero idealmente, se 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 deQueing los datos y empuje los datos en la pila.

  2. mientras que el deQueueing tiene una condición base donde el elemento de la pila se abre cuando el tamaño de la pila es 1. Esto asegurará que no haya un desbordamiento de pila durante la recursión del deQueue.

  3. Mientras que deQueueing primero pop 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, recursivamente llame a la función deQueue y luego presione el elemento que se encuentra arriba 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 pila única y la pila de llamadas de recursión.

1
Radioactive

aquí está mi solución en Java usando la lista enlazada.

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 de pop consume mucho tiempo. Así que no sugeriré crear una cola usando dos pilas.

0
Irshad ck

Responderé esta pregunta en Go porque Go no tiene una gran cantidad de colecciones en su biblioteca estándar.

Dado que una pila es realmente fácil de implementar, pensé que intentaría 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, es de esperar 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:]
    }
}

Son básicamente dos pilas donde permitimos que la parte inferior de las pilas se manipulen unas con otras. También he usado las convenciones de nomenclatura de STL, donde las operaciones tradicionales de empujar, estallar y echar un vistazo de una pila tienen un prefijo delantero/trasero, ya sea que se refieran al frente o al dorso 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 hacer un seguimiento de esto, ya que una porción en Ir no puede crecer en el frente una vez que se ha reducido.

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.

0
John Leidegren

A continuación se muestra la solución en lenguaje javascript utilizando 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"
0
Jyoti Prasad Pal
public class QueueUsingStacks<T>
{
    private LinkedListStack<T> stack1;
    private LinkedListStack<T> stack2;

    public QueueUsingStacks()
    {
        stack1=new LinkedListStack<T>();
        stack2 = new LinkedListStack<T>();

    }
    public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
    {
        while(source.Head!=null)
        {
            dest.Push(source.Head.Data);
            source.Head = source.Head.Next;
        }
    }
    public void Enqueue(T entry)
    {

       stack1.Push(entry);
    }
    public T Dequeue()
    {
        T obj;
        if (stack2 != null)
        {
            Copy(stack1, stack2);
             obj = stack2.Pop();
            Copy(stack2, stack1);
        }
        else
        {
            throw new Exception("Stack is empty");
        }
        return obj;
    }

    public void Display()
    {
        stack1.Display();
    }


}

Para cada operación de puesta en cola, agregamos a la parte superior de la pila1. Para cada salida de cola, 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 la pila1 en stack2. La complejidad de tiempo de la puesta en cola es la misma que una pila regular

0
PradGar

Con O(1)dequeue(), que es igual que pythonquick's answer :

// 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 la función de retroceso para aumentar la velocidad 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 a pesar de todo.

0
hIpPy