网站建设方面的书,初学网页设计教程,网站建设的软件,正邦设计有限公司上篇文章中#xff0c;对栈的概念及特点进行了解释#xff0c;并且给出了栈实现的具体代码。本篇文章将给出队列的基本概念及特点。并给出相应的代码。
1. 队列的概念及结构#xff1a;
在给出队列的概念之前#xff0c;先给出上篇文章中提到的栈的概念#xff1a;一种只…上篇文章中对栈的概念及特点进行了解释并且给出了栈实现的具体代码。本篇文章将给出队列的基本概念及特点。并给出相应的代码。
1. 队列的概念及结构
在给出队列的概念之前先给出上篇文章中提到的栈的概念一种只能在表尾进行插入和删除的线性表。
对于队列与栈相同的一点是依然只能在表尾插入数据。但是队列只允许在表头删除数据。
进行插入操作的一端称之为队尾。将插入数据的操作称之为入队列。
进行删除数据的一段称之为对头。将删除数据的操作称之为出队列。
队列整体结构可以有下图反应2. 队列的代码实现
2.1 队列结构的定义
通过结构体定义下放给的队列结构
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
在后续的操作中需要通过向所编写的功能函数中传递两个结构体指针来分别表示队头、队尾来达到头删、尾插的目的。例如在进行插入时插入第一个数据时、均指向第一个数据。即 只有插入的元素数量时、两个指针才会拉开差距。例如插入个元素时大致效果如下
所以在后续操作时需要改变、两个指针中的内容。在之前关于单链表的文章中一起学数据结构3——万字解析链表的概念及单链表的实现_起床写代码啦的博客-CSDN博客提到当一级指针作为形式参数时函数内部对于形式参数的更改并不会影响这两个指针中实际保存的内容。解决这个问题的方法 在之前的文章中曾提到过下面几种1. 通过传递关于二级指针来达到改变着两个指针中存储内容的目的。
2.在书写函数时最后直接返回形参。并且在外部创建变量来记录函数的返回值。
本文提供第三种方法即再额外创建一个结构体来存储这两个指针。并且将这个结构体的指针作为形参传递到函数中。即
typedef struct Queue
{QNode* phead;QNode* tail;int size;
}Que;
如果想更改中存储的内容只需要命名一个结构体指针,例如。通过可以达到目的。
对于上面提出的用结构体封装两个指针的方法也可以看作关于带头结点的双向循环链表文章一起学数据结构4——带头结点的双向循环链表_起床写代码啦的博客-CSDN博客
中哨兵位头结点的作用。
2.2 队列初始化
将结构体中各个结构体成员初始化代码如下
void QueueInit(Que* ps)
{assert(ps);ps-phead ps-tail 0;ps-size 0;
}
2.3 向队列中插入元素
与通过栈顶向栈中插入元素的思路大致相同首先需要进行扩容。但是因为在实现栈时是采用顺序实现。而对于本文的队列则采用链式实现。所以在栈中开辟空间时是开辟一部分连续空间。当这部分空间被占满时再开辟。对于链式结构只需要在每次插入之前开辟一个单独的结点即可。具体代码如下
void QueuePush(Que* ps, QDataType x)
{assert(ps);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-next NULL;newnode-data x;if (ps-tail NULL){ps-phead ps-tail newnode;}else{ps-tail-next newnode;ps-tail newnode;}ps-size;
}2.3 删除队列中的元素
在文章的前面提到队列的特点是尾部插入元素、头部删除元素、先进先出。所以对于删除队列中的元素只需要先将指向下一个结点。但是需要注意当队列中只有一个结点时当掉该结点时需要处理这两个指针。具体代码如下
void QueuePop(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));if (ps-phead-next NULL){free(ps-phead);ps-phead ps-tail NULL;}else{QNode* next ps-phead-next;free(ps-phead);ps-phead next;}ps-size--;
}
2.4 取队列的队头、队尾元素
直接通过指针返回队头、队尾的元素即可只给出代码不做多余解释
QDataType QueueFront(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps-phead-data;
}QDataType QueueBack(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps-tail-data;
}
2.5 探空
原理与栈中的探空结构相同只给出代码不做多余解释
bool QueueEmpty(Que* ps)
{assert(ps);return ps-phead NULL;
} 2.6 统计长度
在前面的删除元素、删除元素的功能中每进行一次变动都会有进行相应的变动。所以统计长度这部分直接返回即可。代码如下
int QueueSize(Que* ps)
{assert(ps);return ps-size;
} 2.7 删除栈
与删除单链表原理相同先创建一个变量存储队列的头指针通过循环进行删除对于删除的过程首先创建一个变量用于存储,再最后让存储中存储的地址。最后将全部置为或者即可。代码如下
void QueueDestory(Que* ps)
{assert(ps);QNode* cur ps-phead;while (cur){QNode* next cur-next;free(cur);cur next;}ps-phead ps-tail NULL;ps-size 0;
}
3. 队列功能测试
通过下面的测试代码对队列的功能进行测试
void TestQueue()
{Que ps;QueueInit(ps);QueuePush(ps, 1);QueuePush(ps, 2);QueuePush(ps, 3);QueuePush(ps, 4);while (!QueueEmpty(ps)){printf(%d, QueueFront(ps));QueuePop(ps);}QueueDestory(ps);}int main()
{TestQueue();return 0;
}
结果如下
