首页 > 代码库 > [转载]队列的链式存储
[转载]队列的链式存储
申明：转自 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 }
1.队列定义：除了定义队列中节点的数据结构，还专门定义了队首和队尾，方便对队列操作，这样一来，队列的操作就只需要对pointer结构体中的对手指真和队尾指针进行。
2.判断是否为空
当队首指针和队尾指针只想同一块地址时，队列为空，队列为空就是说队列中没有数据元素。注意队首front只是队列的头结点，并不代表队列的实际队首，在队列不为空时，队列的实际队首应该是头结点的下一个节点。
3.插入数据元素
插入在队尾进行，插入后，新插入的节点就成为了队尾。
4.删除数据元素
删除在队首进行，需要注意的是，当实际的队首也是队尾时，删除队列中的一个数据后队列就成为了空队列（rear=front）。最后不要忘了将删除的数据的内存空间释放掉。
5.注意点
最后释放内存时，一定要先释放掉pointer中的队首指针和队尾指针指向的内存空间，再释放掉pointer结构体指向的内存空间。
[转载]队列的链式存储
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。