**通过队列的api实现栈的功能

桃扇骨 2021-06-22 15:37 332阅读 0赞

使用队列实现栈的下列操作：

*  push(x) -- 元素 x 入栈
 *  pop() -- 移除栈顶元素
 *  top() -- 获取栈顶元素
 *  empty() -- 返回栈是否为空

**注意:**

*  你只能使用队列的基本操作-- 也就是 `push to back`, `peek/pop from front`, `size`, 和 `is empty` 这些操作是合法的。
 *  你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 *  你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

### 思路： ###

1、队列先进先出，栈先进后出，区别在于队列插到队尾，而栈是插在队头，如果能让队列实现头插法就可以

import java.util.LinkedList;
    import java.util.Queue;
    
    class MyStack {
    
    	private Queue<Integer> in;
    	private Queue<Integer> out;
    
    	/** Initialize your data structure here. */
    	public MyStack() {
    		in = new LinkedList<>();
    		out = new LinkedList<>();
    	}
    
    	/** Push element x onto stack. */
    	public void push(int x) {
    		in.offer(x); //每次push的时候，把out队列重新插到队尾，这样就像插到队头的效果
    		while (!out.isEmpty()){
    			in.offer(out.poll());
    		}
    		Queue temp = in;
    		in = out;
    		out = temp;
    	}
    
    	/** Removes the element on top of the stack and returns that element. */
    	public int pop() {
    		return out.poll();
    	}
    
    	/** Get the top element. */
    	public int top() {
    		return out.peek();
    	}
    
    	/** Returns whether the stack is empty. */
    	public boolean empty() {
    		return out.isEmpty();
    	}
    }
    
    /**
     * Your MyStack object will be instantiated and called as such:
     * MyStack obj = new MyStack();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.top();
     * boolean param_4 = obj.empty();
     */