队列queue，是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。遵循FIFO，允许插入的一端是队尾，允许删除的一端是队头。
为了避免当队中只有一个元素时，队头和队尾重合使处理变得麻烦，引入了两个指针，front指向队头，rear指向队尾元素的下一位置。当front等于rear时，队列为空。假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组，并把队列中的所有元素存储在数组的前n个单元，数组下标为0的一端为队头。那么入队时，其实就是在队尾追加一个元素，不需要移动任何元素，时间复杂度为o(1).而出队时，则将队头元素移除，即将数组下标为0位置处的元素移除，那么这样就意味着队列中的所有元素都得向前移动，以保证队列的队头，这样一来，该操作的时间复杂度为O(n)。
循环队列：将队列的头尾相接的顺序存储结构。
补充下基础知识：取模 %
a % b 表示a除以b的余数
(a+b) % p，其结果是a+b算术和除以p的余数，即(a+b) = kp + r,则(a+b)%p = r；
例如：rear=1，front=2，SIZE=5 则（rear+1)%SIZE => (1+1)%5 = k*5 + r = 0*5 + 2;所以值为2，等于front，所以队列满。
队列顺序存储结构的定义。front指向队头，若队列不为空，rear指向队尾元素的下一位。
1 #define MAXSIZE 100 2 typedef int datatype; 3 typedef struct 4 { 5 datatype data[MAXSIZE]; 6 int front; 7 int rear; 8 }squeue;
获取队列长度：
1 int LengthQueue(squeue *sq) 2 { 3 return ((sq->rear - sq->front + MAXSIZE) % MAXSIZE); 4 }
入队操作：循环队列入队前先判断队列是否满了，判断条件是（sq->rear+1）% MAXSIZE 是否和sq->front相等，如果相等则表示队列满。入队后，同样要改变rear的位置，不能简单的rear+1，而是通过（sq->rear + 1）% MAXSIZE的值赋给新队列的sq->rear。
1 int EnterQueue(squeue *sq, datatype x) 2 { 3 if ((sq->rear + 1) % MAXSIZE == sq->front) 4 { 5 printf("queue full\n"); 6 return -1; 7 } 8 sq->data[sq->rear] = x; 9 sq->rear = (sq->rear + 1) % MAXSIZE; 10 return 0; 11 }
出队操作：循环队列的出队操作先判断队列是否为空。不为空则，将队头元素出队，front向后移动一位到最后则转到数组的头部，因此可以通过sq->front = （sq->front + 1）% MAXSIZE操作，处理该情况。
1 datatype DeleteQueue(squeue *sq) 2 { 3 if (sq->rear == sq->front) 4 { 5 printf("queue empty\n"); 6 return -1; 7 } 8 sq->front = (sq->front + 1) % MAXSIZE; 9 return sq->data[sq->front]; 10 }
因为队列的顺序存储存在溢出的可能，所以我们又考虑循环队列的链式存储。
循环队列的链式存储：为了操作方便，我们将队头指针指向头结点，而队尾指针指向终端结点。即front-->头结点-->对头-->。。。-->队尾 <--rear。空队列时，front和rear都指向头结点。
结点及链队列定义：结点中包含一个数据域data以及一个指向下一个结点的指针域。而在链队列结构体定义中包含两个指向结点的front和rear指针。
1 typedef int datatype; 2 typedef struct qnode 3 { 4 datatype data; 5 struct qnode *next; 6 }qnode, *qptr; 7 8 typedef struct 9 { 10 qptr front; 11 qptr rear; 12 }linkqueue;
链队列的入队操作：
方法一中，先要入队的结点申请一个空间，并将新结点的值赋给p->data = x；将新结点p的后续置空：q->next = NULL;接着将新结点p赋值给原队尾结点的后继：lq->rear->front = p；最后，把当前结点p设置为新队尾结点：lq->rear = p；
方法二中：直接给原队尾的后续开辟一个结点空间：lq->rear->next = (qptr)malloc(sizeof(qnode));然后将新开辟的结点设置为队尾结点：lq->rear = lq->rear->front；接着赋值：lq->rear->data = x；最后将新队尾结点的后续置空：lq->rear->next = NULL;
1 int EnterLinkQueue(linkqueue *lq, datatype x) 2 { 3 qptr *p; 4 p = (qptr *)malloc(sizeof(qnode)); 5 if (p == NULL) 6 return -1; 7 p->data = x; 8 p->next = NULL; 9 10 lq->rear->front = p; 11 lq->rear = p; 12 return 0; 13 } 14 15 int EnterLinkQueueTwo(linkqueue *lq, datatype x) 16 { 17 lq->rear->next = (qptr *)malloc(sizeof(qnode)); 18 lq->rear = lq->rear->next; 19 20 lq->rear->data = x; 21 lq->rear->next = NULL; 22 return 0; 23 }
链队列的出队操作：出队操作在队头，即将头结点的后继出队，让头结点的后继的后继结点作为新的头结点后继结点。额。。。。。。若队列除头结点外只剩下一个元素时，则需要将rear指针指向头结点。
方法一：首先判断链队列是否为空，然后用一个结点指针p指向待删的队头结点：p = lq->front->next；并保存其值。接着，将待删结点的后继赋给头结点的后继：lq->front->next = p->next;判断，如果队头是队尾，则删除后将rear指向头结点。如果链队列中只有一个元素，则出队后，lq->rear应该指向头结点，即lq->rear=lq->front
方法二：直接将头结点下移至原链队列的队头元素的位置。然后删除原头结点，设置新的头结点。
1 datatype DeleteQueue(linkqueue *lq) 2 { 3 datatype data; 4 qptr p; 5 6 if (lq->front == lq->rear) 7 { 8 printf("linkqueue empty\n"); 9 return -1; 10 } 11 p = lq->front->next; 12 data = p->data; 13 lq->front->next = p->next; 14 if (lq->rear == p) 15 { 16 lq->rear = lq->front; 17 } 18 free(p); 19 return data; 20 } 21 22 datatype DeleteQueueTwo(linkqueue *lq) 23 { 24 qptr q; 25 p = lq->front; 26 lq->front = q->next; 27 free(p); 28 return lq->front->data; 29 }
创建一个空链队列：一个是链队列结构，一个是结点结构。
1 linkqueue *CreateLinkQueue() 2 { 3 linkqueue *lq; 4 lq = (linkqueue *)malloc(sizeof(linkqueue)); 5 6 lq->front = lq->rear = (qptr)malloc(sizeof(qnode)); 7 lq->front->next = NULL; 8 return lq; 9 }
创建一个空顺序循环队列：
1 int InitQueue(squeue * sq) 2 { 3 sq->front = 0; 4 sq->rear = 0; 5 return 0; 6 }
循环队列和链队列比较：1、从时间复杂度上考虑，他们的操作都是常数时间O（1），不过循环队列的顺序结构要事先申请好空间，使用期间不释放，而对于链式队列，每次申请和释放也会存在一些时间开销，如果入队出队频繁，则两者还是存在细微的差异。2、从空间复杂度上考虑，循环队列的顺序结构必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在该问题，尽管需要一个指针域的空间开销，但还是可以接受的，因此在空间上，链队列更加灵活。
如果在确定队列长度最大值的情况下，建议使用循环队列的顺序结构，如果无法预估队列的长度时，用链队列。
2013-02-02 14:18