C++——设计队列类和循环队列类

设计队列类和循环队列类

要求：

能够设计队列类和循环队列类，实现存储和取数功能。

Append：加入队列，将一个元素加入到队列的后面

Get:读取队列，从队列前面读取并删除一个元素

IsEmpty：判断队列是否为空

IsFull：判断队列是否已满

Traverse：遍历，从头至尾访问队列的每个单元

Clear：清除，使队列为空

非循环静态分配空间队列类基本操作如下：

#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXQSIZE 10 
typedef char QElemType; 
typedef int Status;
class   Queue {
        private:
                int          rear;                            // 头指针,若队列不空,指向队列头元素
                char                 front[MAXQSIZE];    // 尾指针,若队列不空,指向队列尾元素的下一个位置
        public:
                Queue();
                Status IsEmpty(); 
                Status IsFull();
                Status Append(QElemType e);
                Status Get(QElemType &e);
                Status Traverse();
                Status Clear();
};
Queue::Queue()
{
        cout<<"构造函数使用ing"<<endl;
        rear=0;
}

Status Queue::IsEmpty()
{
        if(rear==0)
                return true;
        else
                return false;
}

Status Queue::IsFull()
{
        if(rear==MAXQSIZE)
                return true;
        else
                return false;
}

Status Queue::Append(QElemType e)
{
        // 插入元素e为Q的新的队尾元素
        if(IsFull()) // 队列满
                return ERROR;
        front[rear++]=e;
        return OK;
}

Status Queue::Get(QElemType &e)
{
        // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
        if(rear==0) // 队列空
                return ERROR;
        e=front[0];
        for(int i=0;i<rear-1;i++)
        {
                front[i]=front[i+1];
        }
        rear--;
        return OK;
}

Status Queue::Traverse()
{
        if(IsEmpty())  return 0;
        for(int i=0;i<rear;i++)
        {
                cout<<front[i]<<' ';
        }
}

Status Queue::Clear()
{
        rear=0;
}


int main()
{
        Queue Q;
        char q1[3]={'a','b','c'};
        char q2[3]={'d','e','f'};
        int i;
        char e;
        printf("依次进队列元素a,b,c\n");
        for(i=0;i<3;i++)
                Q.Append(q1[i]);
         
        if(!Q.IsEmpty())
                cout<<"此时栈非空\n"; 
        
        Q.Get(e);
        cout<<"出队一个元素："<<e; 
        
        cout<<endl<<"依次进队列元素d,e,f\n";
        for(i=0;i<3;i++)
                Q.Append(q2[i]);
        
        cout<<"出队序列为：";
        Q.Traverse();
        /*
        while(!Q.IsEmpty())
        {
                Q.Get(e);
                cout<<e<<" ";
        }*/
}

循环动态分配存储空间队列类操作如下：

#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXQSIZE 10 
typedef char QElemType;
typedef int Status;

class   Queue {
        private:
                QElemType   *base;                           // 初始化的动态分配存储空间
                //QElemType   base[MAXQSIZE];   //也可以直接静态分配存储空间
                int          front;                           // 头指针,若队列不空,指向队列头元素
                int          rear;                            // 尾指针,若队列不空,指向队列尾元素的下一个位置
        public:
                Queue();
                ~Queue();
                Status IsEmpty(); 
                Status IsFull(); 
                Status Append(QElemType e);
                Status Get(QElemType &e);
                Status Traverse();
                Status Clear(); 
};

Queue::Queue() {
        // 构造一个空队列Q
        cout<<"构造函数使用ing"<<endl;
        base=new QElemType[MAXQSIZE];
        if(!base) // 存储分配失败
                exit(OVERFLOW);
        front=rear=0;
}

Queue::~Queue()
{
        // 销毁队列Q,Q不再存在
        cout<<endl<<"析构函数使用ing"<<endl;
        if(base)
                delete base;  //delete []base
        base=NULL;   
        front=rear=0;
}

Status Queue::IsEmpty()
{
        if(front==rear)
                return true;
        else
                return false;
}


Status Queue::IsFull()
{
        if((rear+1)%MAXQSIZE==front)
                return true;
        else
                return false;
}

Status Queue::Append(QElemType e)
{
        // 插入元素e为Q的新的队尾元素
        if((rear+1)%MAXQSIZE==front) // 队列满
                return ERROR;
        base[rear]=e;
        rear=(rear+1)%MAXQSIZE;
        return OK;
}

Status Queue::Get(QElemType &e)
{
        // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
        if(front==rear) // 队列空
                return ERROR;
        e=base[front];
        front=(front+1)%MAXQSIZE;
        return OK;
}

Status Queue::Traverse()
{
        for(int i=front;i<rear;i++)
        {
                cout<<base[i]<<' ';
        }
}
Queue::Clear()
{
        rear=front=0;
}
int main()
{
        Queue Q;
        char q1[3]={'a','b','c'};
        char q2[3]={'d','e','f'};
        int i;
        char e;
        printf("依次进队列元素a,b,c\n");
        for(i=0;i<3;i++)
                Q.Append(q1[i]);
         
        if(!Q.IsEmpty())
                cout<<"此时栈非空\n"; 
        
        Q.Get(e);
        cout<<"出队一个元素："<<e; 
        
        cout<<endl<<"依次进队列元素d,e,f\n";
        for(i=0;i<3;i++)
                Q.Append(q2[i]);
        
        cout<<"出队序列为：";
        Q.Traverse();
}