数据结构 Queue 队列 -- C语言实现
队列
队列的概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特点FIFO(First In First Out)
- 入队:进行插入操作的一端称为队尾
- 出队:进行删除操作的一端称为队头
链实栈代码实现
Ququq.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode *next;
QDataType data;
}QNode;
//控制变量结构体
//只有一个值,就不用定义结构体,有多个就定义结构题。
typedef struct Queue
{
struct QueueNode *head; //队头,出队,头删
struct QueueNode *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 * next = NULL;
QNode *cur = pq->head;
while (cur)
{
next = pq->head->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)
{
perror("malloc fail ");
exit(-1);
}
//先初始化再使用
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));
if (pq->head->next == NULL)//只有一个节点
{
free(pq->head);//先释放
pq->tail = pq->head = NULL;//后置空 :tail 和 head都得置空,不然下次就插不进了 ---为什么要置空,因为push需要NULL识别空队列插入
}
else
{
QNode *next = pq->head->next;//记住下一个
free(pq->head);//释放头节点
pq->head = next;//下个节点成为新节点
}
}
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);
QNode *cur = pq->head;
int size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
bool QueueEmpty(Queue *pq)
{
assert(pq);
//return QueueSize(pq) == 0;
return pq->head == NULL ;//只要有一个就可以了
//head为空tail也为空
}
本文来自博客园,作者:HJfjfK,原文链接:https://www.cnblogs.com/DSCL-ing/p/18344045