#yyds干货盘点#算法开启小码农队列血脉
队列队列的概念及结构
队列：只允许在==一端进行插入==数据操作，在==另一端进行删除==数据操作的特殊线性表，队列具有==先进先出==FIFO(First In First Out)
入队列：进行==插入==操作的一端称为==队尾==
出队列：进行==删除==操作的一端称为==队头==
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据（就会挪动数据），效率会比较低
代码模块
队列节点
typedef int QDatatype;
typedef struct QueueNode
{
QDatatype data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;队列初始化函数QueueInit
//队列初始化函数
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}对列销毁函数QueueDestroy
//队列销毁函数
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur != NULL)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}入队函数QueuePush
//入队函数
void QueuePush(Queue* pq, QDatatype x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
if (!pq->head)
pq->head = pq->tail = newnode;
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}出队函数QueuePop
//出队函数
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (!next)
pq->tail = NULL;
}队列判空函数QueueErase
//队列判空函数
bool QueueErase(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
取队头函数QueueFront
//取队头函数
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueErase(pq));
return pq->head->data;
}取队尾函数QueueBack
//取对尾函数
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueErase(pq));
return pq->tail->data;
}取队长函数QueueSize
//队列长度函数
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}测试
void test1()
{
Queue q;
//把队列结构体指针给过去，队列里的东西随便改
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePop(&q);
QueuePush(&q, 3);
QueuePush(&q, 4);
//遍历队列
while (!QueueErase(&q))
{
printf("%d ",QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
代码
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDatatype;
typedef struct QueueNode
{
QDatatype data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
//队列初始化函数
extern void QueueInit(Queue* pq);
//队列销毁函数
extern void QueueDestroy(Queue* pq);
//入队函数
extern void QueuePush(Queue* pq, QDatatype x);
//出队函数
extern void QueuePush(Queue* pq);
//取对头函数
extern QDatatype QueueFront(Queue* pq);
//取对尾函数
extern QDatatype QueueBack(Queue* pq);
//队列长度函数
extern int QueueSize(Queue* pq);
//队列判空函数
extern bool QueueErase(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//队列初始化函数
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
//队列销毁函数
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur != NULL)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
//入队函数
void QueuePush(Queue* pq, QDatatype x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
if (!pq->head)
pq->head = pq->tail = newnode;
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//出队函数
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (!next)
pq->tail = NULL;
}
//取队头函数
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueErase(pq));
return pq->head->data;
}
//取对尾函数
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueErase(pq));
return pq->tail->data;
}
//队列长度函数
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}
//队列判空函数
bool QueueErase(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void test1()
{
Queue q;
//把队列结构体指针给过去，队列里的东西随便改
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePop(&q);
QueuePush(&q, 3);
QueuePush(&q, 4);
//遍历队列
while (!QueueErase(&q))
{
printf("%d ",QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
test1();
return 0;
}
https://blog.51cto.com/u_15443484/4842500
页:
[1]