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


思路

队列是先进先出的,而栈是后进先出的,如何用两个栈来实现队列的效果呢?

我们假设只用 stack1 来存放元素,这样的话,直接 stack1.pop 是行不通的。每次要弹出元素时,将 stack1 的元素全部弹出,依次存放到 stack2 中,这样原本在 stack1 最底下的元素,就来到了 stack2 的顶部,使用 stack2.pop 就可以得到我们想要的结果。

import java.util.Stack;
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()) {
            throw new RuntimeException("Queue is empty");
        }
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

小结

熟悉栈后进先出的特点,说不定在有些题目会派上大用场。用一种数据结构模拟另一种数据结构,要结合其特性去思考。


内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/Yee-Q/p/13671256.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!