【LeetCode】用两个栈实现队列 Java 题解

关注

发布于: 4 小时前

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：
输入：["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输出：[null,null,3,-1]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

栈和队列是常见的数据结构，栈的特点：LIFO(last-in-first-out), 队列的特点：FIFO (first-in-first-out)。
根据题意，使用两个栈就可以实现队列，代码如下。

代码

class CQueue {        Stack<Integer> headStack;     Stack<Integer> tailStack; 
    public CQueue() {        headStack = new Stack<>();        tailStack = new Stack<>();    }        public void appendTail(int value) {        headStack.push(value);    }        public int deleteHead() {        if (tailStack.isEmpty()) {            while (!headStack.isEmpty()) {                tailStack.push(headStack.pop());            }        }
        if (!tailStack.isEmpty()) {            int ans = tailStack.pop();            return ans;        }                return -1;    }}
/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持每日一题，加油！

发布于: 4 小时前阅读数: 4

原文链接:【http://xie.infoq.cn/article/5051b1842735254b092e52d89】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】用两个栈实现队列 Java 题解

题目描述

思路分析

代码

总结

HQ数字卡

评论