package com.heu.wsq.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 225. 用队列实现栈
 * @author wsq
 * @date 2020/12/20
 * 使用队列实现栈的下列操作：
 *
 * push(x) -- 元素 x 入栈
 * pop() -- 移除栈顶元素
 * top() -- 获取栈顶元素
 * empty() -- 返回栈是否为空
 * 注意:
 *
 * 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
 * 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 * 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）
 *
 * 链接：https://leetcode-cn.com/problems/implement-stack-using-queues
 */
public class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /**
     * 将压入栈的元素放在现有队列的末尾
     * @param x
     */
    public void push(int x){
        if (queue2.isEmpty() && queue1.isEmpty()){
            this.queue1.add(x);
        }else if (queue2.isEmpty()){
            queue1.add(x);
        }else if (queue1.isEmpty()){
            queue2.add(x);
        }
    }

    public int pop(){
        // 这里可以调用 empty()函数判断是否存在元素
        Queue<Integer> outQueue;
        Queue<Integer> inQueue;
        if (!queue1.isEmpty()){
            outQueue = queue1;
            inQueue = queue2;
        }else{
            outQueue = queue2;
            inQueue = queue1;
        }
        while (outQueue.size() > 1){
            inQueue.add(outQueue.poll());
        }
        return outQueue.poll();
    }

    public int top(){
        Queue<Integer> outQueue;
        Queue<Integer> inQueue;
        if (!queue1.isEmpty()){
            outQueue = queue1;
            inQueue = queue2;
        }else{
            outQueue = queue2;
            inQueue = queue1;
        }
        while (outQueue.size() > 1){
            inQueue.add(outQueue.poll());
        }
        int tmp = outQueue.peek();
        inQueue.add(outQueue.poll());
        return tmp;
    }

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

    public static void main(String[] args) {
        MyStack ms = new MyStack();
        ms.push(10);
        ms.push(20);
        ms.pop();
        System.out.println(ms.top());
    }
}