你好，这里是新人 Sunfor

这篇是我最近对于数据结构 队列的学习心得和错题整理
有任何错误欢迎指正，欢迎交流！
会持续更新，希望对你有所帮助，我们一起学习，一起进步

前言

队列的定义

队列的概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出的特性
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

队列的基本操作

• enqueue(入队)：将元素添加到队列的尾部
• dequeue(出队)：移除并返回队列头部的元素
• peek(查看队头元素)：返回队列头部的元素，但不移除它
• QEmpty(检查队列是否为空)：判断队列中是否还有元素
• QSize(获取队列的大小) : 返回队列中当前的元素的个数

队列用C语言实现

类比于我们之前实现顺序表,单链表,双链表,栈，队列的实现同样是多文件操作

• Queue.h:主要存放代码实现过程中需要的头文件,同时充当目录
• Queue.c:函数的具体功能的实现
• text.c:测试函数的功能,包含主函数

Queue.h

#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* phead;//队头QueueNode* ptail;//队尾int size;//保存队列有效数据个数
}Queue;//队列的初始化
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq,QDataType x);//判空
bool QueueEmpty(Queue* pq);//出队列
void QueuePop(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataTypr QueueBack(Queue* pq);//队列有效数据个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列
void QueuePush(Queue* pq,QDataType x)
{assert(pq);//申请新结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if(newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL; if(pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->tail = pq->ptail->next;//newnode}pq->size++;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty);//只有一个结点的情况if(pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//删除队头结点QueueNode* Next = pq->phead->next;free(pq->phead);pq->phead = Next;}--pq->size;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty);return pq->phead->data;
}//取队尾数据
QDataTypr QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty);return pq->ptail->data;
}//队列有效数据个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);assert(!QueueEmpty);QueueNode* pcur = pq->phead;while(pcur){QueueNode* Next = pcur->next;free(pcur);pcur = Next;}pq->phead = pq->ptial = NULL;pq->size = 0;
}

text.c

#include"Queue.h"void QueueTest01()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//printf("head:%d\n", QueueFront(&q));//printf("tail:%d\n", QueueBack(&q));printf("size:%d\n", QueueSize(&q));QueueDestroy(&q);
}int main()
{QueueTest01();return 0;
}

队列 VS 栈

队列的应用

1.用队列实现栈
题目要求：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：
必须保证至少有一个队列为空
出栈：找不为空的队列，将size-1个数据导入到另一个队列中
入栈：往不为空队列中插入数据
取栈顶元素：找不为空的队列，取队尾元素

#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* phead;QueueNode* ptail;int size;//保存队列有效数据个数
}Queue;void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请新节点QueueNode* newnode =(QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//ptail newnodeif (pq->phead == NULL){//队列为空pq->phead = pq->ptail = newnode;}else{//队列不为空pq->ptail->next = newnode;pq->ptail = pq->ptail->next;//newnode}pq->size++;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}// 出队列，队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点的情况，避免ptail变成野指针if (pq->ptail == pq->phead){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//删除队头元素、QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}/
typedef struct {//两个队列Queue q1;Queue q2;
} MyStack;//STInit
MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);//记得传的是地址QueueInit(&pst->q2);return pst;
}//入栈
void myStackPush(MyStack* obj, int x) {//往不为空的队列中插入数据if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}}//出栈
int myStackPop(MyStack* obj) {//找不为空的队列Queue* empQ = &obj->q1;//先假设q1为空Queue* noneQ = &obj->q2;//q2不为空if(!QueueEmpty(&obj->q1)){noneQ = &obj->q1;empQ = &obj->q2;}//将不为空队列中size-1个数据导入到空队列中while(QueueSize(noneQ) > 1){int front = QueueFront(noneQ);QueuePush(empQ,front);QueuePop(noneQ);}//非空队列现在只剩下一个数据---要出栈的数据int pop = QueueFront(noneQ);QueuePop(noneQ);return pop;
}//取栈顶元素---取非空队列中的队尾元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}//STDestroy
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;
}