【算法题】由两个栈组成的队列

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

解题思路

为了实现栈后进先出的特点,设计栈stackPush用于实现add,栈stackPop用于实现polladd操作永远在stackPush上执行;对于poll操作,如果stackPop有元素,则直接从stackPop弹出,否则先把元素从stackPush导入到stackPop,然后再从stackPop弹出。

实现代码

import java.util.Stack;

public class MyQueue {
    private Stack<Integer> stackPush;
    private Stack<Integer> stackPop;

    public MyQueue() {
        this.stackPush = new Stack<>();
        this.stackPop = new Stack<>();
    }

    public void add(int num) {
        stackPush.push(num);
    }

    public int poll() {
        if (stackPop.empty() && stackPush.empty()) {
            throw new RuntimeException("Queue is empty");
        }

        if (stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.pop());
            }
        }

        return stackPop.pop();
    }

    public int peek() {
        if (stackPop.empty() && stackPush.empty()) {
            throw new RuntimeException("Queue is empty");
        }

        if (stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.pop());
            }
        }

        return stackPop.peek();
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容