C++下环形队列的简单实现
#include <iostream> #include <string> using namespace std; class student { public: student(string name="o",int age=0) { sName=name; iAge=age; } void print() { cout<<"name:"<<sName<<endl; cout<<"age:"<<iAge<<endl; cout<<endl; } private: string sName; int iAge; }; class MyQueue { public: MyQueue(int c); ~MyQueue(); void ClearQueue(); int queuelen(); bool full(); bool empty(); void enterqueue(student element); void deletequeue(student &element); void traverse(); private: int iCapacity; student *iQueue;//this pointer stands for the whole queue. int iLen; int head; int tail; }; MyQueue::MyQueue(int c) { iCapacity=c; iQueue=new student[iCapacity]; iLen=0; head=0; tail=0; cout<<"this queue's capacity is "<<c<<endl; } MyQueue::~MyQueue() { delete iQueue; iQueue=NULL; } void MyQueue::ClearQueue() { iLen=0; head=0; tail=0; } int MyQueue::queuelen() { return iLen; } bool MyQueue::full() { return iLen == iCapacity ? true: false; } bool MyQueue::empty() { return iLen == 0 ? true: false; } void MyQueue::enterqueue(student element)//入队,从tail进 { if (full()==false) { iQueue[tail%iCapacity]=element; //iQueue[tail]=element; tail++; //tail=tail%iCapacity; iLen++; } } void MyQueue::deletequeue(student &element)//出队,从head出,删除元素就是删除地址,该函数就是指删除首元素。 { if(empty()==false) { element=iQueue[head%iCapacity]; //element=iQueue[head]; head++; //head=head%iCapacity; iLen--; } } void MyQueue::traverse()//遍历 { //cout<<iQueue[0]<<" "<<iQueue[1]<<" "<<iQueue[2]<<" "<<iQueue[3]<<endl;检验的确是循环使用的。 for(int i=head;i<head+iLen;i++) { iQueue[i%iCapacity].print();//iLen or iCapacity??? cout<<endl; } } int main() { /* MyQueue *p=new MyQueue(4); p->enterqueue(10); p->enterqueue(12); p->enterqueue(14); p->enterqueue(16); int e=0;//任意赋初值 p->deletequeue(e); cout<<e<<endl;//返回删除的元素的值 cout<<endl; p->traverse(); p->enterqueue(20); p->traverse();*/ MyQueue *p=new MyQueue(4); student s1("a",1); student s2("b",2); student s3("c",3); student s4("d",4); p->enterqueue(s1); p->enterqueue(s2); p->enterqueue(s3); p->enterqueue(s4); p->traverse(); delete []p; p=NULL; return 0; }
队列,FIFO;分为普通队列和环形队列。
它只允许在队头进行删除操作,而在队尾进行插入操作。
普通队列效率低,速度慢,且容易造成内存空间浪费。
相较于普通队列,环形队列(循环队列)则很好的解决了这些问题。