亲宝软件园·资讯

展开

C语言 队列

。菀枯。 人气:0

前言

前一段时间,我们试着用C语言实现了数据结构中的顺序表,单链表,双向循环链表,栈。今天我们再用C语言来实现另一种特殊的线性结构:队列

一. 什么是队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(head)进行删除操作,而在表的后端(tail)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

这个队列就可以理解成我们平时的排队,先进入的先出去,与我们之前实现的先进后出的栈相反。

二. 使用什么来实现栈

再把上次的图拿出来,我们看看是用线性表来实现队列,还是链表比较好

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问可以直接访问任何元素必须从头节点开始往后寻找
任意位置插入或删除元素要搬移其他的元素,效率低。只需要修改节点的指针指向,效率高
插入动态顺序表,当空间不够时需要扩容无容量概念,需要就申请,不用就释放
应用场景元素高效存储,并且需要频繁访问需要在任意位置插入或者删除频繁

综合上表来看,我觉得链表较为方便,原因如下:

1.队列有多少元素不确定,链表可以做到需要就申请,不用就释放,较为方便

2.队列是先进先出,顺序固定,不需要随机访问。

三. 队列的实现

3.1头文件

1.包含的标准库

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

2.定义结构体

typedef int QDateType;//队列存储数据类型

typedef struct QueueNode //队列元素节点
{
	QDateType val;
	struct QueueNode* next;
}QueueNode;

typedef	struct Queue //队列
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

3.函数声明

void QueueInti(Queue* pq);
// 队列初始化
void QueueDestory(Queue* pq);
// 队列的销毁
void QueuePush(Queue* pq, QDateType x);
// 入队
void QueuePop(Queue* pq);
// 出队
QDateType QueueFront(Queue* pq);
// 取出队首元素
int QueueSize(Queue* pq);
// 求队列的长度
bool QueueEmpty(Queue* pq);
// 判断队是否为空

3.2 函数的实现

1.队列的初始化

将头尾置为空指针即可。

void QueueInti(Queue* pq)
{
    assert(pq); //防止pq为空指针
    pq->head = pq->tail = NULL;
}

2.队列的销毁

遍历队列元素,然后将每一个元素释放。

void QueueDestory(Queue* pq)
{
    assert(pq); //防止pq为空指针
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->tail = pq->head = NULL;
}

3.入队

对于入队,我们首先需要去开辟一个新的节点来存储数据,然后将这个节点加入到tail后即可。此时我们就要分别考虑。

1.如果为空队列,那么我们不仅要改变tail,还要改变head的值

2.如果不为空队列,只用改变tail即可。

void QueuePush(Queue* pq, QDateType x)
{
	assert(pq); //防止pq为空指针

	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newNode)
	{
		printf("malloc error\n");
		exit(-1);
	}
	newNode->val = x;
	newNode->next = NULL;//开辟一个新节点存储数据

	if (pq->tail == NULL)//判断是否为空队列
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

4.出队

对于出队,我们同样需要考虑两种情况

void QueuePop(Queue* pq)
{
    assert(pq);//防止pq为空指针
    assert(pq->head && pq->tail); //防止队列为空队列
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QueueNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

5. 取出队首元素

没啥说的,直接访问头节点取出即可

QDateType QueueFront(Queue* pq)
{
    assert(pq);//防止pq为空指针
    assert(pq->head && pq->tail); //防止队列为空队列

    return pq->head->val;
}

6.判断是否为空队列

我们只需要判断头指针是否为NULL,如果是则为空

bool QueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->head == NULL;
}

7. 求队伍长度

创建一个变量,遍历队伍求长度。

int QueueSize(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    int count = 0;
    while (cur)
    {
        cur = cur->next;
        count++;
    }
    return count;
}

四.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDateType;

typedef struct QueueNode
{
	QDateType val;
	struct QueueNode* next;
}QueueNode;

typedef	struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

void QueueInti(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->tail = pq->head = NULL;
}

void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);

	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newNode)
	{
		printf("malloc error\n");
		exit(-1);
	}
	newNode->val = x;
	newNode->next = NULL;

	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}

}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->val;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	int count = 0;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;
}

加载全部内容

相关教程
猜你喜欢
用户评论