长春比较有名的做网站建设,珠海网站建设建站系统,中关村在线报价大全,建设手机网站包括哪些费用吗目录
概念
队列的实现
利用结构体存放队列结构
为什么单链表不使用这种方法#xff1f;
初始化队列
小提示#xff1a;
队尾入队列
队头出队列
获取队头元素
获取队尾元素
获取队列中有效元素个数
检测队列是否为空
销毁队列
最终代码
循环队列
队列的OJ题 …目录
概念
队列的实现
利用结构体存放队列结构
为什么单链表不使用这种方法
初始化队列
小提示
队尾入队列
队头出队列
获取队头元素
获取队尾元素
获取队列中有效元素个数
检测队列是否为空
销毁队列
最终代码
循环队列
队列的OJ题
用队列实现栈
用栈实现队列 概念
只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 的特性进行插入操作的一端称为队尾进行删除操作的一端称为队头 队列的实现 tip队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 利用结构体存放队列结构 我们之前在实现单链表的时候使用到了二级指针来达到修改头尾结点的效果这样会增加代码复杂性和理解难度......
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h//链式结构表示队列
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//队列的结构使用结构体避免了二级指针的使用
typedef struct Queue
{QNode* phead;QNode* ptail;int size; //存放队列大小
}Queue;现在我们依然选择用单链表实现队列但是我们将指向链表的头尾结点的指针信息都存放在一个结构体中这样就起到了简化参数传递的作用。即在初始化队列时只需分配一个包含头尾节点、队列大小等信息的结构对象并将其作为参数传递给相关函数。这样就可以直接通过访问该结构对象中的相应成员变量来修改或获取所需信息
为什么单链表不使用这种方法 这是因为在单链表中使用结构体来表示整个单链表可能会带来一些不必要的复杂性并且没有明显的好处相比于这种方法使用二级指针会有以下有点 1. 简化插入和删除操作由于插入或删除操作需要调整前后两个节点之间的连接关系而队列不需要考虑在指定位置插入的问题将头尾结点分别存放在结构体中可能需要更多额外处理步骤才能保持正确连接关系。 2. 节省内存空间如果每个节点都包含了头尾信息则会导致额外占用内存空间并且增加了维护数据一致性所需付出成本。 3. 降低复杂度通过仅保存对首元素即头部进行引用在大多数情况下足以满足对单链表进行各种操作所需求。这样可以简化代码逻辑并提高代码可读性与可维护性。 初始化队列
//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
实现步骤
1、利用断言检测队列指针的有效性
2、有效则将队列初始化为空队列即将指向队头元素和队尾元素的指针及队列元素个数都置为空
小提示
这个看不看都行
队尾入队列
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
实现步骤
1、利用断言检测队列指针的有效性
2、malloc申请新的结点空间并进行开辟失败的判断
3、若开辟成功则向链表结点中插入有效数据以及下一个结点的置空
4、检测队列是否为空若为空则将新申请的结点作为队列的第一个元素令指向队头和队尾的指针指向该元素
5、若不为空则将指向队尾元素的指针指向新元素同时将指向队尾的指针向后移动指向该元素
6、完成一次队尾入队操作后将队列元素个数加一
队头出队列
// 对头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}实现步骤
1、利用断言检测队列指针的有效性
2、利用断言检测队列头元素不为空
3、利用临时指针变量删除队头结点并将指向队头结点指针向后移动最后释放该指针并置空
4、队头元素出队列后若头指针变为空则将尾指针也变为空
获取队头元素
//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);// assert(pq-phead);return pq-phead-val;
}
实现步骤
1、利用断言检测队列指针的有效性
2、利用断言检测队列头元素不为空
3、返回此时队头元素的值
获取队尾元素
//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);// assert(pq-phead);return pq-phead-val;
}
实现步骤
1、利用断言检测队列指针的有效性
2、利用断言检测队列头元素不为空
3、返回此时队尾元素的值
获取队列中有效元素个数
//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
实现步骤
1、利用断言检测队列指针的有效性
2、返回结构体中的size值
检测队列是否为空
//检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}
实现步骤
1、利用断言检测队列指针的有效性
2、返回对pq-phead NULL的判断结果返回结果为真则队列为空为假则队列非空
销毁队列
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
实现步骤
1、利用断言检测队列指针的有效性
2、遍历每一个队头元素并销毁最后将头尾指针及队列元素数量均置为空
最终代码
Queue.h文件
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h//链式结构表示队列
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//队列的结构使用结构体避免了二级指针的使用
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}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);//检测队列是否为空
bool QueueEmpty(Queue* pq);//销毁队列
int QueueSize(Queue* pq);
Queue.c文件
#includeQueue.h//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}// 对头出队列
void QueuePop(Queue* pq)
{assert(pq);// assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);// assert(pq-phead);return pq-phead-val;
}//获取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);// assert(pq-ptail);return pq-ptail-val;
}//检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
test.c文件
#include Queue.hint main()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);printf(%d , QueueFront(q));QueuePop(q);printf(%d , QueueFront(q));QueuePop(q);QueuePush(q, 4);QueuePush(q, 5);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}QueueDestroy(q);return 0;
}
循环队列 概念循环队列是一种特殊的队列数据结构它通过使用固定大小的数组来实现。与普通队列不同的是在循环队列中当尾指针rear达到数组末尾时会从数组开头重新开始存储元素 优点充分利用出队操作后释放出来的空间避免频繁地移动元素 适用场景循环队列常用于需要高效处理连续输入输出流数据的场景如缓冲区、任务调度等 关于循环队列的实现放在下一篇文章......
队列的OJ题
用队列实现栈
225. 用队列实现栈 - 力扣LeetCode
具体解题思路如下
1、题目要求使用两个队列但队列的基本功能需要自己实现
2、利用栈的结构体存储两个队列的头尾指针及队列元素个数的信息
3、为队列申请结点空间并利用QueueInit函数初始化队列
4、 入栈时利用if判断谁为非空队列后将要入栈的元素尾插进非空队列中(QueueBack函数)出栈的大体过程如下图所示 5、出栈时为了将队列的最后一个元素先排出就需要让原来存储有效数据的队列的前N-1个元素放入空的队列中然后再将元队列中的最后一个元素排出两个队列的作用是来回切换的需要利用if语句判断队列的空与非空后在进行操作出栈的大体过程如下图所示 6、获取栈顶元素时只需要判断两个队列谁不为空将不为空的队列的队尾元素返回即可
7、判断栈是否为空时当两个队列均为空时栈才能为空所以需要用
8、销毁栈时、不仅要释放掉malloc申请的内存空间还要将两个队列一同销毁
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h//链式结构表示队列
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//队列的结构使用结构体避免了二级指针的使用
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}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);//检测队列是否为空
bool QueueEmpty(Queue* pq);//销毁队列
int QueueSize(Queue* pq);//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}// 对头出队列
void QueuePop(Queue* pq)
{assert(pq);// assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}//获取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}//检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}typedef struct {Queue q1;Queue q2;
} MyStack;//初始化栈
MyStack* myStackCreate() {//申请结点空间MyStack* pst (MyStack*)malloc(sizeof(MyStack));//取地址后就可以操作栈结构体中p1和p2中的内容QueueInit(pst-q1); //-的优先级大于QueueInit(pst-q2); //-的优先级大于return pst;
}//入栈
void myStackPush(MyStack* obj, int x) {//如果q1队列不为空则q1队列用于存放导出的数据if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}//如果q1队列为空则q2队列用于存放导出的数据else{QueuePush(obj-q2,x);}
}//出栈
int myStackPop(MyStack* obj) {//起始假设q1为空,q2不为空empty指针指向空队列noempty指向非空队列Queue* empty obj-q1;Queue* noempty obj-q2;//如果我们假设失败则证明q1不为空q2为空交换标志if(!QueueEmpty(obj-q1)){empty obj-q2;noempty obj-q1;}//然后将队列中的前N-1个元素导入空队列所以循环结束的条件就是队列中元素等于1(这个剩下的就是要出栈的元素)while(QueueSize(noempty) 1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}//将队列中前N-1个元素导出后剩余的就是要出栈的元素,将该元素存储进整型变量top中int top QueueFront(noempty);//存储完成后将该元素也进行出队列操作QueuePop(noempty);//最后返回要出栈的元素return top;
}//获取栈顶元素
int myStackTop(MyStack* obj) {//谁不为空就获取谁的队尾元素if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}//如果q1队列为空则q2队列用于存放导出的数据else{return QueueBack(obj-q2);}
}//判断栈是否为空
bool myStackEmpty(MyStack* obj) {//只有当两个队列均为空的时候该栈才不会有有效数据return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}//销毁栈
void myStackFree(MyStack* obj) {//初始化时除了malloc了一个结点还初始化了两个队列所以除了要将申请的结点释放还要将申请的两个队列销毁QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}关于pst-q1的解释 为了操作队列我们在初始化栈时需要将队列对象作为参数传递给函数即pst-q1它表示获取指针 pst 所指向的结构体中成员变量 q1 的地址可以理解为队列q1的地址而pst是一个指向MyStack结构体的指针所以说就是获取MyStack结构体中成员变量的地址。 用栈实现队列
232. 用栈实现队列 - 力扣LeetCode 具体解题思路如下
1、题目要求使用两个栈但栈的基本功能需要自己实现
2、利用栈的结构体存储两个队列的头尾指针及队列元素个数的信息
3、为栈申请结点空间并利用STInit函数初始化栈
4、入队时直接利用STPush函数进行入栈即可
5、先返回队头元素然后再出队先判断用于出数据的popst栈是否为空如果为空则将pushst栈中的数据倒顺序后放入popst栈中利用STPush函数将pushst栈的栈顶元素放入空的popst栈中
6、出队时用临时变量front接收返回的队头元素然后利用STPop函数将该元素出队最后返回该元素的值
7、判断队列是否为空时当两个栈均为空时队列才能为空所以需要用
8、销毁栈时、不仅要释放掉malloc申请的内存空间还要将两个栈一同销毁
#include stdio.h
#include assert.h
#include stdlib.h//支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; //表示栈顶位置int capacity; //栈的容量
}ST;// 初始化栈
void STInit(ST* ps);// 销毁栈
void STDestroy(ST* ps);// 入栈
void STPush(ST* ps, STDataType data);// 出栈
void STPop(ST* ps);// 获取栈顶元素
STDataType STTop(ST* ps);// 获取栈中有效元素个数
int STSize(ST* ps);// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int STEmpty(ST* ps);// 初始化栈
void STInit(ST* pst)
{//首先要指向一个栈assert(pst);pst-a NULL;pst-capacity 0;pst-top 0; //令pop表示栈顶元素的下一个元素的下标
}// 销毁栈
void STDestroy(ST* pst)
{//首先要指向一个栈assert(pst);//正常操作不再过多复述free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}//入栈
void STPush(ST* pst, STDataType x)
{//首先要指向一个栈assert(pst);//判断栈是否已满如果栈满则申请新的内存空间if (pst-top pst-capacity){int newCapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newCapacity;}//如果栈未满则进行入栈操作若初始化时pop-1则下面两行代码交换执行顺序pst-a[pst-top] x; //此时pop表示的是栈顶元素的下一个元素的下标 pst-top; //top表示的下标数
}//出栈
void STPop(ST* pst)
{//首先要指向一个栈assert(pst);//top0表示栈为空top0表示没有元素入栈存在这两种情况就不能执行出栈操作可以提供的图理解assert(pst-top 0);//直接对top执行减减操作以获取实际数组元素下标pst-top--;
}// 获取栈顶元素
STDataType STTop(ST* pst)
{//首先要指向一个栈assert(pst);//top0表示栈为空top0表示没有元素入栈存在这两种情况就不能执行出栈操作可以提供的图理解assert(pst-top 0);//当初始化top0时top的值与实际数组元素下标的值之间的关系是实际下标 top-1//所以这里要进行减一操作得到实际的数组元素下标后再输出return pst-a[pst-top - 1];
}//获取栈中有效元素个数
int STSize(ST* pst)
{//首先要指向一个栈assert(pst);//初始化top0则top等于多少栈中就有多少个元素return pst-top;
}//检测栈是否为空如果为空返回非零结果如果不为空返回0
int STEmpty(ST* pst)
{//首先要指向一个栈assert(pst);//如果pst-top不为空则返回结果为真为空则返回假return pst-top NULL;
}typedef struct {ST pushst;ST popst;
} MyQueue;//初始化栈
MyQueue* myQueueCreate() {MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}//入队
void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst,x);
}//出队
int myQueuePop(MyQueue* obj) {int front myQueuePeek(obj);STPop(obj-popst);return front;
}//返回队头元素
int myQueuePeek(MyQueue* obj) {//栈不为空就倒数据if(STEmpty(obj-popst)){//将pusust里面的数据倒转顺序后传递给popstwhile(!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}//判断是否为空
bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-popst) STEmpty(obj-pushst);
}//销毁队
void myQueueFree(MyQueue* obj) {STDestroy(obj-popst);STDestroy(obj-pushst);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj myQueueCreate();* myQueuePush(obj, x);* int param_2 myQueuePop(obj);* int param_3 myQueuePeek(obj);* bool param_4 myQueueEmpty(obj);* myQueueFree(obj);
*/
关于pst-pushst和pst-popst的解释 ~over~
