剑指 Offer 09：用两个栈实现队列

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 81

题目： 用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

思路：
栈是后进先出（头插头取），假设输入 123，输出则是321
队列是先进先出（尾插头取），假设输入123，输出则是123.
建立一个输入栈stack1和输出栈stack2，将输入栈的元素移入输出栈，再将输出栈stack2的元素依次弹出，其效果即如队列。

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>(); //输入栈
    Stack<Integer> stack2 = new Stack<Integer>(); //输出栈
    public void push(int node) { //入队列，尾插
        stack1.push(node);
    }
    
    public int pop() { //出队列，头取
        if(stack1.empty()&&stack2.empty()){ // stack1 stack2 都没有
            return -1;
        }
        if(stack2.empty()){ //如果输出栈为空
            while(!stack1.empty()){ //将输入栈的元素倒入输出栈
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop(); //不管输出栈是否为空，最终都弹出一次输出栈，此时为队列顺序
    }
}

或：

class CQueue {
    Stack<Integer> s1=new Stack<>(); // 输入栈
    Stack<Integer> s2=new Stack<>(); // 输出栈
    public CQueue() {
    }
    
    public void appendTail(int value) {
        s1.push(value);
    }
    
    public int deleteHead() {
        if(s1.isEmpty() &&  s2.isEmpty()){ // stack1 stack2 都没有
            return -1;
        }
        if(!s2.isEmpty()){    // stack1不知， stack2 有！
            return s2.pop();
        }else{   // stack1有， stack2没有 ，则需要将stack1倒入stack2
            while(!s1.isEmpty()){                
                s2.push(s1.pop());
            }
            return s2.pop();
        }
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89375.html

剑指 Offer 09：用两个栈实现队列

相关推荐