栈三
2024年1月29日大约 1 分钟约 360 字
C++描述队列的抽象数据类型
const int maxsize=50;
enum bool{false,true};
template<class T>
class Queue{
public:
Queue(){};
~Queue(){};
virtual bool EnQueue(const T& x)=0;
virtual bool DeQueue(T& x)=0;
virtual bool getFront(T& x)=0;
virtual bool IsEmpty()const=0;
virtual bool IsFull()const=0;
virtual int getSize()const=0;
<!-- more -->
};基于数组实现的循环队列。
和栈有类似的地方。循环队列的判满方式是判断rear+1%maxsize=front是否满足条件。实现一个算法或者数据结构的过程是先给出类定义然后逐步的实现每个对应的方法。
循环队列的类定义及其实现
#include<iostream>
#include<assert.h>
#include "Queue.h"
template <class T>
class SeqQueue:public Queue<T>{
public:
SeqQueue(int sz=0);
~SeqQueue(){delete [] elements;}
bool EnQueue(const T& x);
bool int DeQueue(T& x);
bool getFront(T& x);
bool IsEmpty()const{return (front=rear)?true:false;}
void makeEmpty(){front=rear=0;}
bool IsFull()const{return ((rear+1)%maxsize==front)?true:false;}
int getSize()const{return (rear-front+maxsize)%maxsize;}
friend ostream & operator<<(ostream& os,SeqQueue<T>& Q);
protected:
int rear,front;
T* elements;
int maxsize;
};
template<class T>
SeqQueue<T>::SeqQueue(int sz):front(0),rear(0),maxsize(sz){
elements=new T [maxsize];
assert(elements);
};
template<class T>
bool SeqQueue<T>::EnQueue(const T&x){
if(!IsFull())return false;
elements[rear]=x;
rear=(rear+1)%maxSize;
return true;
};
template<class T>
bool SeqQueue<T>::DeQueue(T& x){
if(!IsEmpty())return false;
x=elements[front];
front=(front+1)%maxsize;
return true;
};
template<class T>
bool SeqQueue<T>:getFront(T& x)const{
if(!IsEmpty())return false;
x=elements[front];
return true;
};
template<class T>
ostream& operator<<(ostream& os,SeqQueue<T>& Q){
};