网站空间控制面板软件,wordpress 小米模板,2345浏览器影视大全,最近免费高清版电影在线观看队列概念
队列同栈一样#xff0c;是一种特殊的数据结构#xff0c;只允许在一端进行插入操作#xff0c;在另一端进行删除操作#xff0c;队列遵循先进先出原则。
进行插入操作的一端称为队尾#xff0c;插入元素叫做入队
进行删除操作的一端称为队头#xff0c;删除…队列概念
队列同栈一样是一种特殊的数据结构只允许在一端进行插入操作在另一端进行删除操作队列遵循先进先出原则。
进行插入操作的一端称为队尾插入元素叫做入队
进行删除操作的一端称为队头删除元素叫做出队 队列同栈一样可以使用数组实现也可以使用链表实现。
各接口实现
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* ne;QDataType val;
}QNode;//队列节点typedef struct Queue
{QNode* head;//用于找到队头QNode* tail;//用于找到队尾int count;
}Queue;//队列的基本结构void QuInit(Queue* ps);
void QuDestory(Queue* ps);void QuPush(Queue* ps, QDataType x);
void QuPop(Queue* ps);QDataType QuFront(Queue* ps);
QDataType QuBack(Queue* ps);bool QuEmpty(Queue* ps);
int QuSize(Queue* ps);QuInit初始化和QuDestory销毁空间
void QuInit(Queue* ps)
{assert(ps);ps-head ps-tail NULL;ps-count 0;
}站的初始化很简单将结构体中的内容初始化为NULL和0即可 void QuDestory(Queue* ps)
{assert(ps);QNode* cur ps-head;while (cur){QNode* ne cur-ne;free(cur);cur ne;}ps-count 0;ps-head ps-tail cur NULL;
}销毁空间因为这个队列使用链表实现的并且开辟空间用的malloc函数所以不能直接把head和tail给free了这样不会把所有开辟的空间给释放会造成内存泄漏。
QuPush入队和QuPop出队
void QuPush(Queue* ps, QDataType x)
{assert(ps);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-ne NULL;if (ps-head NULL){assert(ps-tail NULL);ps-head ps-tail newnode;}else{ps-tail-ne newnode;ps-tail newnode;}ps-count;
}开辟空间的操作不多做解释。
在进行入队操作时分两种情况当head和tail都为NULL的时候插入一个元素之后队头和队尾其实是在同一个位置的。
另一种情况是队内存在元素这个时候只需要把要入队的元素链接在队尾然后让在移动tail指针移动到链接之后的队尾即可。 void QuPop(Queue* ps)
{assert(ps);assert(ps-count);if (ps-head-ne NULL){free(ps-head);ps-head ps-tail NULL;}else{QNode* cur ps-head-ne;free(ps-head);ps-head cur;}ps-count--;
}出队的时候要注意队内没有元素的时候是能出队的。
如果说队内元素只有一个那么直接free掉即可。反之就需要先创建一个临时变量用来记录一下队头的下一个元素然后free掉队头在让队头移动到临时变量的位置即可。
查看队头元素QuFront和QuBack查看队尾元素
这个很简单只要队列不为空直接返回队头指向的元素值即可
QDataType QuFront(Queue* ps)
{assert(ps);assert(ps-count);return ps-head-val;}查看队尾元素同查看队头元素一样。
QDataType QuBack(Queue* ps)
{assert(ps);assert(ps-count);return ps-tail-val;
}判断队列是否为空QuEmpty
bool QuEmpty(Queue* ps)
{assert(ps);assert(ps-count);return ps-head NULL;
}如果队列的头指针head为空则队列为空反之则队列不为空
队列长度QuSize
在实现队列的时候我们会用一个count来记录队列的长度在这里直接把count当成返回值即可
int QuSize(Queue* ps)
{assert(ps);return ps-count;
}源码
.h文件
#pragma once#include iostream
#include stdlib.h
#include assert.husing namespace std;typedef int QDataType;typedef struct QueueNode
{struct QueueNode* ne;QDataType val;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int count;
}Queue;void QuInit(Queue* ps);
void QuDestory(Queue* ps);void QuPush(Queue* ps, QDataType x);
void QuPop(Queue* ps);QDataType QuFront(Queue* ps);
QDataType QuBack(Queue* ps);bool QuEmpty(Queue* ps);
int QuSize(Queue* ps);.cpp文件
#include queue.hvoid QuInit(Queue* ps)
{assert(ps);ps-head ps-tail NULL;ps-count 0;
}void QuDestory(Queue* ps)
{assert(ps);QNode* cur ps-head;while (cur){QNode* ne cur-ne;free(cur);cur ne;}ps-count 0;ps-head ps-tail cur NULL;
}void QuPush(Queue* ps, QDataType x)
{assert(ps);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-ne NULL;if (ps-head NULL){assert(ps-tail NULL);ps-head ps-tail newnode;}else{ps-tail-ne newnode;ps-tail newnode;}ps-count;
}void QuPop(Queue* ps)
{assert(ps);assert(ps-count);if (ps-head-ne NULL){free(ps-head);ps-head ps-tail NULL;}else{QNode* cur ps-head-ne;free(ps-head);ps-head cur;}ps-count--;
}QDataType QuFront(Queue* ps)
{assert(ps);assert(ps-count);return ps-head-val;}
QDataType QuBack(Queue* ps)
{assert(ps);assert(ps-count);return ps-tail-val;
}bool QuEmpty(Queue* ps)
{assert(ps);assert(ps-count);return ps-head NULL;
}int QuSize(Queue* ps)
{assert(ps);return ps-count;
}
