首页 > 代码库 > [转载]队列的链式存储

[转载]队列的链式存储

申明:转自    http://www.cnblogs.com/Romi/archive/2012/08/28/2660954.html

技术分享
  1 //队列的链式存储.C  2 #include<stdio.h>  3 #include<stdlib.h>  4 #include<malloc.h>  5   6 //定义队列  7 typedef struct node {  8     int data;  9     struct node *next; 10 }Queue; 11  12 //定义对手指针和队尾指针 13 typedef struct pointer { 14     Queue *front;//队首指针,队首指针不存放队列元素 15     Queue *rear;//队尾指针,指向队尾的结点 16 }Qpointer; 17  18 //队列初始化,队首和队尾指向同一个内存空间,指针域为NULL 19 void QueueInit(Qpointer *qp) 20 { 21     Queue *que; 22     que = (Queue*)malloc(sizeof(Queue)); 23     que->next = NULL; 24     qp->front = que; 25     qp->rear = que; 26 } 27  28 //判断队列是否为空:为空返回1,不为空返回0 29 int IsEmpty(Qpointer *qp) 30 { 31     //判断方法:对手指针和队尾指针是否相同 32     if (qp->front == qp->rear) 33     { 34         return 1; 35     } 36     return 0; 37 } 38  39 //插入数据元素:插入成功返回1,失败返回0 40 int QueuePush(Qpointer *qp, int element) 41 { 42     Queue *que; 43     que = (Queue*)malloc(sizeof(Queue)); 44     if (que == NULL) 45     { 46         return 0; 47     } 48     que->data =http://www.mamicode.com/ element; 49     que->next = NULL; 50     qp->rear->next = que;//将节点插入队列尾 51     qp->rear = que;//调整队尾指针(队尾指针,指向队尾的结点) 52     return 1; 53 } 54  55 //删除数据元素:删除成功返回1,失败返回0 56 int QueuePop(Qpointer *qp, int *element) 57 { 58     Queue *que; 59     if (IsEmpty(qp)) 60     { 61         return 0; 62     } 63     que = qp->front->next;//que指向队列头结点的下一个节点,即真正的队首 64     *element = que->data;//将要出队列的元素 65     qp->front->next = que->next; 66     //判断队列是否就只剩下一个元素 67     if (qp->rear == que) 68     { 69         qp->rear = qp->front; 70     } 71     free(que); 72     return 1; 73 } 74  75 int main() 76 { 77     Qpointer *qp; 78     int x; 79     int element; 80     //初始化队列 81     qp = (Qpointer*)malloc(sizeof(Qpointer)); 82     QueueInit(qp); 83     printf("input positive integers:\n"); 84     scanf("%d", &x); 85     while (x > 0) 86     { 87         QueuePush(qp, x); 88         scanf("%d", &x); 89     } 90     //输出队列:队首->队尾 91     Queue *p = qp->front->next; 92     if (p == NULL) 93         return 0; 94     printf("queue element:\n"); 95     while (p) 96     { 97         printf("%d ", p->data); 98         p = p->next; 99     }100     printf("\n");101     //删除队列102     printf("delete queue:\n");103     while (QueuePop(qp, &element))104     {105         printf("%d ", element);106     }107     printf("\n");108     //释放内存空间109     p = qp->front;110     free(p);111     free(qp);112 113     return 0;114 }
View Code

1.队列定义:除了定义队列中节点的数据结构,还专门定义了队首和队尾,方便对队列操作,这样一来,队列的操作就只需要对pointer结构体中的对手指真和队尾指针进行。

2.判断是否为空
当队首指针和队尾指针只想同一块地址时,队列为空,队列为空就是说队列中没有数据元素。注意队首front只是队列的头结点,并不代表队列的实际队首,在队列不为空时,队列的实际队首应该是头结点的下一个节点。

3.插入数据元素

插入在队尾进行,插入后,新插入的节点就成为了队尾。

4.删除数据元素

删除在队首进行,需要注意的是,当实际的队首也是队尾时,删除队列中的一个数据后队列就成为了空队列(rear=front)。最后不要忘了将删除的数据的内存空间释放掉。

5.注意点

最后释放内存时,一定要先释放掉pointer中的队首指针和队尾指针指向的内存空间,再释放掉pointer结构体指向的内存空间。

 

[转载]队列的链式存储