面试题7:用两个栈实现队列和用两个队列实现一个栈

简介:
复制代码
题目:用两个栈实现一个队列。队列的生命如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。

template <typename T>class CQueue
{
public:
  CQueue(void);
  ~CQueue(void);
  void appendtail(const T& node);
  T deleteHead();
private:
  stack<T> stack1;
  stack<T> stack2;
};
复制代码

解题思路:

插入操作在stack1中进行,删除操作在stack2中进行,如果stack2为空,则将stack1中的所有元素转移到stack2中。

代码实例:

View Code

使用两个队列实现一个栈

参考文献:

http://hi.baidu.com/ozwarld/blog/item/ec9b52d4d48ce1dc50da4b0f.html

解法:

  1. 有两个队列q1和q2,先往q1内插入a,b,c,这做的都是栈的push操作。
  2. 现在要做pop操作,即要得到c,这时可以将q1中的a,b两个元素全部dequeue并存入q2中,这时q2中元素为a,b,对q1再做一次dequeue操作即可得到c。
  3. 如果继续做push操作,比如插入d,f,则把d,f插入到q2中,
  4. 此时若要做pop操作,则做步骤2
  5. 以此类推,就实现了用两个队列来实现一个栈的目的。

注意在此过程中,新push进来的元素总是插入到非空队列中,空队列则用来保存pop操作之后的那些元素,那么此时空队列不为空了,原来的非空队列变为空了,总是这样循环。

对于push和pop操作,其时间为O(n).

代码实例

View Code

 

 

 本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2012/05/03/2480651.html,如需转载请自行联系原作者

 

目录
相关文章
|
4月前
|
存储 Java 编译器
【面试知识】Java内存分配之常量池、堆、栈
【面试知识】Java内存分配之常量池、堆、栈
|
5月前
|
缓存 网络协议 Linux
手把手实现tcp/ip用户态协议栈,帮你实践网络知识(网络必备,面试项目)
手把手实现tcp/ip用户态协议栈,帮你实践网络知识(网络必备,面试项目)
|
6月前
【栈和队列面试题】用栈实现队列(动图解析更清晰)
【栈和队列面试题】用栈实现队列(动图解析更清晰)
|
4月前
|
算法 容器
【算法训练营】队列合集(2) 2073. 买票需要的时间 || 面试题 03.04. 化栈为队 ||
【算法训练营】队列合集(2) 2073. 买票需要的时间 || 面试题 03.04. 化栈为队 ||
59 0
|
2月前
|
存储 算法 调度
【数据结构入门精讲 | 第五篇】栈知识点及考研408、企业面试练习
【数据结构入门精讲 | 第五篇】栈知识点及考研408、企业面试练习
37 0
|
2月前
|
存储 前端开发 搜索推荐
【数据结构入门精讲 | 第六篇】队列知识点及考研408、企业面试练习
【数据结构入门精讲 | 第六篇】队列知识点及考研408、企业面试练习
55 0
|
3月前
|
设计模式 消息中间件 Java
面试官:什么是JIT、逃逸分析、锁消除、栈上分配和标量替换?
面试官:什么是JIT、逃逸分析、锁消除、栈上分配和标量替换?
512 1
|
3月前
|
存储 程序员 C++
面试题:C++堆和栈的区别?
面试题:C++堆和栈的区别?
24 0
|
3月前
面试题 03.05:栈排序
面试题 03.05:栈排序
22 0
|
3月前
面试题 03.04:化栈为队
面试题 03.04:化栈为队
24 5