• / 3
  • 下载费用:10 金币  

面试题整理-两个栈实现队列.doc

关 键 词:
面试题整理-两个栈实现队列.doc
资源描述:
面试题整理-两个栈实现队列题目用两个栈实现队列。解法准备两个栈。一个是 input, 一个是 output。1、入栈:直接用 input.push()2、出栈:如果 output 非空。则利用 output 出栈。如果 output 为空。则把 input 中的元素全部 pop 至 output 栈中。再利用 output 出栈。说得简单一点就是从 input 栈进去,从 ouput 栈出去。明白为什么叫 input,output 没。实际上就是利用 output 栈把出去的顺序颠倒一下。略微可以优化的,就是在 pop 的时候,如果要把 input 全部倒到 output 中,可以把最后一个元素,留在 input 中。最后从 input 那里 pop。代码 stas.h[cpp] view plaincopy #ifndef _STACK_AS_QUEUE_H  #define _STACK_AS_QUEUE_H   #ifndef _NAME_SPACE_BEGIN_  #define _NAME_SPACE_BEGIN_ namespace stas {  #define _NAME_SPACE_END_ }  #endif  #include  #include   _NAME_SPACE_BEGIN_    template  class queue {  private:  std::stack input;  std::stack output;  private:  void _pop_input_into_output(const int leave = 0);  public:  queue() {}  ~queue(){}  const bool empty() const;  void push(const T  void pop();  T  };   template  void queue::_pop_input_into_output(const int leave) {  while (input.size() leave) {  output.push(input.top());  input.pop();  }  }   template  const bool queue::empty() const {  return input.empty()  }   template  void queue::push(const T  }   template  void queue::pop() {  if (!output.empty()) output.pop();  else {  this-_pop_input_into_output(1);  output.pop();  }  }   template  T  else {  this-_pop_input_into_output();  return output.top();  }  }    _NAME_SPACE_END_  #endif /*end of _STACK_AS_QUEUE_H */ 再写个测试的主程序 main.cpp输入1 x 表示把 x 入队列输出0表示把队首元素出队。[cpp] view plaincopy #include  #include  #include  #include “stas.h“  using namespace std;  using namespace stas;   int main(int argc, char *argv[]) {  stas::queue q;  while (1) {  int a, b;  cin a;   if (a%2) {  cin b;  q.push(b);  } else {  cout q.top() endl;  q.pop();  }  }  return 0;  }
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:面试题整理-两个栈实现队列.doc
链接地址:https://www.weizhuannet.com/p-9503546.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开