232.用栈实现队列

题目描述：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

解题思路：

运用两个栈，输入栈和输出栈来实现队列的操作

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;


    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();

    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        dumpstackIn();
        return stackOut.pop();

    }
    
    public int peek() {
        dumpstackIn();
        return stackOut.peek();

    }
    
    public boolean empty() {
        return stackOut.isEmpty() && stackOut.isEmpty();

    }
    
        //复用函数dumpstackIn来完成pop和peek的动作
        //因为pop和peek都是要将输入栈的数据导入输出栈
    private void dumpstackIn(){
        if (stackOut.isEmpty()){
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }
    }
}
    
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

225. 用队列实现栈

题目描述：
使用队列实现栈的下列操作：

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

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

理论知识：

队列的操作：
·添加元素：add() 抛异常;offer(); 返回null
·返回第一个元素：element() 抛异常; peek() null;
·删除第一个元素：remove() 抛异常; poll() null;
·判断队列是否为空：isEmpty();
栈的操作：
·把项压入栈顶：push()
·查看栈顶元素：不删除：peek();
·移除栈顶元素：pop();
·判断栈是否为空：Empty();

解题方法：单向队列

解题思路：
利用两个队列来模拟栈，队列1为保持跟栈一样顺序的队列，队列2则是辅助操作；
1.push()：新增的元素相放到队列2中，判断队列1状态：
如果队列1为空，则直接交换两队元素，队列2始终保持为空；
如果队列1不为空，则先将队列1的元素依次放入队列2中，再交换q1和q2
2.pop();top();Empty()操作都只需对q1操作即可

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>(); //q1用来保持跟站内一样顺序的元素
        q2 = new LinkedList<>(); //q2用来做辅助操作

    }
    
    public void push(int x) {
        q2.offer(x);
        //判断q1是否为空，若为空直接交换q1和q2元素；若不为空，就将q1的元素依次放入q2
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        //交换q1和q2的元素，保存在q1中
        Queue<Integer> temp = new LinkedList<>();
        temp = q1;
        q1 = q2;
        q2 = temp;

    }
    
    public int pop() {
        return q1.poll();

    }
    
    public int top() {
        return q1.peek();

    }
    
    public boolean empty() {
        return q1.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();
 */