算法学习day10:用栈实现队列,用队列实现栈(Java)

发布时间:2024年01月23日

前言:栈和队列是程序中两种不同的存储数据的方式。队列就像超市里的收银排队一样,先进行排队的先出去,后进行排队的后出去。栈就像羽毛球筒一样,把一个个羽毛球(数据)放进去,最先放进去的数据最后拿出来,最后放进去的数据最先拿出来。

用栈实现队列

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

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
说明:
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

思路:
队列是先进先出,和栈不一样。如果在队列里输入数据1 2 3,取出来的结果也是1 2 3,但如果是栈的话,输出结果是3 2 1(反转)

结合前面的字符串反转的知识(一个字符串反转两次和原来一样),我们需要两个栈,让第一个栈的输出(3 2 1)成为第二个栈的输入,这样第二个栈也能输出1 2 3了

但是队列的数据并不是一次性全部输出的,可能先输入3个,输出1个,再输入2个,这就需要我们对第一个栈(以下简称为入栈)和第二个栈(以下简称为出栈)进行对应的条件判定

输出的时候,我们应该先判断入栈是否为空,如果不是的话就把数据全部放到出栈去,再进行输出的操作,因为之后大部分操作会用到,在代码里可以包装成一个方法(即下面的moveIntoOut)

代码如下:

public class MyQueue {
    Stack<Integer> sIn;
    Stack<Integer> sOut;

    public MyQueue(){
        sIn = new Stack<>();
        sOut = new Stack<>();
    }

    private void moveIntoOut(){//把入栈的元素全部放到出栈里
        if(!sOut.isEmpty()){return;}
        while (!sIn.isEmpty()){
            sOut.push(sIn.pop());
        }
    }

    public void push(int x){//将一个元素放到队列尾部
        sIn.push(x);
    }

    public void pop(){//从队列首部移除元素
        moveIntoOut();
        sOut.pop();
    }

    public int peek(){//返回队列首部的元素
        moveIntoOut();
        return sOut.peek();
    }

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

注意事项:进行pop和peek操作之前要先清空入栈,不然返回的顺序不对
以及,moveIntoOut中,如果出栈不是空的话,是不能对出栈添加元素的,具体原因可以画图方便理解

用队列实现栈

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

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空
注意:
你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)

思路:
上面我们用两个栈实现了队列,那这里大家可能也会惯性思维用两个队列去实现栈,但实际上一个队列就足够了,栈输入时正常对队列输入,模拟栈输出时,我们需要把队列的size - 1个元素重新输入队列,如:
对栈输入1 2 3,得到(入口) 1 2 3
对队列输入1 2 3,得到(入口) 1 2 3(出口)

此时栈的输出应该是1,我们想在出口输出1的话,把2和3重新排序,如下:
(入口)2 3 1(出口)
这样的输出就可以达成目标。

总结一下,上面的思路是:输出时,把队列的输出当成输入,重复size - 1次
代码如下:

public class MyStack {
    Queue<Integer> q1;
    public MyStack(){
        q1 = new LinkedList<>();
    }

    private void paixu(){//通过排序,把最后一个元素放在最前面
        int size = q1.size();
        for (int i = 0; i < size - 1; i++) {
            q1.add(q1.poll());
        }
    }

    public void push(int x){
        q1.add(x);
    }

    public void pop(){
        paixu();
        q1.poll();
    }

    public int top(){
        paixu();
        int result = q1.poll();
        q1.add(result);
        return result;
    }

    public boolean empty(){
        return q1.isEmpty();
    }
}
文章来源:https://blog.csdn.net/2301_80840872/article/details/135760834
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。