¿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 en cola utilizando sólo las dos pilas?

Sep 16 '08 10:09 Nitin

A - Cómo invertir una pila

Para entender cómo construir una cola usando dos pilas, debes entender cómo invertir una pila con total claridad. Recuerda cómo funciona la pila, es muy similar a la pila de platos de tu cocina. El último plato lavado estará en la parte superior de la pila limpia, lo que se denomina último en entrar , primero en salir ( LIFO ) en informática.

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

Si empujamos los números enteros 1,2,3 respectivamente, entonces 3 estará en la parte superior de la pila. Debido a que 1 se empujará primero, luego 2 se colocará encima 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;

Ahora tenemos nuestra pila representada como una botella llena con los 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 sostenerla boca abajo para que todos los valores se inviertan en orden?

Sí, podemos hacer eso, pero es una botella. Para hacer el mismo proceso, necesitamos tener una segunda pila que almacenará los elementos de la primera 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, sacaremos cada elemento de la pila izquierda y los empujaremos a la pila derecha. Puedes ver lo que sucede mientras lo hacemos en la imagen a continuación;

Entonces sabemos cómo invertir una pila.

B - Usar dos pilas como cola

En la parte anterior, expliqué cómo podemos invertir el orden de los elementos de la pila. Esto era importante, porque si empujamos y colocamos elementos en la pila, la salida será exactamente en orden inverso a una cola. Pensando en un ejemplo, coloquemos la matriz de números enteros {1, 2, 3, 4, 5}en una pila. Si sacamos los elementos y los 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 esté vacía, la salida será {1, 2, 3, 4, 5}. Entonces 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 constará de dos pilas. Se usará una pila para enqueuela operación (la pila #1 a la izquierda, se llamará Pila de entrada), se usará otra pila para la dequeueoperación (la pila #2 a la derecha, se llamará Pila de salida). Mira la imagen a continuación;

Nuestro pseudocódigo es el siguiente;

Operación de puesta en cola

Push every input element to the Input Stack

Operación de salida de cola

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 números enteros se insertarán en la pila de entrada ( pila #1 ) que se encuentra a la izquierda;

Entonces, ¿qué pasará si ejecutamos una operación de retirada de la cola? Cada vez que se ejecuta una operación de eliminación de la cola, 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, 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;

Consulte 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 los quitáramos de la cola. Por lo tanto, si ejecutamos dos operaciones de eliminación de la 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;

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

Nuevamente, si ejecutamos dos operaciones más para sacar de la cola, en la primera operación de sacar de la cola, 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;

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

C - Implementación de cola construida con dos pilas

Aquí hay una implementación en Java. No voy a utilizar la implementación existente de Stack, por lo que el ejemplo aquí 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) MyQueue class : Queue Implementation Using Two Stacks

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) Demo Code

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) Sample Output

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5

Aug 22 '2016 23:08 Levent Divilioglu