标题

[C++笔试题]C++用两个栈实现一个队列的功能

责任编辑:admin
日期:2012-12-03

题目:用两个栈实现一个队列的功能,用C++实现。

思路:

假设两个栈A和B,且都为空。

可以认为栈A提供入队列的功能,栈B提供出队列的功能。

入队列:入栈A。

出队列:

  • 如果栈B不为空,直接弹出栈B的数据。
  • 如果栈B为空,则依次弹出栈A的数据,放入栈B中,再弹出栈B的数据。
  1. #include <iostream> 
  2. using namespace std; 
  3. #include <stack> 
  4. /* 
  5. * 问题:用两个栈实现一个队列的功能,用C++实现它 
  6. */ 
  7. template<class T> 
  8. class MyQueue{ 
  9. public
  10.     /*入队列,方法是直接放入第一个栈就可以了*/ 
  11.     void push(T &t){ 
  12.         sin.push(t); 
  13.     } 
  14.     /*出栈,如果第二个栈有数据,直接弹出;如果没有,把栈1的数据全压倒栈2再弹出*/ 
  15.     void pop(){ 
  16.         //如果出栈没数据了,就把入栈所有的数据挨个弹出,压入出栈 
  17.         if(sout.size()==0){ 
  18.             sin2sout(); 
  19.         } 
  20.          
  21.         if(sout.size()>0){ 
  22.             sout.pop(); 
  23.         } 
  24.     } 
  25.  
  26.     T front(){ 
  27.         //如果出栈没数据了,就把入栈所有的数据挨个弹出,压入出栈 
  28.         if(sout.size()==0){ 
  29.             sin2sout(); 
  30.         } 
  31.          
  32.         if(sout.size()>0){ 
  33.             return sout.top(); 
  34.         } else { 
  35.             return NULL; 
  36.         } 
  37.     } 
  38.  
  39.     /*获取长度*/ 
  40.     int size(){ 
  41.          
  42.         return sin.size()+sout.size(); 
  43.     } 
  44. private
  45.     /*将入栈的数据,全放到出栈里面*/ 
  46.     void sin2sout(){ 
  47.         while(sin.size()>0){ 
  48.             sout.push(sin.top()); 
  49.             sin.pop(); 
  50.         } 
  51.     } 
  52.     //用作进入数据的栈 
  53.     stack<T> sin; 
  54.     //用作取出数据的栈 
  55.     stack<T> sout; 
  56. }; 
  57.  
  58. void main(){ 
  59.     MyQueue<int> mqueue; 
  60.     for(int i=0; i<10; ++i){ 
  61.         mqueue.push(i); 
  62.     } 
  63.  
  64.     while(mqueue.size()!=0){ 
  65.         cout<<mqueue.front()<<" "
  66.         mqueue.pop(); 
  67.     } 
  68.     cout<<endl; 
  69.     system("pause"); 

阅读:

相关新闻:
评论