建设旅游网站的目的和意义,学电脑培训多少钱,制作一个网页需要哪几个步骤,手机网站建设价格表一、队列的概念
队列是一种特殊的线性表#xff0c;特殊之处在于它只允许在表的前端#xff08;front#xff09;进行删除操作#xff0c;而在表的后端#xff08;rear#xff09;进行插入操作#xff0c;和栈一样#xff0c;队列是一种操作受限制的线性表。进行插入操…一、队列的概念
队列是一种特殊的线性表特殊之处在于它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作和栈一样队列是一种操作受限制的线性表。进行插入操作的端称为队尾进行删除操作的端称为队头。
二、模拟实现顺序队列 我们可以用单链表模拟实现顺序队列。
队列采用的FIFO(first in first out)新元素等待进入队列的元素总是被插入到链表的尾部对应单链表的尾插而读取的时候总是从链表的头部开始读取。每次读取一个元素释放一个元素对应单链表的头删。
对应的接口
注意又提供一种避免使用二级指针的方法创建一个结构体变量里面存储结点当我们想要改变结构体里面的值我们就用一级指针即可。
typedef int QDataType;
typedef struct QueueNode
{//用单链表模拟实现队列struct QueueNode* next;QDataType data;
}QNode;//新的避免二级指针的结构体
typedef struct Queue
{QNode* head;QNode* tail;int sz;
}Que;void QueueInit(Que* pq);
void QueueDestory(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueeuPop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);队列的初始化
void QueueInit(Que* pq)
{assert(pq);pq-sz 0;pq-head pq-tail NULL;
}
队列的销毁
注意free过后也要指向空
void QueueDestroy(Que* pq)
{assert(pq);while (pq-sz 0){QNode* cur pq-head-next;free(pq-head);pq-head cur;pq-sz--;}pq-tail pq-head NULL;
}队列的插入数据
也就是单链表的尾插同时也要注意当队列为空时的特殊情况。
void QueuePush(Que* pq,QDataType x)
{//类似于尾插assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next NULL;if (pq-head NULL){pq-head pq-tail newnode;pq-sz;}else{pq-sz;pq-tail-next newnode;pq-tail newnode;}
}
队列的删除数据
也就是单链表的头删同时也要注意只剩下一个结点删除后尾结点指向空的情况 void QueeuPop(Que* pq)
{assert(pq);assert(pq-sz 0);//头删//单独判断只剩下一个结点头删后tail是野指针的情况if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;pq-sz--;}else{QNode* cur pq-head;pq-head pq-head-next;free(cur);pq-sz--;}}
返回队列头数据
QDataType QueueFront(Que* pq)
{assert(pq);//assert(pq-head);assert(!QueueEmpty(pq));return pq-head-data;
}
返回队列尾数据
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
判断队列是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}
返回队列的数据个数
int QueueSize(Que* pq)
{assert(pq);//assert(pq-head);return pq-sz;
}三、模拟实现循环队列
622. 设计循环队列 - 力扣LeetCode
这实际上是把队列空间想象成一个环形空间环形空间中的存储单元循环使用用这种方法管理的队列也就称为循环队列。
注意本题结构较为复杂必须要画图进行解决这样就容易考虑到特殊情况不容易出错。
本题用数组实现较为简单如果用单链表实现那么rear尾结点的前一个不好寻找。
那数组如何实现循环呢
数组实现循环并不像单链表那样有一个next指针指向头结点如果已经走向尾部可以直接让头部的值等于尾部想要的值。
//如何用数组实现循环
typedef struct {int* a;int front;int rear;int num;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cur (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//用k1个数组空间便于判断空和满的情况。cur-a (int*)malloc(sizeof(int)*(k1));cur-front 0;cur-rear 0;cur-num k;return cur;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-front obj-rear)return true;elsereturn false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//两种情况都要考虑到if(obj-front-obj-rear 1 || obj-rear-obj-front obj-num)return true;elsereturn false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判断是否已经满if(myCircularQueueIsFull(obj) true)return false;//假设rear在队列的尾部if(obj-rear obj-num){obj-a[obj-rear] value;obj-rear 0;}else{obj-a[obj-rear] value;obj-rear;}//obj-a[obj-rear] value;//obj-rear;//obj-rear % (obj-num1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//先判断是否已经空了if(myCircularQueueIsEmpty(obj) true){return false;}//假设front在队列的尾部if(obj-front obj-num)obj-front 0;elseobj-front;//obj-front;//obj-front % (obj-num1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj) true)return -1;elsereturn obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {//注意队尾的rear比数据提前一位数所以是rear-1//但要考虑rear-1的情况if(myCircularQueueIsEmpty(obj) true)return -1;if(obj-rear 0){//需要再创建一个临时变量不能改变rear的值int tmp obj-num;return obj-a[tmp];}// else// return obj-a[(obj-rearobj-num)%(obj-num1)];return obj-a[obj-rear-1];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
四、用队列实现栈
225. 用队列实现栈 - 力扣LeetCode
本题要求用两个队列实现栈两个队列我们就可以互相倒数据来满足题目对栈的需求
思路
入队列
入不为空的队列
出队列
利用队列的性质将前n-1个数据放入另一个空的队列中删除剩下一个数据这样就完成栈的pop操作 代码
typedef struct {Que q1;Que q2;
} MyStack;MyStack* myStackCreate() {MyStack* cur (MyStack*)malloc(sizeof(MyStack));//不能忘记初始化QueueInit(cur-q1);QueueInit(cur-q2);return cur;
}void myStackPush(MyStack* obj, int x) {//push到不为空的的队列中if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}int myStackPop(MyStack* obj) {//先假设q1不为空q2为空Que* empty obj-q1;Que* nonEmpty obj-q2;if(!QueueEmpty(obj-q1)){//如果假设失败相反empty obj-q2;nonEmpty obj-q1;}while(QueueSize(nonEmpty)1){//开始用函数进行捯数据//从前往后的顺序是根据队列pop的顺序定的QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top QueueBack(nonEmpty);QueuePop(nonEmpty);return top;
}int myStackTop(MyStack* obj) {Que* empty obj-q1;Que* nonEmpty obj-q2;if(!QueueEmpty(obj-q1)){//如果假设失败相反empty obj-q2;nonEmpty obj-q1;}return QueueBack(nonEmpty);
}bool myStackEmpty(MyStack* obj) {//判断两个队列return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}void myStackFree(MyStack* obj) {//先对两个队列中的链表进行freeQueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}
五、用栈实现队列
232. 用栈实现队列 - 力扣LeetCode
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
思路
本题与上一题用队列实现栈有所差别可以直接区分push栈和pop栈如果pop栈为空就将push栈全部捯到pop栈
代码
typedef struct
{ST push;ST pop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* cur (MyQueue*)malloc(sizeof(MyQueue));SLInit(cur-push);SLInit(cur-pop);return cur;
}void myQueuePush(MyQueue* obj, int x) {STPush(obj-push,x);
}int myQueuePop(MyQueue* obj) {int ret myQueuePeek(obj);STPop(obj-pop);return ret;
}int myQueuePeek(MyQueue* obj) {//出栈只能从后往前出//如果pop栈为空就将push栈全部捯到pop栈if(STEmpty(obj-pop)){while(!STEmpty(obj-push)){STPush(obj-pop,STTop(obj-push));STPop(obj-push);}}int ret STTop(obj-pop);return ret;
}bool myQueueEmpty(MyQueue* obj) {//用函数求解return STEmpty(obj-push) STEmpty(obj-pop);
}void myQueueFree(MyQueue* obj) {SLDestroy(obj-pop);SLDestroy(obj-push);free(obj);
}
