[C++知识库] 数据结构 (七) 线性表

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 数据结构 (七) 线性表_队列 -> 正文阅读

[C++知识库]数据结构 (七) 线性表_队列

文章目录

一. 队列的基本概念

队列是一种特殊的受限制的线性表
队列只允许在一端进行插入操作,在另外一端进行删除操作的线性表
队列是一种先进先出(First In First Out),FIFO.允许插入的一端为队尾,允许删除的一端为队头.
队列不允许在中间部位进行操作,删除的时候,总是从队头删除,插入的时候插入到队尾.

二. 队列的顺序存储实现

使用一块连续的内存空间来实现队列的存储
我们使用列表来实现一个队列

SeqQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define QUEUE_MAX 1024
#define SEQ_QUEUE_TRUE 1
#define	SEQ_QUEUE_FALSE 0

typedef struct SeqQueue
{
	void *data[QUEUE_MAX];
	int size;
}SeqQueue;


// 初始化队列
SeqQueue *init_seq_queue();

// 入队
void push_seq_queue(SeqQueue* q, void * data);

// 出队
void  pop_seq_queue(SeqQueue *q);

// 获取队首元素
void *front_seq_queue(SeqQueue *q);

// 获取队尾元素
void *back_seq_queue(SeqQueue *q);

// 判断队列是否为空
int is_empty(SeqQueue *sq);

// 获取队列的大小
int get_size_seq_queue(SeqQueue *q);

// 清空队列
void clear_seq_queue(SeqQueue *q);

// 销毁队列
void destroy_seq_queue(SeqQueue *q);

SeqQueue.c

#include "SeqQueue.h"
// 初始化队列
SeqQueue *init_seq_queue()
{
	SeqQueue *q = (SeqQueue *)malloc(sizeof(SeqQueue));
	if (q != NULL)
	{
		for (int i = 0; i < QUEUE_MAX; i++)
		{
			q->data[i] = NULL;
		}
		q->size = 0;
	}
	return q;
}

// 入队
void push_seq_queue(SeqQueue* q, void *data)
{
	// 放到队尾部
	if (data != NULL && q != NULL && q->size < QUEUE_MAX)
	{
		q->data[q->size] = data;
		q->size++;
	}
}

// 出队
void  pop_seq_queue(SeqQueue *q)
{
	if (q != NULL && q->size > 0)
	{
		for (int i = 0; i < q->size - 1; i++)
		{
			// 后面的元素全部前移
			q->data[i] = q->data[i + 1];
		}
		// 最后一个节点置空
		q->data[q->size - 1] = NULL;
		q->size--;
	}
}

// 获取队首元素
void *front_seq_queue(SeqQueue *q)
{
	if (q != NULL && q->size > 0)
	{
		return q->data[0];
	}
	return NULL;
}

// 获取队尾元素
void *back_seq_queue(SeqQueue *q)
{
	if (q != NULL && q->size > 0)
	{
		return q->data[q->size - 1];
	}
	return NULL;
}

// 判断队列是否为空
int is_empty(SeqQueue *q)
{
	if (q != NULL)
	{
		return q->size == 0 ? SEQ_QUEUE_TRUE : SEQ_QUEUE_FALSE;
	}
	return SEQ_QUEUE_FALSE;
}

// 获取队列的大小
int get_size_seq_queue(SeqQueue *q)
{
	if (q != NULL)
	{
		return q->size;
	}
	return -1;
}

// 清空队列
void clear_seq_queue(SeqQueue *q)
{
	if (q != NULL)
	{
		for(int i = 0;i <q->size;i++)
		{
			q->data[i] = NULL;
		}
		q->size = 0;
	}
}

// 销毁队列
void destroy_seq_queue(SeqQueue *q)
{
	if (q != NULL)
	{
		free(q);
	}
}

测试代码

#include "SeqQueue.h"

int main()
{
	// 创建一个队列
	SeqQueue *q = init_seq_queue();
	// 往队列中添加5个数
	// 入队 1,2,3,4,5
	int arr[5] = { 1,2,3,4,5 };
	for (int i = 0; i < 5; i++)
	{
		//push_seq_queue(q,(void *)&i);// 想一下这行代码为啥是错误的
		push_seq_queue(q, (void *)&(arr[i]));
	}
	// 查看栈大小
	printf("5个数据入队之后的大小: %d\n", q->size);
	printf("队头: %d, 队尾: %d\n", *(int *)front_seq_queue(q), *(int *)back_seq_queue(q));
	// 出队,然后并按照出队顺序打印
	/*for (int i = 0; i < q->size; i++)
	{
		printf("第 %d 个出队的数据为: %d\n", i + 1, *(int *)front_seq_queue(q));
		pop_seq_queue(q);
	}*/
	// 上面这个打印会有问题,想想是为了什么?
	// 因为在出栈的时候q->size的大小是变动的,所以你本意q->size是5打印五次,但是打着打着q->size变小了

	// 可以使用while循环出栈打印
	int index = 1;
	while (q->size > 0)
	{
		printf("第 %d 个出队的数据为: %d\n", index, *(int *)front_seq_queue(q));
		pop_seq_queue(q);
		index++;
	}

	// 全部出队之后,看看栈是否为空,如果为空,再添加两个元素
	if (is_empty(q))
	{
		push_seq_queue(q, (void *)(&arr[0]));
		push_seq_queue(q, (void *)(&arr[1]));
		printf("入队两个之后队列大小: %d,队头: %d,队尾: %d\n", q->size, *(int *)front_seq_queue(q),*(int*)back_seq_queue(q));
		// 清空队列,然后查看大小
		clear_seq_queue(q);
		printf("清空之后大小为: %d\n", q->size);
	}
	else
	{
		printf("出错了,全部都出队了,队列不为空!");
	}

	// 销毁队列
	destroy_seq_queue(q);

	system("pause");
	return 0;
}

结果:

三. 队列的链式存储

使用链表来实现队列
单向链表实现队列
链表的最后一个节点是队尾
链表的第一个节点是队头
插入的时候,就正常插入,插入到链表的尾部,也就是队尾
取出的时候,在头部取出,这样就保证了先进先出.
注意头节点的设计,一开始的头节点是指向NULL

头文件 LinkQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LINK_QUEUE_TRUE 1
#define LINK_QUEUE_FALSE 0

typedef struct LinkNode
{
	struct LinkNode *next;
	void *data;
} LinkNode;

typedef struct LinkQueue
{
	LinkNode *head;
	int size;
}LinkQueue;

// 初始化
LinkQueue *init_link_queue();

// 入队
void push_link_queue(LinkQueue *q, void *node);

// 出队
void pop_link_queue(LinkQueue *q);

// 获取队头节点
void *front_link_queue(LinkQueue *q);

// 获取队尾节点
void *back_link_queue(LinkQueue *q);

// 获取队列大小
int get_size_link_queue(LinkQueue *q);

// 判断队列是否为空
int is_empty(LinkQueue *q);

// 清空队列
void clear_link_queue(LinkQueue *q);

// 销毁队列
void destroy_link_queue(LinkQueue *q);

实现部分: LinkQueue.c

#include "LinkQueue.h"
// 初始化
LinkQueue *init_link_queue()
{
	LinkQueue *q = (LinkQueue *)malloc(sizeof(LinkQueue));
	LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
	if (q != NULL && node != NULL)
	{
		node->data = NULL;
		node->next = NULL;
		q->head = node;
		q->size = 0;
	}
	return q;
}

// 入队,插入到尾部
void push_link_queue(LinkQueue *q, void *data)
{
	// 入队
	if (q != NULL && data != NULL)
	{
		// 创建新的节点
		LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));
		if (newNode != NULL)
		{
			newNode->data = data;
			newNode->next = NULL;
		}
		// 遍历节点,找到最后一个节点
		LinkNode *pCurrent = q->head; // 头节点
		while (pCurrent->next != NULL)
		{
			pCurrent = pCurrent->next;
		}
		pCurrent->next = newNode;
		q->size++;
	}

}

// 出队,删除第一个节点
void pop_link_queue(LinkQueue *q)
{
	if (q != NULL && q->size > 0)
	{
		// 要删除的节点
		LinkNode *nodeDel = q->head->next;
		q->head->next = nodeDel->next;
		free(nodeDel);
		q->size--;
	}
	
}

// 获取队头数据,也就是获取第一个节点
void *front_link_queue(LinkQueue *q)
{
	if (q != NULL && q->size > 0)
	{
		LinkNode *nodeTemp = q->head->next;
		return nodeTemp->data;
	}
	return NULL;
}

// 获取队尾数据
void *back_link_queue(LinkQueue *q)
{
	if (q != NULL && q->size > 0)
	{
		LinkNode *nodeLast = q->head->next;
		while (nodeLast->next != NULL)
		{
			nodeLast = nodeLast->next;
		}
		return nodeLast->data;
	}
	return NULL;
}

// 获取队列大小
int get_size_link_queue(LinkQueue *q)
{
	if (q != NULL)
	{
		return q->size;
	}
	return -1;
}

// 判断队列是否为空
int is_empty(LinkQueue *q)
{
	if (q != NULL)
	{
		return q->size == 0 ? LINK_QUEUE_TRUE : LINK_QUEUE_FALSE;
	}
	return LINK_QUEUE_TRUE;
}

// 清空队列
void clear_link_queue(LinkQueue *q)
{
	if (q != NULL)
	{
		q->size = 0;
		q->head->next = NULL;
	}
}

// 销毁队列
void destroy_link_queue(LinkQueue *q)
{
	if (q != NULL)
	{
		LinkNode *pCurrent = q->head;
		while (pCurrent->next != NULL)
		{
			free(pCurrent->next);
			pCurrent = pCurrent->next;
		}
		free(q);
	}
}

测试代码

#include"LinkQueue.h"
int main()
{
	int arr[5] = { 1,2,3,4,5 };
	// 队列初始化和入队
	LinkQueue *q = init_link_queue();
	int arrLen = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < arrLen; i++)
	{
		push_link_queue(q, (void *)&(arr[i]));
	}
	printf("入队后队列大小: %d,队头: %d,队尾: %d\n", get_size_link_queue(q),*(int*)front_link_queue(q),*(int*)back_link_queue(q));

	int temp;
	int index = 1;
	// 然后是出队
	while (q->size > 0)
	{
		temp = *(int *)front_link_queue(q);
		printf("第 %d 次出队的数据: %d\n", index, temp);
		pop_link_queue(q);
	}
	// 如果队列是空,再存放两个数据1,2
	if (is_empty(q))
	{
		push_link_queue(q, (void *)&arr[0]);
		push_link_queue(q, (void *)&arr[1]);
		printf("存入两个数之后,队列大小: %d,队头: %d,队尾: %d\n", get_size_link_queue(q), *(int *)front_link_queue(q), *(int *)back_link_queue(q));

	}
	else
	{
		printf("出错,全部出队之后,队列不为空!");
	}

	// 清空队列
	clear_link_queue(q);
	printf("清空之后队列大小: %d\n", get_size_link_queue(q));

	destroy_link_queue(q);

	system("pause");
	return 0;
}