欢迎访问我的新博客：http://www.milkcu.com/blog/
原文地址：http://www.milkcu.com/blog/archives/1370916840.html
标题：队列的多种C语言实现
内容：队列是先进先出（FIFO）的线性表，C语言中可以使用数组、全局变量、引用实现队列。
作者：MilkCu
概念
队列的操作
队列是受限制的线性表，只允许在队尾（tail）插入、对头（head）删除。
队列的操作方式与堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
队列的属性
以队列q为例。
q.head指向队头元素；
q.tail指向下一个新元素将要插入的位置。
在队列中，位置1紧邻在n的后面形成一个环序。
队列的状态
当q.head = q.tail时，队列为空，
初始时有q.head = q.tail = 1 ；
当q.head = q.tail + 1时，队列是满的 。
数组实现
利用数组q.key[n]实现一个最多容纳n-1个元素的队列。
# include <stdio.h>
# define M 100
typedef struct queue {
int head;
int tail;
int key[M];
int length;
} queue;
queue q;
void enqueue(int x);
int dequeue(void);
int main(void)
{
q.head = q.tail = 1;
q.length = 98;
enqueue(1);
enqueue(3);
enqueue(5);
enqueue(7);
printf("%d\n", dequeue());
printf("%d\n", dequeue());
printf("%d\n", dequeue());
printf("\t%d\n", q.head);
printf("%d\n", dequeue());
}
void enqueue(int x)
{
q.key[q.tail] = x;
if(q.tail == q.length) {
q.tail = 1;
} else {
q.tail++;
}
}
int dequeue(void)
{
int x;
x = q.key[q.head];
if(q.head == q.length) {
q.head = 1;
} else {
q.head++;
}
return x;
}全局变量实现
全局变量也挺方便的，只是注意不要和局部变量重名而被取代了。
# include <stdio.h>
# define M 100
typedef struct queue {
int head;
int tail;
int key[M];
int length;
} queue;
void enqueue(queue * qp, int x);
int dequeue(queue * qp);
int main(void)
{
queue q;
q.head = q.tail = 1;
q.length = 98;
enqueue(&q, 1);
enqueue(&q, 3);
enqueue(&q, 5);
enqueue(&q, 7);
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
}
void enqueue(queue * pq, int x)
{
pq -> key[pq -> tail] = x;
if(pq -> tail == pq -> length) {
pq -> tail = 1;
} else {
pq -> tail++;
}
}
int dequeue(queue * pq)
{
int x;
x = pq -> key[pq -> head];
if(pq -> head == pq -> length) {
pq -> head = 1;
} else {
pq -> head++;
}
return x;
}引用传参实现
引用是C++的特性，在一些数据结构的表示中也是挺方便的，只可惜C语言没有，可能被指针代替了吧。
# include <stdio.h>
# define M 100
typedef struct queue {
int head;
int tail;
int key[M];
int length;
} queue;
void enqueue(queue & q, int x);
int dequeue(queue & q);
int main(void)
{
queue q;
q.head = q.tail = 1;
q.length = 98;
enqueue(q, 1);
enqueue(q, 3);
enqueue(q, 5);
enqueue(q, 7);
printf("%d\n", dequeue(q));
printf("%d\n", dequeue(q));
printf("%d\n", dequeue(q));
printf("\t%d\n", q.head);
printf("%d\n", dequeue(q));
}
void enqueue(queue & q, int x)
{
q.key[q.tail] = x;
if(q.tail == q.length) {
q.tail = 1;
} else {
q.tail++;
}
}
int dequeue(queue & q)
{
int x;
x = q.key[q.head];
if(q.head == q.length) {
q.head = 1;
} else {
q.head++;
}
return x;
}上面的程序中，main函数为测试函数，且均省略了对上溢和下溢的检验！
（全文完）