数据结构——循环队列

  1 #include<iostream>
  2 #include<stdlib.h>
  3 using namespace std;
  4 
  5 typedef int QElemType;
  6 typedef int Status;
  7 #define MAXSIZE 10
  8 #define OVERFLOW -2
  9 #define OK 1
 10 #define ERROR 0
 11 
 12 //循环队列的存储结构
 13 typedef struct
 14 {
 15     QElemType *base;    //存储空间的基地址
 16     int front;          //头指针
 17     int rear;           //尾指针
 18 }SqQueue;
 19 
 20 //循环队列的初始化
 21 Status InitQueue(SqQueue &Q)
 22 {
 23     Q.base = new QElemType[MAXSIZE];  //为队列分配一个最大容量为MAXSIZE的数组空间
 24 
 25     if (!Q.base)                     //分配失败
 26         exit(OVERFLOW);
 27 
 28     Q.front = Q.rear = 0;               //头指针和尾指针置为0，对列为空
 29 
 30     return OK;
 31 }
 32 
 33 //队列长度
 34 int QueueLength(SqQueue Q)
 35 {
 36     return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;    //循环队列，取余
 37 }
 38 
 39 //入队
 40 //插入元素e，作为队列Q的新的队尾元素
 41 Status EnQueue(SqQueue &Q, QElemType e)
 42 {
 43     if ((Q.rear + 1) % MAXSIZE == Q.front)     //尾指针在循环意义上加1后等于头指针，表明对满
 44         return ERROR;
 45 
 46     Q.base[Q.rear] = e;                   //新元素插入队尾
 47 
 48     Q.rear = (Q.rear + 1) % MAXSIZE;          //队尾指针加1
 49 
 50     return OK;
 51 }
 52 
 53 //出队
 54 //删除Q的队头元素，用e返回其值
 55 Status DeQueue(SqQueue &Q, QElemType &e)
 56 {
 57     if (Q.front == Q.rear)     //队空
 58         return ERROR;
 59 
 60     e = Q.base[Q.front];      //保存队头元素
 61 
 62     Q.front = (Q.front + 1) % MAXSIZE;    //出队，队头指针加1
 63 
 64     return OK;
 65 }
 66 
 67 //取队头元素
 68 //返回队头元素，不修改头指针
 69 QElemType GetHead(SqQueue Q)
 70 {
 71     if (Q.front != Q.rear)     //队列非空
 72         return Q.base[Q.front];
 73 }
 74 
 75 int main()
 76 {
 77     int i, e;
 78     int len;
 79     SqQueue Q;
 80 
 81     InitQueue(Q);   //初始化一个空队列
 82 
 83     for (i = 0; i < MAXSIZE; i++)
 84         EnQueue(Q, i);       //入队
 85 
 86     len = QueueLength(Q);
 87 
 88     cout << "当前队列情况为：";
 89 
 90     for (i = Q.front; i < Q.rear; i++)
 91     {
 92         cout << Q.base[i] << " ";
 93     }
 94     cout << endl;
 95 
 96     cout << "当前队列里的元素有" << len << "个" << endl;
 97 
 98     cout << "当前的队头元素是：" << GetHead(Q) << endl;
 99 
100     cout << "出队元素有：";
101     for (i = 0; i < 3; i++)
102     {
103         DeQueue(Q, e);   //出队
104         cout << e << " ";
105     }
106     cout << endl;
107 
108     len = QueueLength(Q);
109 
110     cout << "当前队列情况为：";
111 
112     for (i = Q.front; i < Q.rear; i++)
113     {
114         cout << Q.base[i] << " ";
115     }
116     cout << endl;
117 
118     cout << "当前队列里的元素有" << len << "个" << endl;
119 
120     cout << "当前的队头元素是：" << GetHead(Q) << endl;
121 
122     system("pause");
123         return 0;
124 }