数据结构之普通队列C语言版

文章目录

• 数据结构之普通队列C语言版
• • 什么是普通队列
  • 简单使用C语言实现普通队列
  • • 前期准备
    • 结构体封装
    • 初始化队列
    • 判断队列是否为空
    • 判断队列是否满队
    • 获取队列当前元素个数
    • 获取队头
    • 出队函数
    • 测试函数

什么是普通队列

队列是一种数据结构，是用来存储数据的，普通队列是队列里最简单的，也比较好理解。操作和栈是差不多的。队列和栈的区别就是，栈是先进后出，队列是先进先出。然后就没有多大的区别了。

简单使用C语言实现普通队列

队列的基本概念就这么多，想深入了解概念的请看课本去。这里是使用编程语言来实现队列的。

前期准备

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAXSIZE 10

主要是包含是头文件，然后是预定义一个最大容量。

结构体封装

要实现一个数据结构首先是知道数据结构的样子是什么，然后画出来，然后对应的内容就使用对应的数据类型封装，在C语言中，就使用结构体来封装队列的各个组件。

队列的基本样子：

从图中可以看到的是队列有队头和队尾，所以使用两个标记去表示，left靠队头这边，right靠队尾这边。那就开始封装吧。

typedef struct Queue
{
	int elem[MAXSIZE];
	int left;
	int right;
	int curSize;
}Queue,*pQueue;

typedef是取别名：

typedef struct Queue Queue		//Queue是struct Queue的别名
typedef struct Queue* pQueue	//pQueue是struct Queue*的别名

初始化队列

pQueue creatQueue()
{
	pQueue head = (pQueue)malloc(sizeof(Queue));
	assert(head);
	head->left = -1;
	head->right = -1;
	head->curSize = 0;
	return head;
}

left和right一开始都初始化为-1方便等下操控elem数组。这里的初始化很随意，不过就是等下实现源代码的时候会做一些改变。问题不是很大。在堆区申请的内存，在函数结束后不会释放。

判断队列是否为空

int empty(pQueue head)
{
	return head->curSize == 0;
}

这就是万金油参数curSize的好处，封装好了之后就直接使用，如果不封装curSize成员的话也可以采用right-left表示。一样的意思。但我不想折磨自己，怎么简单怎么来。

判断队列是否满队

int full(pQueue head)
{
	return head->curSize >= MAXSIZE;	//MAXSIZE是已经预定义的量，10
}

获取队列当前元素个数

int size(pQueue head)
{
	return head->curSize;
}

直接返回curSize成员，没什么好说的。

获取队头

int front(pQueue head)
{
	return head->elem[head->left];
}

因为队列的特点是先进先出。所以封装一个获取头部元素的函数来调用队列中的数组的第一个元素（根据实际情况而言，因为等下出队的时候left会往右移动，所以就是返回elem数组中left表示下标下的元素）。函数的结构也很多简单。

出队函数

void pop(pQueue head)
{
	if (head->curSize == 0)
	{
		head->left = -1;
		head->right = -1;
		return;
	}
	head->left++;
	head->curSize--;
}

根据curSize的值判断当前队列是否为空的队列，如果为空队列就直接结束掉函数，在结束之前记得把left和right复位，回到最初的状态，因为已经出队了left和right没有比较在elem的中间位置或者的最后，而应该是回到elem数组第一个元素的前一个元素，也就是-1的位置。

测试函数

void test1()
{
	pQueue que = creatQueue();
	for (int i = 0; i < 3; i++)
	{
		push(que, i);
	}
	printf("%d\t%d\n", empty(que), size(que));
	while (!empty(que))
	{
		printf("%d ", front(que));
		pop(que);
	}
	printf("\n%d\t%d\n", empty(que), size(que));
	for (int i = 5; i < 9; i++)
	{
		push(que, i);
	}
	printf("%d\t%d\n", empty(que), size(que));
	while (!empty(que))
	{
		printf("%d ", front(que));
		pop(que);
	}
	printf("\n%d\t%d\n", empty(que), size(que));
	for (int i = 0; i < 6; i++)
	{
		push(que, i);
	}
	printf("%d\t%d\n", empty(que), size(que));
	for (int i = 6; i < 11; i++)
	{
		push(que, i);
	}
	printf("%d\t%d\n", empty(que), size(que));
	while (!empty(que))
	{
		printf("%d ", front(que));
		pop(que);
	}
	printf("\n%d\t%d\n", empty(que), size(que));
	for (int i = 10; i < 21; i++)
	{
		push(que, i);
	}
	printf("%d\t%d\n", empty(que), size(que));
	while (!empty(que))
	{
		printf("%d ", front(que));
		pop(que);
	}
	printf("\n%d\t%d\n", empty(que), size(que));
}

在主函数中调用这个函数，然后就会得到下面的结果：

0       3
0 1 2
1       0
0       4
5 6 7 8
1       0
0       6
队列已满
0       10
1 2 3 4 5 6 7 8 9 10
1       0
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
队列已满
0       11
11 -33686019 -1937940619 -1937940619 -2079107460 799472782 789760239 803142870 803142870 -211528068 1694151040
1       0

队列就这样了，反复练就容易了。

把数据结构简单化-----------Cukor丘克