队列的存储结构的实现(C/C++实现)

 1 #include "iostream.h"
 2 #include "stdlib.h"
 3 #define max 20
 4 typedef char elemtype;
 5 #include "queue.h"
 6 void main()
 7 {
 8     elemtype e;
 9     queue q;
10     cout<<"(1)初始化队列q"<<endl;
11     initqueue(q);
12     cout<<"(2)队列为"<<(queueempty(q)?"空":"非空")<<endl;
13     cout<<"(3)依次输入字母序列,以'#'结束:"<<endl;
14     cin>>e;
15     while(e!='#')
16     {
17         enqueue(q,e);
18         cin>>e;
19     }
20     cout<<"(4)队列为"<<(queueempty(q)?"空":"非空")<<endl;
21     e=dequeue(q);
22     cout<<"(5a)出队一个元素dequeue()为:"<<e<<endl;
23     if(dequeue1(q,e))
24         cout<<"(5b)出队一个元素dequeue1()为:"<<e<<endl;
25     cout<<"(6)队列q的元素个数:"<<queuelength(q)<<endl;
26     cout<<"(7)清空队列"<<endl;
27     clearqueue(q);
28     cout<<"(8)队列q的元素个数:"<<queuelength(q)<<endl;
29     cout<<"(9)字符abc依次入队列"<<endl;
30     enqueue(q,'a');
31     enqueue(q,'b');
32     enqueue(q,'c');
33     e=gethead(q);
34     cout<<"(10a)队头元素gethead()为:"<<e<<endl;
35     if (gethead1(q,e))
36         cout<<"(10b)队头元素gethead1()为:"<<e<<endl;
37     cout<<"(11)队列的元素个数:"<<queuelength(q)<<endl;
38     cout<<"(12)所有元素出队列:";
39     while(!queueempty(q))
40         cout<<dequeue(q)<<" ";
41     cout<<endl;
42     cout<<"(13)队列q的元素个数:"<<queuelength(q)<<endl;
43     cout<<"(14)释放队列"<<endl;
44     destoryqueue(q);
45 }

  1 typedef struct
  2 {
  3     elemtype *base;//动态分配存储空间
  4     int front;//头指针,若队列不空指向队列队头元素
  5     int rear;//尾指针,若队列不空指向队列队尾元素的下一个位置
  6 }queue;
  7 void initqueue(queue &q)
  8 {
  9     //初始化队列
 10     q.base=new elemtype[max];//分配存储空间
 11     if(!q.base)
 12     {
 13         cout<<"队列分配失败\n";
 14         exit(-2);
 15     }
 16     else
 17         q.front=q.rear=0;//初始状态,front和rear都为0
 18 }
 19 void clearqueue(queue &q)
 20 {
 21     //清空队列,但不销毁
 22     q.front=0;//清空函数,恢复到初始状态
 23     q.rear=0;
 24 }
 25 int queueempty(queue q)
 26 {
 27     //判断队列是否为空
 28     if(q.front==q.rear)//空队列,返回1,否则返回0
 29         return 1;
 30     else
 31         return 0;
 32 }
 33 int queuelength(queue q)
 34 {
 35     //求队列中元素个数
 36     return (q.rear-q.front+max)%max;//计算队列当前存储的元素数目
 37 }
 38 void enqueue(queue &q,elemtype e)
 39 {
 40     //入队列操作
 41     if((q.rear+1)%max==q.front)//队满的操作
 42     {
 43         cout<<"队满,无法插入新元素!"<<endl;
 44         exit(-2);
 45     }
 46     else
 47     {
 48         q.base[q.rear]=e;//元素e存在当前rear所指位置
 49         q.rear=(q.rear+1)%max;//rear指针后移
 50     }
 51 }
 52 elemtype dequeue(queue &q)
 53 {
 54     //出队列操作
 55     if(q.front==q.rear)//空队列不能出队
 56     {
 57         //队空
 58         cout<<"空队列,无法删除头元素!"<<endl;
 59         exit(-2);
 60     }
 61     else
 62     {
 63         elemtype e=q.base[q.front];//当前的队列头元素作为返回值
 64         q.front=(q.front+1)%max;//front指针后移
 65         return e;
 66     }
 67 }
 68 int dequeue1(queue &q,elemtype &e)
 69 {
 70     //出队列操作
 71     if(q.front==q.rear)//空队列不能出队
 72     {
 73         //队空
 74         cout<<"空队列,无法删除头元素!"<<endl;
 75         return 0;
 76     }
 77     else
 78     {
 79         e=q.base[q.front];//当前的队列头元素作为返回值
 80         q.front=(q.front+1)%max;//front指针后移
 81         return 1;
 82     }
 83 }
 84 elemtype gethead(queue q)
 85 {
 86     //读队头元素的值,但不删除
 87     if(q.front==q.rear)//空队列,无法读
 88     {
 89         //队空
 90         cout<<"空队列,无头元素"<<endl;
 91         exit(-2);
 92     }
 93     else 
 94         return q.base[q.front];//队列头元素的数组下标即front本身
 95 }
 96 void destoryqueue(queue &q)
 97 {
 98     //销毁队列
 99     delete q.base;//释放连续的存储空间
100     q.base=NULL;//基地址赋值为空
101     q.front=0;//头指针赋值为0
102     q.rear=0;//尾指针赋值为0
103 }
104 int gethead1(queue q,elemtype &e)
105 {
106     //读队头元素的值,但不删除
107     if(q.front==q.rear)//空队列,无法读
108     {
109         //队空
110         cout<<"空队列,无头元素"<<endl;
111         return 0;
112     }
113     else 
114         e=q.base[q.front];//队列头元素的数组下标即front本身
115     return 1;
116 }