C语言 队列

目录

一、队列概念

二、基础数组队列

三、基础链表队列

四、数组队列 -- 函数

五、链表队列 -- 函数

一、队列概念

先进先出，后进后出
第一个元素无数据
数组队列长度 -- 根据数组长度决定
链表队列长度 -- 根据电脑内存决定

二、基础数组队列

#include <stdio.h>
#include <malloc.h>
// 队列: 先进先出，后进后出
// 循环队列 -- 数组
// 最大存储个数 MAXSIZE-1
// 队列第一个无数据

// 队空：queue->front == queue->rear
// 队满：(queue->rear + 1) % MAXSIZE == queue->front

#define MAXSIZE 3

typedef struct {
    int data[MAXSIZE];
    // 头指针
    int front;
    // 尾指针
    int rear;
}SqQueue;

int main()
{
    int inData = 100;
    int outData = 0;

    // 定义队列指针
    SqQueue* queue;
    // 申请队列内存
    queue = (SqQueue*)malloc(sizeof(SqQueue));
    // 头尾指针初始化
    queue->front = queue->rear = 0;

    // 入队
    if ((queue->rear + 1) % MAXSIZE == queue->front)
    {
        printf("队列已满，入队失败\n");
    }
    else
    {
        queue->rear = (queue->rear + 1) % MAXSIZE;
        queue->data[queue->rear] = inData;
        printf("%d\n", queue->data[queue->rear]);
    }

    // 出队
    if (queue->front == queue->rear)
    {
        printf("队列已空，出队失败\n");
    }
    else
    {
        queue->front = (queue->front + 1) % MAXSIZE;
        outData = queue->data[queue->front];
        printf("%d\n", outData);
    }
}

三、基础链表队列

#include <stdio.h>
#include <malloc.h>
/// <summary>
/// 链表队列: 先进先出，后进后出
/// 第一个元素无数据
/// 队列长度根据电脑内存为准
/// 
/// 队空：queue->front == queue->rear
/// 队满：p == NULL
/// </summary>
typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode,*QueuePtr;
typedef struct
{
	QueuePtr front, rear;
}LinkQueue;

int main()
{
	int inData = 100;
	int outData = 0;
	// 定义队列
	LinkQueue* queue;
	// 定义节点
	QNode* node;
	// 队列<头指针>申请内存
	queue = (LinkQueue*)malloc(sizeof(LinkQueue));
	// 队列<头节点>申请内存
	node = (QNode*)malloc(sizeof(QNode));
	
	// 队列初始化
	node->next = NULL;
	// 头尾指针指向第一个节点
	queue->front = queue->rear = node;

	//--------------------------------------------------------
	#pragma region 入队
	QNode* p;
	//创建新节点
	p = (QNode*)malloc(sizeof(QNode));
	if (p == NULL)
	{
		printf("电脑内存不足，申请失败\n");
	}
	p->data = inData;
	p->next = NULL;
	// 新节点 入队
	queue->rear->next = p;
	// 队列尾指针指向 新节点
	queue->rear = p;
	#pragma endregion

	//--------------------------------------------------------
	#pragma region 出队
	QNode* ptr;
	if (queue->front == queue->rear)
	{
		printf("队列已空\n");
	}
	else
	{
		// 获取头指针的数据
		ptr = queue->front->next;
		outData = ptr->data;
		printf("outData: %d\n", outData);
		// 出队
		queue->front->next = ptr->next;
		// 最后一个元素出队
		if (ptr->next == NULL)
		{
			queue->rear = queue->front;
		}
		// 释放空间
		free(ptr);
	}
	#pragma endregion	
}  

四、数组队列 -- 函数

ArrayQueue.h

#ifndef __ARRAYQUEUE_H__
#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 100
typedef int DataType;

typedef struct
{
	DataType data[MAXSIZE];
	int front;
	int rear;
}SqQueue;

SqQueue* InitQueue(void);
int QueueIsEmpty(SqQueue* queue);
int QueueIsFull(SqQueue* queue);
int QueueLength(SqQueue* queue);
int QueueGetHead(SqQueue* queue, DataType* e);
int EnQueue(SqQueue* queue, DataType e);
int DeQueue(SqQueue* queue, DataType* e);
int QueueTraverse(SqQueue* queue);
#endif // !__ARRAYQUEUE_H__

ArrayQueue.c

#include "ArrayQueue.h"

/// <summary>
/// 队列初始化
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
SqQueue* InitQueue(void)
{
	SqQueue* queue;
	queue = (SqQueue*)malloc(sizeof(SqQueue));
	queue->front = queue->rear = 0;
	return queue;
}

/// <summary>
/// 判断队列是否为空
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
int QueueIsEmpty(SqQueue* queue)
{
	return queue->front == queue->rear ? 1 : 0;
}

/// <summary>
/// 判断队列是否已满
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
int QueueIsFull(SqQueue* queue)
{
	return queue->front == (queue->rear+1)%MAXSIZE ? 1 : 0;
}

/// <summary>
/// 获取队列当前长度
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
int QueueLength(SqQueue* queue)
{
	// +MAXSIZE -- 防止为负数的情况
	return (queue->rear - queue->front + MAXSIZE) % MAXSIZE;
}

/// <summary>
/// 获取当前头节点的数据
/// </summary>
/// <param name="queue"></param>
/// <param name="e"></param>
/// <returns></returns>
int QueueGetHead(SqQueue* queue, DataType* e)
{	
	// 若队列为空
	if (QueueIsEmpty(queue))
	{
		// 失败
		return 0;
	}
	// 获取首节点数据
	*e = queue->data[queue->front];
	// 成功
	return 1;
}

/// <summary>
/// 入队
/// </summary>
/// <param name="queue"></param>
/// <param name="e"></param>
/// <returns></returns>
int EnQueue(SqQueue* queue, DataType e)
{
	// 若队列已满
	if (QueueIsFull(queue))
	{
		return 0;
	}
	// 队列添加数据
	queue->data[queue->rear] = e;
	// 队列尾指针后移
	queue->rear = (queue->rear + 1) % MAXSIZE;
	return 1;
}

/// <summary>
/// 出队
/// </summary>
/// <param name="queue"></param>
/// <param name="e"></param>
/// <returns></returns>
int DeQueue(SqQueue* queue, DataType* e)
{
	// 若队列为空
	if (QueueIsEmpty(queue))
	{
		return 0;
	}
	// 获取头数据
	*e = queue->data[queue->front];
	// 头指针后移
	queue->front = (queue->front + 1) % MAXSIZE;
	return 1;
}

/// <summary>
/// 队列遍历
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
int QueueTraverse(SqQueue* queue)
{
	int i;
	// 若队列为空
	if (QueueIsEmpty(queue))
	{
		return 0;
	}
	i = queue->front;
	while (i != queue->rear)
	{
		printf("%d ", queue->data[i]);
		i = (i + 1) % MAXSIZE;
	}
	printf("\n");
	return 1;
}

main.c 

#include <stdio.h>
#include "ArrayQueue.h"

int main()
{
	SqQueue* queue;
	DataType result;

	// 队列初始化
	queue = InitQueue();	

	// 入队
	EnQueue(queue, 100);
	EnQueue(queue, 200);
	
	// 获取首元素
	QueueGetHead(queue, &result);
	printf("%d\n", result);

	// 获取队列长度
	result = QueueLength(queue);
	printf("%d\n", result);

	// 队列遍历
	QueueTraverse(queue);

	// 出队
	DeQueue(queue, &result);
	printf("%d\n", result);
}

五、链表队列 -- 函数

LinkQueue.h

#ifndef __LINKQUEUE_H__
#include <stdio.h>
#include <malloc.h>

typedef int DataType;

typedef struct QNode
{
	DataType data;
	struct QNode* next;
}QNode;
typedef struct
{
	QNode *front, *rear;
}SqQueue;

SqQueue* InitQueue(void);
int QueueIsEmpty(SqQueue* queue);
int QueueLength(SqQueue* queue);
int QueueGetHead(SqQueue* queue, DataType* e);
int EnQueue(SqQueue* queue, DataType e);
int HeadEnQueue(SqQueue* queue, DataType e);
int DeQueue(SqQueue* queue, DataType* e);
int QueueTraverse(SqQueue* queue);
#endif // !__LINKQUEUE_H__

LinkQueue.c 

#include "LinkQueue.h"

/// <summary>
/// 队列初始化
/// </summary>
/// <returns></returns>
SqQueue* InitQueue(void)
{
	SqQueue* queue;
	QNode* node;
	
	queue = (SqQueue*)malloc(sizeof(SqQueue));
	node = (QNode*)malloc(sizeof(QNode));

	node->next = NULL;
	// 头尾指针指向第一个节点
	queue->front = queue->rear = node;
	
	return queue;
}

/// <summary>
/// 判断队列是否为空
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
int QueueIsEmpty(SqQueue* queue)
{
	return queue->front == queue->rear ? 1 : 0;
}

/// <summary>
/// 获取队列元素的个数
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
int QueueLength(SqQueue* queue)
{
	QNode* p;
	int i = 0;
	p = queue->front;
	while (p != queue->rear)
	{
		i++;
		p = p->next;
	}
	return i;
}

/// <summary>
/// 获取首个元素
/// </summary>
/// <param name="queue"></param>
/// <param name="e"></param>
/// <returns></returns>
int QueueGetHead(SqQueue* queue, DataType* e)
{
	*e = queue->front->next->data;
	return 1;
}

/// <summary>
/// 入队
/// </summary>
/// <param name="queue"></param>
/// <param name="e"></param>
/// <returns></returns>
int EnQueue(SqQueue* queue, DataType e)
{
	QNode* p;
	p = (QNode*)malloc(sizeof(QNode));
	// 若电脑内存不足
	if (p == NULL)
	{
		return 0;
	}
	// 数据添加
	int a = sizeof(p->data) / sizeof(DataType);
	p->data = e;
	p->next = NULL;
	// 新节点 --  连接
	queue->rear->next = p;
	// 尾指针后移
	queue->rear = p;

	return 1;
}

/// <summary>
/// 队列头插入
/// </summary>
/// <param name="queue"></param>
/// <param name="e"></param>
/// <returns></returns>
int HeadEnQueue(SqQueue* queue, DataType e)
{
	QNode* p;
	p = (QNode*)malloc(sizeof(QNode));
	// 若电脑内存不足
	if (p == NULL)
	{
		return 0;
	}
	// 数据添加
	p->data = e;
	// 新节点 -- 连接
	p->next = queue->front->next;
	// 头指针前移
	queue->front->next = p;

	return 1;
}

/// <summary>
/// 出队
/// </summary>
/// <param name="queue"></param>
/// <param name="e"></param>
/// <returns></returns>
int DeQueue(SqQueue* queue, DataType* e)
{
	QNode* p;
	// 若队列为空
	if (QueueIsEmpty(queue))
	{
		return 0;
	}
	// 获取头节点
	p = queue->front->next;
	// 获取数据
	*e = p->data;
	// 出队
	queue->front->next = p->next;
	// 若是最后一个节点
	if (p->next == NULL)
	{
		queue->rear = queue->front;
	}
	// 节点释放
	free(p);
	return 1;
}

/// <summary>
/// 队列遍历
/// </summary>
/// <param name="queue"></param>
/// <returns></returns>
int QueueTraverse(SqQueue* queue)
{
	// 获取第一个节点
	QNode* p = queue->front->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		// 指针后移
		p = p->next;
	}
	printf("\n");
	return 1;
}

 main.c

#include <stdio.h>
#include "LinkQueue.h"

int main()
{
	SqQueue* queue;
	DataType result;

	// 队列创建
	queue = InitQueue();

	// 入队
	EnQueue(queue, 100);
	HeadEnQueue(queue, 200);
	HeadEnQueue(queue, 300);

	// 队列遍历
	QueueTraverse(queue);

	// 队列元素个数
	result = QueueLength(queue);
	printf("%d \n", result);
	
	// 获取队列首元素
	QueueGetHead(queue, &result);
	printf("%d \n", result);

	// 出队
	DeQueue(queue, &result);
	printf("%d \n", result);
	DeQueue(queue, &result);
	printf("%d \n", result);
}

如有错误，烦请批评指正