@[toc]
同步GitHub在此 👉 https://github.com/TeFuirnever/GXL-Skill-Tree
- 剑指 Offer(C++版本)系列:总目录和一些提高效率的说明
- 剑指 Offer(C++版本)系列:剑指 Offer 03 数组中重复的数字
- 剑指 Offer(C++版本)系列:剑指 Offer 04 二维数组中的查找
- 剑指 Offer(C++版本)系列:剑指 Offer 05 替换空格
- 剑指 Offer(C++版本)系列:剑指 Offer 06 从尾到头打印链表
- 剑指 Offer(C++版本)系列:剑指 Offer 07 重建二叉树
1、题干
用两个栈实现队列 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 示例 1: 输入: ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出:[null,null,3,-1] 示例 2: 输入: ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出:[null,-1,null,null,5,2] 提示: 1 <= values <= 10000 最多会对 appendTail、deleteHead 进行 10000 次调用 通过次数202,426提交次数280,577
2、递归法
队列是先入先出,栈是先入后出。
算法流程:
- 加入队尾 appendTail(int value) 函数: 把数字 value 加入栈 stk 即可;
- 加入复制 copy(stack<int> &a, stack<int> &b) 函数,把栈 a 的元素复制到栈 b 中;</int></int>
- 删除队首 deleteHead() 函数:
- 当栈 stk 为空,即两个栈都为空,因此返回 -1 ;
- 把 stk 中所有元素 copy() 复制到 cache 中;
- 记录 cache 的栈顶元素,并删除该元素;
- 把 cache 中所有元素 copy() 复制到 stk 中;
- 直接返回被记录的栈顶元素。
//面试题09. 用两个栈实现队列 //标准做法 class CQueue { public: stack<int> stk, cache; CQueue() { } void appendTail(int value) { stk.push(value); } void copy(stack<int> &a, stack<int> &b) { while (a.size()) { b.push(a.top()); a.pop(); } } int deleteHead() { if (stk.empty()) { return -1; } copy(stk, cache); int res = cache.top(); cache.pop(); copy(cache, stk); return res; } }; /** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */
4、复杂度
/* 插入元素 时间复杂度:O(1)。 空间复杂度:O(n)。最差情况下,需要保存n个元素。 删除元素 时间复杂度:O(n)。 空间复杂度:O(n)。最差情况下,需要保存n个元素。 */
——————————————————————————————————————
- 剑指 Offer(C++版本)系列:总目录和一些提高效率的说明
- 剑指 Offer(C++版本)系列:剑指 Offer 03 数组中重复的数字
- 剑指 Offer(C++版本)系列:剑指 Offer 04 二维数组中的查找
- 剑指 Offer(C++版本)系列:剑指 Offer 05 替换空格
- 剑指 Offer(C++版本)系列:剑指 Offer 06 从尾到头打印链表
- 剑指 Offer(C++版本)系列:剑指 Offer 07 重建二叉树
—————————————————————————————————————
本文由 leetcode、牛客、公众哈哦、知乎共同支持!
https://leetcode-cn.com/u/tefuirnever/
https://blog.nowcoder.net/wsguanxl