用两个栈实现队列

用两个栈实现队列

用两个栈实现一个队列，队列声明如下，实现它的两个函数appendTail和deleteHead,分别完成在队尾插入结点和在队列头部删除结点的功能

template <typename T>
class CQueue
{
public:
 CQueue();
 ~CQueue();
 
 void appendTail(const T& nods);
 T deleteHead();

private:
 stack<T> stack1;
 stack<T> stack2;
};

#include <iostream>
#include <stack>
#include <exception>
using namespace std;

template <typename T>
class CQueue
{
public:
 CQueue(){};
 ~CQueue(){};
 
 void appendTail(const T& nods);
 T deleteHead();

private:
 stack<T> stack1;
 stack<T> stack2;
};

template <typename T>
void CQueue<T>::appendTail(const T& nods)
{
 stack1.push(nods);
}

template <typename T>
T CQueue<T>::deleteHead()
{
 if (stack2.size() == 0)
 {
  if (stack1.size() > 0)
  {
   while (stack1.size() > 0)
   {
    T& data = stack1.top();
    stack1.pop();
    stack2.push(data); 
   }
   T& ret = stack2.top();
   stack2.pop();
   return ret;
  }
  else
   throw new exception();
 }
 else
 {
  T ret = stack2.top();
  stack2.pop();
  return ret; 
 }
}

int main()
{
 CQueue<int> myDeque;
 myDeque.appendTail(1);
 myDeque.appendTail(2);
 myDeque.appendTail(3);
 try{
  cout << myDeque.deleteHead() << endl;
  cout << myDeque.deleteHead() << endl;
 } catch(exception ex) {
  cout << "has exception" << endl;
 }
 return 0;
}

本文永久更新链接地址：