队列的多种C语言实现

欢迎访问我的新博客：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函数为测试函数，且均省略了对上溢和下溢的检验！

（全文完）