做暖暖视频网站大全,金牛区建设审批网站,wordpress讨论吧,wordpress参考文献不是你变优秀了, 那个人就会喜欢你. 文章索引 前言1. 什么是队列2. 队列的实现3. OJ题目解析4. 总结 前言
感情可以培养是个伪命题. 如果有足够多的时间和爱, 就可以让另一个人爱上你的话, 那谁和谁都可以相爱了. 爱情之所以会让人死去活来, 是因为, 答案都写在了…不是你变优秀了, 那个人就会喜欢你. 文章索引 前言1. 什么是队列2. 队列的实现3. OJ题目解析4. 总结 前言
感情可以培养是个伪命题. 如果有足够多的时间和爱, 就可以让另一个人爱上你的话, 那谁和谁都可以相爱了. 爱情之所以会让人死去活来, 是因为, 答案都写在了彼此第一次见面的那天.
本文旨在介绍队列的实现方法以及OJ有关队列的题目分析
博客主页: 酷酷学!!!
期待更多好文 感谢关注~ 正文开始
1. 什么是队列
队列: 只允许一端进行插入数据操作, 在另一端进行删除操作的特殊线性表, 队列具有先进先出FIFO(First In First Out) 入队列: 进行插入操作的一端称为队尾 出队列: 进行删除操作的一端称为队头 2. 队列的实现
队列也可以使用数组和链表的结构实现, 使用链表的结构更优一些, 因为如果使用数组结构, 出队列在数组头上出数据, 效率会比较低.而链表在头删会比较友好.
故我们采用链表结构继续队列的实现 第一步:
首先进行文件的创建 然后在Queue.h文件中进行声明和定义 定义链表的节点,包含一个数据域和一个指针域, 因为我们需要使用链表来实现队列
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int DataType;typedef struct QueueNode
{struct QueueNode* next;DataType val;
}QNode;
以下是我们需要实现的队列的方法, 也声明在头文件中,在链表的实现中,我们传递了一个头指针,指向了这个链表, 但是对于队列, 我们定义两个指针,头指针和尾指针, 这样我们在进行头删和尾插时比较方便, 那为什么链表为什么不定义连个指针呢, 一是链表需要进行头插尾插, 头删尾删, 我们还需要找到尾节点的前一个节点, 解决不了根本问题, 干脆定义一个指针进行遍历查找, 那么回想, 想要改变链表的头指针, 我们需要传递头指针的地址, 也就是二级指针, 那么这里也一样, 我们是不是也要传递队列的头指针的地址和尾指针的地址呢? 答案是肯定, 但是麻烦, 有没有更好的办法呢? 队尾插入
//void QueuePush(QNode** pphead, QNode** pptail, QDataType x);队头删除
//void QueuePop(QNode** pphead, QNode** pptail);有,可以定义一个结构体, 让队列的头指针和尾指针都存放在结构体中, 这样我们想要改变头指针和尾指针也就变成了改变结构体的成员, 那么传递结构体指针, 进行实参的修改就可以完美解决, 如下, 当然这里我们增加一个size变量用来记录队列元素的个数, 以避免我们需要知道个数是进行O(N)时间复杂度的查找, 接下来的方法实现也会深有体会.
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);//队尾插入
void QueuePush(Queue* pq, DataType x);
//队头删除
void QueuePop(Queue* pq);//判空
bool QueueEmpty(Queue* pq);
//获取节点个数
int QueueSize(Queue* pq);//获取头节点
DataType QueueFront(Queue* pq);
//获取尾节点
DataType QueueTail(Queue* pq);第二步: 队列接口的实现:
初始化
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}这里我们来对比学习, 可以点击查看链表的实现链表(1) 我们进行链表的实现时, 直接就是头插操作, 为什么呢, 答案是实现链表我们只需要一个指针, 指向链表就可以了,我们直接在插入时进行初始化, 而队列不是, 队列有三个变量, 所以我们需要对他进行初始化操作, 头指针尾指针和size变量.
销毁
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;
}那么有了初始化, 必然少不了我们的销毁操作, 这里主要是针对我们动态开辟的节点, 我们需要手动释放, 不能让它内存泄漏, 当节点都释放完毕后, 需要让头指针和尾指针都置为NULL,规避野指针的出现, size也还原为0.
入队列
void QueuePush(Queue* pq, DataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail!);//perror函数在stdio.h头文件包含,标准错误流return;}newnode-next NULL;newnode-val x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}接下来进行入队列的操作,首先传递过来的结构体肯定不能是个空的, 你是个空的那我还怎么去访问我的头指针和尾指针, 切记NULL不能访问, 然后因为我们初始化的时候没有开辟节点, 所以我们在这里进行节点的开辟, 当然这个是灵活变动的, 使用malloc函数每次开辟一个节点, 那么如果尾指针指向的地方为NULL, 说明没有节点, 那么就让头指针和尾指针都指向第一个节点, 那么反之, 如果有节点的话, 我们只需要让尾指针的next指向这个节点, 并且让新节点成为尾指针.最后size.
注意: 这里不可以使用pq-tail pq-haed 来判断是否队列为NULL, 因为如果有一个节点, 或者队列已满它们两个仍然指向同一个节点
出队列
void QueuePop(Queue* pq)
{assert(pq!NULL);//条件为真,程序继续assert(pq-size!0); //条件为真,程序继续if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}这个出队列首先需要断言结构体不可以为NULL, 这里assert(pq)和assert(pq!NULL)表示的是一个意思,因为空就表示假, 非空就表示真, 这里写出来是便于理解,assert()断言表示, 条件为真则程序继续执行, 如果条件为假则程序中断 接着, 出队列,里面当然还需要有数据, 所以pq-size!0这个条件也必须为真. 如果只有一个节点的话不要忘记了把尾指针也置为NULL,否则尾指针会变成野指针, 如果有多个节点, 先保存下一个节点地址,然后在进行free.最后size–.
判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}这里有了size这个变量我们只需要判断size是否为0即可.
查看数据个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}直接返回size,因为size记录的就是数据的个数, 也规避了遍历查找元素个数.
返回头节点数据返回尾节点数据
DataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}DataType QueueTail(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}最后两个方法也非常简单, 只要存在, 我们直接返回所需节点的数据即可.
第三步:
测试,在test.c中测试我们的代码
#includeQueue.hint main()
{Queue pq;QueueInit(pq);QueuePush(pq, 2);QueuePush(pq, 3);printf(%d , QueueFront(pq));QueuePop(pq);printf(%d , QueueFront(pq));QueuePop(pq);QueueDestroy(pq);return 0;
}当然运行程序结构是没有问题的, 也可以循环出队列,进行测试代码
3. OJ题目解析
题目链接: 用队列实现栈
题目描述: 原始模板:
typedef struct {} MyStack;MyStack* myStackCreate() {}void myStackPush(MyStack* obj, int x) {}int myStackPop(MyStack* obj) {}int myStackTop(MyStack* obj) {}bool myStackEmpty(MyStack* obj) {}void myStackFree(MyStack* obj) {}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj myStackCreate();* myStackPush(obj, x);* int param_2 myStackPop(obj);* int param_3 myStackTop(obj);* bool param_4 myStackEmpty(obj);* myStackFree(obj);
*/思路分析:
首先这道题需要我们使用两个队列来完成栈的实现, 这里我们的思路是, 栈的要求是后进先出, 而队列是先进先出, 让两个队列来回导数据, 插入数据时, 插入到不为空的队列中, 如果需要出数据, 先让不为空的队列的前n-1个数据导入到为空的队列中, 然后在出数据, 此时正好就是最后一个数据, 也就是后入先出, 如图
例如, 数据入队列q1, q2为空, 都为空的情况下, 入哪个都行, 假设q1不为空, 然后让q2一直保持空.
出数据, 先把q1的前n-1个数据导入到q2拿到q1最后一个数据,并且pop掉. 以此类推,保存一个存数据, 一个为空, 入数据不为空的队列, 出数据通过空的导一下. 步骤如下
因为C语言没有自带的队列, 所以我们需要把我们实现的队列写进去, C会自带的队列.这里我们直接导入创建MyStack,里面需要两个队列, myStackCreate其实也就是我们的初始化, 这里不可以直接 MyStack s, 因为函数里面的创建的变量出了函数就被释放了 ,所以我们需要动态开辟空间. 分别进行初始化
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* s (MyStack*)malloc(sizeof(MyStack));QueueInit(s-q1);QueueInit(s-q2);return s;
}入栈, 哪个不为空, 我们就把元素插入到哪个队列, 这里我使用了假设法, 来找出不为空的队列.
void myStackPush(MyStack* obj, int x) {assert(obj);//假设法Queue* Empty obj-q1;Queue* nonEmpty obj-q2;if(QueueEmpty(obj-q2)){Empty obj-q2;nonEmpty obj-q1;}//把数据插入到不为空的队列QueuePush(nonEmpty,x);
}出栈, 还是假设法, 找到不为空的队列, 然后通过为空的队列导一下,不要忘记找到数据之后, 让最后一个数据出队列.
int myStackPop(MyStack* obj) {assert(obj);Queue* Empty obj-q1;Queue* nonEmpty obj-q2;if(QueueEmpty(obj-q2)){Empty obj-q2;nonEmpty obj-q1;}//把不为空的队列的数据的前n-1个数据导入到为空的队列while(QueueSize(nonEmpty)1){QueuePush(Empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top QueueTail(nonEmpty);QueuePop(nonEmpty);return top;
}剩下的几个方法总体来说比较简单, 代码如下,注意销毁操作, 我们手动开辟的空间都需要手动释放.
int myStackTop(MyStack* obj) {assert(obj);if(!QueueEmpty(obj-q1)){return QueueTail(obj-q1);}else{return QueueTail(obj-q2);}}bool myStackEmpty(MyStack* obj) {return (QueueEmpty(obj-q1)QueueEmpty(obj-q2));
}void myStackFree(MyStack* obj) {assert(obj);QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}全部代码如下:
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int DataType;typedef struct QueueNode
{struct QueueNode* next;DataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);//队尾插入
void QueuePush(Queue* pq, DataType x);
//队头删除
void QueuePop(Queue* pq);//判空
bool QueueEmpty(Queue* pq);
//获取节点个数
int QueueSize(Queue* pq);//获取头节点
DataType QueueFront(Queue* pq);
//获取尾节点
DataType QueueTail(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;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, DataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail!);//perror函数在stdio.h头文件包含,标准错误流return;}newnode-next NULL;newnode-val x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq!NULL);//条件为真,程序继续assert(pq-size!0); //条件为真,程序继续if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}DataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}DataType QueueTail(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* s (MyStack*)malloc(sizeof(MyStack));QueueInit(s-q1);QueueInit(s-q2);return s;
}void myStackPush(MyStack* obj, int x) {assert(obj);//假设法Queue* Empty obj-q1;Queue* nonEmpty obj-q2;if(QueueEmpty(obj-q2)){Empty obj-q2;nonEmpty obj-q1;}//把数据插入到不为空的队列QueuePush(nonEmpty,x);
}int myStackPop(MyStack* obj) {assert(obj);Queue* Empty obj-q1;Queue* nonEmpty obj-q2;if(QueueEmpty(obj-q2)){Empty obj-q2;nonEmpty obj-q1;}//把不为空的队列的数据的前n-1个数据导入到为空的队列while(QueueSize(nonEmpty)1){QueuePush(Empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top QueueTail(nonEmpty);QueuePop(nonEmpty);return top;
}int myStackTop(MyStack* obj) {assert(obj);if(!QueueEmpty(obj-q1)){return QueueTail(obj-q1);}else{return QueueTail(obj-q2);}}bool myStackEmpty(MyStack* obj) {return (QueueEmpty(obj-q1)QueueEmpty(obj-q2));
}void myStackFree(MyStack* obj) {assert(obj);QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj myStackCreate();* myStackPush(obj, x);* int param_2 myStackPop(obj);* int param_3 myStackTop(obj);* bool param_4 myStackEmpty(obj);* myStackFree(obj);
*/4. 总结
队列是一种常见的数据结构它遵循先进先出FIFO的原则。队列的主要操作包括入队将元素添加到队列的末尾和出队将队列的首个元素移除。队列还可以支持其他一些操作如查看队列首个元素和判断队列是否为空。
队列的应用十分广泛例如在多线程编程中可以用队列来实现线程间的通信处理任务和数据的排序网络传输中的消息队列等。
队列可以使用数组或链表来实现。使用数组实现队列时需要考虑队列大小的限制当队列已满时需要进行扩容操作。使用链表实现队列时可以避免扩容的问题但需要维护队列的头尾指针。
在时间复杂度方面队列的入队和出队操作的平均时间复杂度为O(1)。但在使用数组实现队列且需要扩容时入队操作的最坏时间复杂度为O(n)。
总结来说队列是一种简单而有用的数据结构适用于需要先进先出顺序的场景。它的实现方式多样使用数组或链表都可以。在设计和实现队列时需要考虑队列大小的限制以及扩容问题。 完 如果此文对您有帮助, 期待您的关注与点赞, 期待共同进步!!!
