用两个栈实现一个队列算法

男娘i 2022-06-09 04:14 201阅读 0赞

栈：后进先出，队列：先进先出。

用两个栈实现一个队列，主要实现队列中的两个函数，appendTail,尾部追加，deleteHead，在头部删除节点，

用了一个模板类，队列的元素可以是任意类型，int，char都可以，其中类模板中构造函数，析构函数，appendTail，deleteHead的声明和实现都要写在.h中，把实现写在.cpp中，会提示这些方法没定义。模板定义挺特殊的。

AnalogQueue.h

\#pragma once  
\#include <stack>  
\#include <exception>  
\#include <iostream>  
  
using namespace std;  
  
template <typename T> class AnalogQueue\{  
public:  
AnalogQueue();  
~AnalogQueue();  
void appendTail(const T& node);  
T deleteHead();  
private:  
stack<T> stackOne;  
stack<T> stackTwo;  
  
\};  
  
template <typename T> AnalogQueue<T>::AnalogQueue()\{  
  
\}  
  
template <typename T> AnalogQueue<T>::~AnalogQueue()\{  
  
\}  
  
template <typename T> void AnalogQueue<T>::appendTail(const T& element)\{  
stackOne.push(element);  
\}

//删除时，先把stackOne中元素，一次压入stackTwo，然后弹出stackTwo的头元素。  
template <typename T> T AnalogQueue<T>::deleteHead()\{  
if(stackTwo.size()<=0)\{  
while(stackOne.size()>0)\{  
T& data = stackOne.top();  
stackOne.pop();  
stackTwo.push(data);  
\}  
\}  
  
if(stackTwo.size() == 0)\{  
cout << "queue is null!"<<endl;  
throw new exception();  
\}  
  
T head = stackTwo.top();  
stackTwo.pop();  
  
cout<<"head node:" << head << endl;  
return head;  
\}

AnalogQueue.cpp

\#include "AnalogQueue.h"  
\#include <exception>  
\#include <iostream>  
  
using namespace std;  
  
int main()\{  
AnalogQueue<char> aQueue;  
aQueue.appendTail('a');  
aQueue.appendTail('b');  
aQueue.appendTail('c');  
aQueue.appendTail('d');  
  
aQueue.deleteHead();  
aQueue.deleteHead();  
aQueue.deleteHead();  
aQueue.appendTail('e');  
aQueue.appendTail('f');  
aQueue.deleteHead();  
aQueue.deleteHead();  
aQueue.deleteHead();  
aQueue.deleteHead();  
  
return 0;  
\}

测试结果：

\-PC:~/algorithm$ g++ AnalogQueue.cpp -o AnalogQueue  
\-PC:~/algorithm$ ./AnalogQueue  
head node:a  
head node:b  
head node:c  
head node:d  
head node:e  
head node:f  
queue is null!  
terminate called after throwing an instance of 'std::exception\*'  
Aborted (core dumped)