【数据结构】队列

1.【单链队列】

利用链表实现队列，在尾部插入头部删除。分别利用头尾指针指向单链表的头部和尾部，初始化时头尾指针均指向同一处，在进行插入时尾部指针指向新插入的节点，在进行删除时头部指针指向其前一个节点。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct Queue {
 5     int data;
 6     Queue * next ;
 7 }Queue , *queue;
 8 
 9 typedef struct {
10     queue front; // 队头指针 
11     queue rear; //  队尾指针 
12 }LinkQueue;
13 //构建一个空队列 
14 void InitQueue(LinkQueue &Q) {
15     Q.front = Q.rear = (queue)malloc(sizeof(Queue));
16     if(!Q.front)
17     exit(0);
18     Q.front->next = NULL;
19 }
20 
21 //销毁队列 
22 void DestroyQueue(LinkQueue &Q) {
23     while(Q.front) {
24         Q.rear = Q.front->next;
25         free(Q.front);
26         Q.front = Q.rear;
27     }
28 }
29 
30 //在队尾添加元素 
31 void EnQueue(LinkQueue &Q , int n) {
32     Q.rear->next = (queue)malloc(sizeof(Queue)) ;
33     if(!Q.rear)
34     exit(0);
35     Q.rear->data = n ;
36     Q.rear = Q.rear->next ;
37     Q.rear->next = NULL ;
38 }
39 
40 //取出队头元素 
41 int DeQueue(LinkQueue &Q) {
42     if(Q.front == Q.rear)
43     return -1 ;
44     Queue *q = Q.front->next;
45     int n = Q.front->data;
46     Q.front = q;
47     free(q);
48     return n;    
49 }
50 
51  //输出所有元素 
52  void PrintfQueue(LinkQueue &Q) {
53      for( ; ; ) 
54      {
55          if(Q.front == Q.rear)
56          break;
57          printf("%d" , DeQueue(Q));
58      }
59  }
60  
61 int main() {
62     LinkQueue Q ;
63     InitQueue(Q);
64     for(int i = 0 ; i < 3 ; i++)
65     {
66         int n = 0 ;
67         scanf("%d" , &n);
68         EnQueue(Q,n);
69     }
70     printf("%d
" , DeQueue(Q));
71     PrintfQueue(Q);     
72 }

2.【循环队列】

充分利用存储空间，防止假溢出

【假溢出】当用线性表的顺序结构实现队列时，不断的添加元素时，队尾指针指向最后一个元素，无法继续添加，队头元素出队列后，队头存储空间不能利用。存储区未满，但队列发生溢出

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef struct {
 4     int *base ;
 5     int front ;
 6     int rear ;
 7 } SqQueue ;
 8 
 9 //构造空队列 
10 int InitQueue(SqQueue &Q) {
11     Q.base = (int *)malloc(6*sizeof(int));
12     if(!Q.base)
13     exit(0);
14     Q.front = Q.rear = 0;
15 }
16 
17 //在队尾添加元素 
18 int EnQueue(SqQueue &Q , int e) {
19     if((Q.rear+1)%6 == Q.front)
20     return -1 ;
21     Q.base[Q.rear] = e;
22     Q.rear = (Q.rear+1) % 6 ; //补码 
23     return 0 ;
24 } 
25 
26 //取出队头元素 
27 int DeQueue(SqQueue &Q ) {
28     if(Q.rear == Q.front)
29     return -1 ;
30     int n = Q.base[Q.front];
31     Q.front = (Q.front+1)%6;
32     return n ;
33 }
34 //判断循环链表的长度 
35 int QueueLength(SqQueue &Q) {
36     return ( Q.rear - Q.front + 6 ) / 6;
37 }
38 
39 int main() {
40     SqQueue Q ;
41     InitQueue(Q) ;
42     for(int i = 0 ; i <= 4 ; i++ )
43     EnQueue(Q , i);
44     while(Q.front != Q.rear)
45     printf("%d" , DeQueue(Q));
46 }