数据结构与算法--用c语言建立队列以及其相关操作

一.队列的定义和特点

队列与栈一样，也是一种特殊的线性表，与栈”先进后出“不同的是，队列服从“先进先出”，也就是元素从队尾进入队列，从队头离开，如图所示：

a1最先进入队列，因此最先从对头离开队列，然后是a2，以此类推。

二.队列的相关操作及其代码

队列同意分为顺序队列和链式队列，因链式队列使用较多，在此我将以链式队列--银行排队系统作为演示

1.队列的建立（初始化）

首先定义一个结构体变量用来存放队列结点的数据和指向下一个结点的指针，并且申请一个新的结点作为头节点，使其的指针指向空，代码如下：

struct people{
	char name[5];
	struct people *next;
};

int m = 0,n = 0;        //用来记录目前排队人数和总人数

struct people *creat()
{
	struct people *head;
	head = new people;
	head->next = NULL;
	printf("创建队列成功！\n");
	return head;
}

2.入队列操作

申请一个新结点，存入数据，再将此结点接入队列的末尾，即使上一个结点的指针指向新结点，代码如下：

void enter(struct people *head)
{
	struct people *p1,*p2;
	p1 = head;
	while(p1->next != 0)
	{
		p1 = p1->next;
	}
	p2 = new people;
	printf("请输入排队人的姓名:\n");
	scanf("%s",&p2->name);
	p1->next = p2;
	p2->next = NULL;
	printf("进入队列成功!\n");
	n++;       //总人数加一 
	m++;       //队列中现有人数加一
}

3.出队列操作

头结点之后的结点出队列（头结点中不存放数据），即将头结点的next指针指向第二个结点，释放掉第一个结点，代码如下：

void leave(struct people *head)
{
	struct people *p1,*p2;
	if(head->next == NULL)        //若队列为空，则直接跳出
	{
		printf("该队列没有人！\n");
		return;
	}
	p1 = head->next;
	p2 = p1->next;
	head->next = p2;
	free(p1);
	printf("离开队列成功!\n");
	m--;        //现队列人数减一
}

4.打印队列中的元素

将队列中的数据从队头开始显示到屏幕上，代码如下：

void print(struct people *head)
{
	struct people *p;
	p = head;
	if(p->next == NULL)        //若队列没有元素，则直接跳出
	{
		printf("该队列没有人！\n");
		return;
	}
	printf("当前排队情况为:\n");
	do
	{	
		p = p->next;
		printf("%s ",p->name);
	}while(p->next != 0);
	printf("\n");
}

完整代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct people{
	char name[5];
	struct people *next;
};

int n = 0,m = 0;

struct people *creat()
{
	struct people *head;
	head = new people;
	head->next = NULL;
	printf("创建队列成功！\n");
	return head;
}

void enter(struct people *head)
{
	struct people *p1,*p2;
	p1 = head;
	while(p1->next != 0)
	{
		p1 = p1->next;
	}
	p2 = new people;
	printf("请输入排队人的姓名:\n");
	scanf("%s",&p2->name);
	p1->next = p2;
	p2->next = NULL;
	printf("进入队列成功!\n");
	n++;
	m++;
}

void leave(struct people *head)
{
	struct people *p1,*p2;
	if(head->next == NULL)
	{
		printf("该队列没有人！\n");
		return;
	}
	p1 = head->next;
	p2 = p1->next;
	head->next = p2;
	free(p1);
	printf("离开队列成功!\n");
	m--;
}

void print(struct people *head)
{
	struct people *p;
	p = head;
	if(p->next == NULL)
	{
		printf("该队列没有人！\n");
		return;
	}
	printf("当前排队情况为:\n");
	do
	{	
		p = p->next;
		printf("%s ",p->name);
	}while(p->next != 0);
	printf("\n");
}

int main()
{
	int a;
	struct people *str;
	
	printf("欢迎进入银行排队系统：\n1.创建队列\n2.进入队列\n3.离开队列\n4.查询前面的客户\n5.查询办理总人数\n6.退出系统\n");
	printf("请输入:\n");
	scanf("%d",&a);
	while(a != 6)
	{
		switch(a)
		{
			case 1:{
				str = creat();
				break;
			}
			case 2:{
				enter(str);
				print(str);
				break;
			}
			case 3:{
				leave(str);
				print(str);
				break;
			}
			case 4:{
				printf("前面还有%d位客户\n",m);
				break;
			}
			case 5:{
				printf("银行今日共接待了%d位客户\n",n);
				break;
			}
		}
		printf("请输入:\n");
		scanf("%d",&a);	
	}
}

三.总结

队列在实际生活中应用非常广泛，并且个人认为，链式结构的队列比顺序结构的队列要更加实用