Implement Queue using Stacks

Implement Queue using Stacks

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2

Naive Way: 我自己试着写了一个。

这个dequeue和enqueue都不能做到O(1)，只有当连续进行单个dequeue或者单个enqueue的指令时，才会实现O(1)的效率。

/*
* I figure out a way to implement queue by two stacks
* However, only when consecutive pop() or consecutive push()
* are conducted, there is efficiency.
*/
import java.util.Stack;
public class StackQueue<Item>{

    public static void main(String args[]){
        StackQueue<Integer> sq = new StackQueue<Integer>();
        sq.enqueue(1);
        sq.enqueue(2);
        sq.enqueue(5);
        System.out.println(sq.dequeue());
    }

    private Stack<Item>stack1;
    private Stack<Item> stack2;

    public StackQueue(){
        stack1 = new Stack<Item>();
        stack2 = new Stack<Item>();
    }

    public Item dequeue(){
        if(!stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.isEmpty()?null:stack2.pop();
    }

    public void enqueue(Item e){
        if(!stack2.isEmpty()){
            while(!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
        }
        stack1.push(e);
    }

    public boolean isEmpty(){
        return stack1.isEmpty() && stack2.isEmpty();
    }

}
Improved Way: 后来看了别人的做法，也是不能使两个operation都是O(1)，而是让其中某个成为O(1)，另一个是O(n)。我觉得跟我的方法思路一样的。总之就是无法让两种operation都变成O(1)。

public Item dequeue(){
        while(!stack1.isEmpty()){stack2.push(stack1.pop());}
        Item e = stack2.isEmpty()?null:stack2.pop();
        while(!stack2.isEmpty()){stack1.push(stack2.pop());}
        return e;
    }

    public void enqueue(Item e){
        stack1.push(e);
    }