数据结构(初阶)—— 栈和队列②

数据结构(初阶)—— 栈和队列②_第1张图片

目录

一、队列的概念和结构

二、链式结构表示队列

三、队列各个接口函数的实现 

1.队列的初始化 

 2.队尾入队列(尾插)

3.队头出队列(头删) 

4.取队头的数据 

5.取队尾的数据 

6.计算队列的数据个数 

7.判断队列是否为空 

四、源代码 

Queue.h 

Queue.c

Test.c 


一、队列的概念和结构

        队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有 先进先出FIFO (First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头;
        队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。( 一般如果采用顺序栈,常设计成循环队列的形式,这个放到下一期博客说
数组实现队列:
数据结构(初阶)—— 栈和队列②_第2张图片

链表实现队列: 

 数据结构(初阶)—— 栈和队列②_第3张图片

二、链式结构表示队列

        用链式结构表示队列,我们需要两个指针,一个控制队尾,一个控制队头,方便数据入队和出队;如果不控制队尾,那么在入数据的时候,我们就需要先去找到队尾(即链表的尾),这就很麻烦;

typedef int QDataType;
//链表的结构
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
    //都是链表的指针,head和tail都可以去访问链表,在处理入队和出队上就很方便了
	QNode* head;//队头
	QNode* tail;//队尾
}Queue;

三、队列各个接口函数的实现 

1.队列的初始化 

//队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

 2.队尾入队列(尾插)

        队列相当于在单链表的基础上加了一些限制,并且多了头尾指针的控制,在进行尾插的时候相比单链表快了很多,单链需要循环判断找尾,而队列可以直接找到尾 ;

如果单链表还不太清楚的同学可以复习一下:https://blog.csdn.net/sjsjnsjnn/article/details/123920224?spm=1001.2014.3001.5501

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
        //第一个元素入队
		pq->head = pq->tail = newnode;
	}
	else
	{
        //数据队尾入
		pq->tail->next = newnode;
        //tail控制队尾(记住新的尾)
		pq->tail = newnode;
	}
}

数据结构(初阶)—— 栈和队列②_第4张图片

3.队头出队列(头删) 

        在头删的时候要注意,当头删删到队尾时候,此时head和tail指向的同一块空间,要记得把tail也要释放了; 

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	//此时head和tail同时指向最后一个空间,释放head后,要注意也要把tail释放了
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

数据结构(初阶)—— 栈和队列②_第5张图片

4.取队头的数据 

//取队头的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列是否为空
	return pq->head->data;//直接返回头指针所指向的数据
}

5.取队尾的数据 

//取队尾的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列是否为空
	return pq->tail->data;//直接返回尾指针所指向的数据
}

6.计算队列的数据个数 

//计算队列的数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int n = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
	return n;
}

7.判断队列是否为空 

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

四、源代码 

Queue.h 

#include 
#include 
#include 
#include 

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

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

//队列的初始化
void QueueInit(Queue* pq);

//队列的销毁
void QueueDestroy(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq, QDataType x);

//队头出队列
void QueuePop(Queue* pq);

//取队头的数据
QDataType QueueFront(Queue* pq);

//取队尾的数据
QDataType QueueBack(Queue* pq);

//计算队列的数据个数
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

 Queue.c

#include "Queue.h"

//队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

//队列的销毁
void QueueDestroy(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));
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	//此时head和tail同时指向最后一个空间,释放head后,要注意也要把tail释放了
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}


//取队头的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}


//取队尾的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

//计算队列的数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int n = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
	return n;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

Test.c 

#include "Queue.h"

void QueueTest1()
{
	Queue q;
	QueueInit(&q);
	//数据入队
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePush(&q, 7);
	QueuePush(&q, 8);
	
	//1 2 3 出队列
	//QueuePop(&q);
	//QueuePop(&q);
	//QueuePop(&q);
	while (!QueueEmpty(&q))
	{
		QDataType front = QueueFront(&q);
		printf("%d ", front);
		QueuePop(&q);
	}
	QueueDestroy(&q);
}

int main()
{
	QueueTest1();
	return 0;
}

你可能感兴趣的