由两个栈组成的队列

一颗蔬菜 2019-09-14 PM 55℃ 0条

【题目】

编写一个类,用两个栈实现队列,支持队列的基本操作(add、poll、peek)。

【解答】

栈的特点是先进后出,而队列的特点是先进后出。我们用两个栈正好能把顺序反过来实现类似队列的操作。
具体实现是一个栈作为压入栈,压入数据时只往这个栈中压入,记为stackPush;另一个栈只作为弹出栈,在弹出数据时只从这个栈弹出,记为stackPop。
将数据压入stackPush栈时,顺序时先进后出的,再将stackPush栈中的数据弹出并压入stackPop时,顺序又变回来了,从整体上来看,实现的功能就是先进先出。

【代码实现】

import java.util.Stack;

public class leetcode1 {
    private Stack<Integer> stackPush;
    private Stack<Integer> stackPop;
    
    public  leetcode1() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }

    public void add(int[] nums) {
        for (int i = 0; i < nums.length; i ++) {
            stackPush.push(num);            
        }
        if (stackPop.isEmpty()) {
            push();
        }
    }

    public int poll() {
        if (stackPop.isEmpty() && stackPush.isEmpty()) {
            throw new RuntimeException("The queue is empty.");
        }
        push();
        return stackPop.pop();
    }

    public int peek() {
        if (stackPop.isEmpty() && stackPush.isEmpty()) {
            throw new RuntimeException("This queue is empty.");
        }
        push();
        return stackPop.peek();
    }

    public void push() {
        // stackPop必须为空
        if (stackPop.isEmpty()) {
            // 必须一次性压入才能保证顺序正确
            while (!stackPush.isEmpty()) {
                stackPop.push(stackPush.pop());
            }
        }
    }

}
标签: 算法

非特殊说明,本博所有文章均为博主原创。