亲宝软件园·资讯

展开

C语言队列

平凡的人1 人气:0

前言

大家好啊,我又双叒叕来水博客了,道路是曲折的,前途是光明的,事物是呈螺旋式上升的,事物最终的发展结果还是我们多多少少能够决定的,好啦,吹水结束,这与这篇博客的主题并没有太多联系。关于栈和队列这一板块本来是想不写(就是想偷懒),但是想了想,觉得这样不太好,关于数据结构这一块可能会有缺失,所以最终还是决定写,必须补齐这一块,恰好最近有时间写博客,所以还是写了,这篇博客将介绍队列的知识点,理解链表那一块的操作后,栈和队列的相关操作还是比较容易去理解的。

队列的表示和实现

队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First in First Out)

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

敲黑板,开始摸鱼:

其实也没什么重点啦,都是一些基本的概念性东西,主要有:

1.要理解FIFO代表的意思

2.什么是队尾队头,别弄混了

队列的实现有两种方法:

数组:不适合,队头出数据需要挪动数据,一般还会出现假溢出,循环队列啥的

链表:单链表较合适,头删尾插,效率较高

当然,并不是说一定要用哪种,由于课本是以数组为例,这里以单链表为例

代码实现

还是老样子,分为三部分,直接上手代码,来,跟着我一起敲

Queue.h

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
 typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
 //初始化
 void QueueInit(Queue* pq);
 //销毁
 void QueueDestory(Queue* pq);
 //队尾入
 void QueuePush(Queue* pq, QDataType x);
 //队头出
 void QueuePop(Queue* pq);
 //取队头数据
 QDataType QueueFront(Queue* pq);
 //取队尾数据
 QDataType QueuBack(Queue* pq);
 //个数
 int QueueSize(Queue* pq);
 //判断是否为空
 bool QueueEmpty(Queue* pq);

Queue.c

#include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
//队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
//队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	//1.一个(防止野指针)
	//2.多个
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueuBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

Test.c

#include "Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestory(&q);
}
int main()
{
	TestQueue();
	return 0;
}

束语

关于堆栈和队列的相关操作就说到这里了,如果对你有帮助的话,那就点个赞把!

加载全部内容

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