Implement Queue using Stacks

解题思路：采用两个栈，实现队列，一个用于进栈S1，一个用于出栈和取头元素S2。进栈时必须将S2中元素全部加入S1中，出栈时必须将S1中的元素加入S2中，才可以保证先进先出。判断为空时，S1，S2均为空。

Java代码实现：

class MyQueue {
   private Stack stack1;
	private Stack stack2;
	MyQueue(){
		stack1=new Stack();
		stack2=new Stack();
	}
    // Push element x to the back of queue.
    public void push(int x) {
       if(stack2.isEmpty()) stack1.push(x);
       else {
    	   while(!stack2.isEmpty()){
    		   stack1.push(stack2.peek());
    		   stack2.pop();
    	   }
    	   stack1.push(x);
       }
    }

    // Removes the element from in front of queue.
    public void pop() {
        if(stack1.isEmpty()) {
            if(!stack2.isEmpty())
                stack2.pop();
        }
        else {
        	while(!stack1.isEmpty()){
        		stack2.push(stack1.peek());
        		stack1.pop();
        	}
        	stack2.pop();
        }
    }

    // Get the front element.
    public int peek() {
    	if(stack1.isEmpty()) {
    	    if(!stack2.isEmpty())
    	        return (int) stack2.peek();
    	    return -1;
    	}
        else {
        	while(!stack1.isEmpty()){
        		stack2.push(stack1.peek());
        		stack1.pop();
        	}
        	return (int) stack2.peek();
        }
    }

    // Return whether the queue is empty.
    public boolean empty() {
        if(stack1.isEmpty()&&stack2.isEmpty()) return true;
        else return false;
    }
}

原题地址：https://leetcode.com/problems/implement-queue-using-stacks/



版权声明：本文为博主原创文章，未经博主允许不得转载。