栈和队列-队列的练习题

1.  用队列实现栈

题目解析:

 题目链接:. - 力扣（LeetCode）

我们需要俩个队列来实现栈的入栈和出栈操作;

首先我们创建俩个队列qu1和qu2并且我们生成相应的构造方法;

解题步骤:

1. 哪个队列不为空,我就把元素放到哪个队列里面去(如果俩个都是空的,那就指定放到第一个里面去)

2. 出栈的时候,哪个不为空,我们就往这个队列放size - 1个元素

3. 当俩个队列都为空的时候,我们模拟的栈就是空的

及具体代码:

class MyStack {
    //先生成俩个队列
    private Queue<Integer> qu1;
    public Queue<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        }else if(!qu2.isEmpty()) {
            qu2.offer(x);
        }else {
            //俩个队列都是空的 指定存放到第一个队列当中
            qu1.offer(x);
        }
    }

    public int pop()  {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for (int i = 0; i < size - 1; i++) {//qu1.size()是一个变量,每次循环一次它都会变化
                //从队列1把元素取出来
                int x = qu1.poll();
                //放到que2里面去
                qu2.offer(x);
            }
            //返回qu1里面剩下的元素
            return qu1.poll();
        }else {
            int size = qu2.size();
            for (int i = 0; i < size - 1; i++) {
                //从队列2把元素取出来
                int x = qu2.poll();
                //放到que1里面去
                qu2.offer(x);
            }
            //返回qu2里面剩下的元素
            return qu2.poll();
        }
    }
//TODO 获取栈顶元素
    public int top() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            int x = -1;
            for (int i = 0; i < size; i++) {//qu1.size()是一个变量,每次循环一次它都会变化
                //从队列1把元素取出来
                 x = qu1.poll();
                //放到que2里面去
                qu2.offer(x);
            }
            //返回qu1里面最后一个元素
            return x;
        }else {
            int size = qu2.size();
            int x = -1;
            for (int i = 0; i < size; i++) {
                //从队列2把元素取出来
                 x = qu2.poll();
                //放到que1里面去
                qu2.offer(x);
            }
            //返回qu2里面剩下的元素
            return x;
        }
    }

    public boolean empty() {
        //俩个队列同时为空的时候 说明模拟实现的栈是空的
        return qu2.isEmpty() && qu1.isEmpty();
    }
}

2.  用栈实现队列

题目解析:

 题目链接:. - 力扣（LeetCode）

我们需要俩个栈来实现队列的入队和出队操作;

首先我们先创建俩个栈:s1,s2,并且创建一个构造方法,生成俩个栈

解题的话分别分为以下俩个步骤:

1. 入队的时候,全部放在第一个栈里面

也就是s1.push(要放入的元素)

2. 出队的时候 我们在第二个栈里面出队,当第二个栈里面没有元素的时候,把第一个栈里面的元素全部放进来

其他方法介绍:

判断队空 empty()

        我们只有当s1和s2没有元素的时候才是队空.

观察队头元素

        我们直接在pop的基础上返回s2的栈顶元素即可

具体代码:

class MyQueue {
    //设置俩个栈
    //1. 入队的时候放在第一个栈里面
    //2. 出队的时候放在第二个栈里面,当第二个栈里面没有元素的时候.把第一个栈里面的元素全部移过来

    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {

        //我们先把元素都放在第一个栈里面
        s1.push(x);
    }

    public int pop() {
        if(empty()) {
            return -1;
        }
        //如果不为空,我们先把s1所有的元素放到s2中去
        if (s2.empty()) {
            while (!s1.empty()){
            int tmp = s1.pop();
            s2.push(tmp);
            }
        }
        //然后我们就返回s2的栈顶元素
        return s2.pop();
    }

    public int peek() {
        if(empty()) {
            return -1;
        }
        //如果不为空,我们先把s1所有的元素放到s2中去
        if (s2.empty()) {
            while (!s1.empty()){
                int tmp = s1.pop();
                s2.push(tmp);
            }
        }
        //然后我们就返回s2的栈顶元素
        return s2.peek();
    }
//俩个栈同时为空才是队空
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}