Use stack (LIFO) to simulate queue (FIFO)

原创转载请注明出处：http://agilestyle.iteye.com/blog/2360962

 

Solution

1. Using 2 stacks

1.1. One stack to accept incoming values in FILO manner

1.2. The other stack to reverse the values in first stack, so LIFO+LIFO becomes FIFO for value retrieval

 

2. An example

2.1. Incoming order: (1,2,3)

2.2. Stack 1 storage order(top to bottom): (3,2,1)

2.3. Stack 2 after pushing and popping all values in Stack 1:(top to bottom): (1,2,3)

 

3. One important thing

The reverse of all values in Stack 1 to stack 2 happens only stack 2 is empty!!!

 

package org.fool.java.test;

import java.util.Stack;

public class MyStackQueueTest {
    public static void main(String[] args) throws Exception {
        MyStackQueue<Integer> q = new MyStackQueue<>();
        q.enQueue(1);
        q.enQueue(2);
        q.enQueue(3);
        q.enQueue(4);

        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());

        q.enQueue(5);
        q.enQueue(6);
        q.enQueue(7);

        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
    }
}

class MyStackQueue<T> {
    Stack<T> s1 = new Stack<>();
    Stack<T> s2 = new Stack<>();

    public void enQueue(T k) {
        s1.push(k);
    }

    public T deQueue() throws Exception {
        if(s2.isEmpty() && s1.isEmpty()) {  // if no elements at all
            throw new Exception("no elements!");
        } else if(s2.isEmpty()) {   // get all elements in s1 and save to s2
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }

        return s2.pop();
    }
}

Console Output

 

Reference

https://www.youtube.com/watch?v=fPHXQP3Flno&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG&index=31&spfreload=10