方法一:
创新互联,专注为中小企业提供官网建设、营销型网站制作、自适应网站建设、展示型网站设计制作、网站设计等服务,帮助中小企业通过网站体现价值、有效益。帮助企业快速建站、解决网站建设与网站营销推广问题。入队时,将元素压入s1。
出队时,将s1的元素逐个“倒入”(弹出并压入)s2,将s2的顶元素弹出作为出队元素,之后再将s2剩下的元素逐个“倒回”s1。
方法二:
入队时,先判断s1是否为空,如不为空,说明所有元素都在s1,此时将入队元素直接压入s1;如为空,要将s2的元素逐个“倒回”s1,再压入入队元素。
出队时,先判断s2是否为空,如不为空,直接弹出s2的顶元素并出队;如为空,将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
最优解:
入队时,将元素压入s1。
出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
注意:考虑没有元素可供出队时的处理(2个栈都为空的时候,出队操作一定会引起异常)
代码实现
//test1.h #include#include using namespace std; template class queueWithTwoStack { public: queueWithTwoStack(); ~queueWithTwoStack(); void addTail(const T& data); T deleteHead(); private: stack s1; stack s2; }; //test1.cpp #include "test1.h" using namespace std; template queueWithTwoStack ::queueWithTwoStack() {} template queueWithTwoStack ::~queueWithTwoStack() {} //加只加在S1中 template void queueWithTwoStack ::addTail(const T& data) { s1.push(data); } //删只删S2中的 template T queueWithTwoStack ::deleteHead() { if((s2.empty())&&(s1.empty())) { printf("is empty!\n"); return -1; } //s2为空,把S1全倒在S2中后删 if(s2.empty()) { while(!s1.empty()) { T top=s1.top(); s1.pop(); s2.push(top); } } //s2不为空直接删 T head=s2.top(); s2.pop(); return head; } void test1() { queueWithTwoStack qw; qw.addTail(1); qw.addTail(2); qw.addTail(3); cout< qw; qw.addTail(1); qw.addTail(2); qw.addTail(3); cout< 参考:《剑指offer》面试题7
http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
当前标题:利用两个栈实现队列-创新互联
URL地址:http://www.cdkjz.cn/article/dghhdd.html