欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列的多种C语言实现

程序员文章站 2022-07-14 14:24:58
...

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

(全文完)

转载于:https://www.cnblogs.com/milkcu/archive/2013/06/11/3808886.html