欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

用栈实现队列

程序员文章站 2024-01-28 21:44:46
...

我们知道,栈是先进后出的数据结构,队列是先进先出的数据结构,用栈实现队列,可以用两个栈实现,如下图所示,先入栈的也是先出栈的
用栈实现队列

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();

    }
    
    public void push(int x) {
        stack1.push(x);
    }
    //在这里是不是有人和我犯了同样的错误呢?直接返回 stack2.pop();
    //出栈的时候需要判断 stack2 是不是空栈
    //如果是空栈,就不能 pop
    //所以当是空栈时,我们需要将 stack1 中的元素插入到 stack2 中,前提是 stack1 不能为空
    //如果不是空栈,直接返回 stack2.pop();
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    //同样,返回栈顶元素和出栈类似,需要作以判断
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
   //判断空时需要同时两个栈都为空
    public boolean empty() {
        return stack1.isEmpty()&&stack2.isEmpty();
    }
}