[转载]队列的链式存储

申明：转自 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 = 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:
");
 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:
");
 95     while (p)
 96     {
 97         printf("%d ", p->data);
 98         p = p->next;
 99     }
100     printf("
");
101     //删除队列
102     printf("delete queue:
");
103     while (QueuePop(qp, &element))
104     {
105         printf("%d ", element);
106     }
107     printf("
");
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结构体指向的内存空间。