1.结构体设计
结构说明：使用单链表作为基础的数据结构 链表结点存储数据和下一个结点地址
但是队列要可以访问队头和队尾 函数需要传两个指针参数 所以单独设计一个结构体存储这两个结点指针front和rear
再创建一个size记录队列结点个数
typedef int QueueNodeDataType;
typedef struct QListNode
{
struct QListNode* _pNext;
QueueNodeDataType _data;
}QNode;
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int _size;
}Queue;
2.功能设计
2.1 初始化： 将队列的front和rear都置为空 队列内有效元素置为0
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->_size = 0;
}
2.2 插入元素设计 队尾入队列：判断front为不为空
1.为空则说明front和rear都要置为newNode
2.不为空则说明只需要改变rear即可 申请新节点链接到链表中 改变rear
void QueuePush(Queue* q, QueueNodeDataType val)
{
assert(q);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
assert(newNode);
newNode->_data = val;
newNode->_pNext = NULL;
if (q->_front == NULL)//队列没有结点
{
q->_front = q->_rear = newNode;
}
else
{
q->_rear->_pNext = newNode;
q->_rear = newNode;
}
q->_size++;
}
2.3 队头出队列：
判断队列为不为空 为空则返回 不为空分两种情况
1.只有一个结点 将front和rear都置为NULL
2.多个结点 只将front指向它的下一个结点即可
void QueuePop(Queue* q)
{
assert(q);
if (q->_front == NULL)
{
return;
}
else
{
if (q->_front == q->_rear)//说明只有一个结点
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* cur = q->_front->_pNext;
free(q->_front);
q->_front = cur;
}
}
q->_size--;
}
2.4 判空：为空返回true 不为空返回false
bool QueueEmpty(Queue* q)
{
assert(q);
return q->_front == NULL;
}
2.5 取队列头元素和取队列尾部元素：判断队列为空的情况
QueueNodeDataType QueueFront(Queue* q)
{
assert(q);
assert(q->_front);
return q->_front->_data;
}
QueueNodeDataType Queuerear(Queue* q)
{
assert(q);
assert(q->_rear);
return q->_rear->_data;
}
2.6 返回队列有效元素个数：返回size
int QueueSize(Queue* q)
{
assert(q);
return q->_size;
}
2.7 销毁队列：遍历队列 销毁结点
void QueueDestory(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur)
{
QNode* tmp = cur;
cur = cur->_pNext;
free(tmp);
}
q->_front = q->_rear = NULL;
}
整体代码
Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<stdbool.h>
typedef int QueueNodeDataType;
typedef struct QListNode
{
struct QListNode* _pNext;
QueueNodeDataType _data;
}QNode;
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int _size;
}Queue;
void QueueInit(Queue* q);
void QueuePush(Queue* q, QueueNodeDataType val);
void QueuePop(Queue* q);
bool QueueEmpty(Queue* q);
int QueueSize(Queue* q);
QueueNodeDataType QueueFront(Queue* q);
QueueNodeDataType Queuerear(Queue* q);
void QueueDestory(Queue* q);
Queue.c
#include"queue.h"
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->_size = 0;
}
void QueuePush(Queue* q, QueueNodeDataType val)
{
assert(q);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
assert(newNode);
newNode->_data = val;
newNode->_pNext = NULL;
if (q->_front == NULL)//队列没有结点
{
|
楼主
标题置顶
标题高亮
