队列的存储结构的实现(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 }