【剑指offer】面试题9：用两个栈实现队列

落日映苍穹つ 2022-06-12 03:12 152阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

## 思路 ##

两个栈分别为stack1和stack2  
stack1专门用来push  
stack2专门用来pop  
当stack2执行pop操作时，检查stack2是否为空，为空的话则将执行操作：

while(stack1.empty()) {
        stack2.push(stack1.pop());
    }

## 代码 ##

Stack<Integer> stack1 = new Stack<>();  // 用来push
    Stack<Integer> stack2 = new Stack<>();  // 用来pop
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.empty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
    
        if(stack2.empty())
            throw new RuntimeException("Queue is empty!");
    
        return stack2.pop();
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    /**
     * 往空的队列里添加、删除元素
     */
    private static void test1() {
        _09_QueueWithTwoStacks q = new _09_QueueWithTwoStacks();
        q.push(1);
        q.pop();
    }
    
    /**
     * 往非空的队列里面添加、删除元素
     */
    private static void test2() {
        _09_QueueWithTwoStacks q = new _09_QueueWithTwoStacks();
        for(int i = 0; i < 5; ++i) {
            q.push(i);
        }
        for(int i = 0; i < 5; ++i) {
            System.out.print(q.pop() + " ");
        }
        System.out.println();
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews