石家庄制作网站的公司哪家好,视频分享网站建设难吗,小程序外包公司,大连看妇科哪家医院好链式结构实现队列 1.队列1.1队列的概念及结构1.2队列的实现 2. 队列的各种函数实现3. 队列的全部代码实现 1.队列
1.1队列的概念及结构
队列#xff1a;只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出 FIFO(Fi… 链式结构实现队列 1.队列1.1队列的概念及结构1.2队列的实现 2. 队列的各种函数实现3. 队列的全部代码实现 1.队列
1.1队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out)的原则
入队列进行插入操作的一端称为队尾
出队列进行删除操作的一端称为队头
如图所示
1.2队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
2. 队列的各种函数实现
首先我们先定义一个栈的结构
typedef int QDataType;//节点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;//链表的结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;这里我们定义了两个结构体这是因为在尾插的时候需要一个尾指针如果每次尾插的时候都要遍历找尾效率太低所以我们可以定义一个尾指针在头删的时候需要一个头指针这个size其实可以加上有也可以不加但是不加上的话求队列长度的时候需要遍历比较麻烦多个数据共同管理这个队列所以我们可以封装成一个结构体来管理这个队列。
初始化队列
void QueueInit(Queue* pq)
{aseert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}因为队列中的每个节点的空间都是动态开辟的所以在用完队列后要及时释放动态开辟的每一个节点。 队尾入队列
void QueuePush(Queue* pq,QDataType x)
{assert(pq);QNode* newcode QueueBuyNode(x);if (pq-phead NULL){assert(pq-ptail NULL);//防止一个为空一个不为空的情况pq-phead pq-ptail newcode;}else{pq-ptail-next newcode;pq-ptail pq-ptail-next;}pq-size;
}这里也可以不把申请节点的代码单独写成一个函数因为这里只有这一个地方会用到申请节点的操作但是还是建议封装成一个函数一方面可以提高代码的可读性另一方面可以在一定程度上避免代码出错。
这里的assert(pq-ptail NULL);这句代码主要时为了防止自己的代码写错造成一个为空一个不为空的情况所以也可以不写保证写代码的时候细心一点就可以了。 申请一个节点
QNode* QueueBuyNode(QDataType x)
{c* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(1);}newnode-data x;newnode-next NULL;
}注意这里是申请一个节点所以要用定义队列节点的结构体类型 QNode而不是管理队列的结构题类型 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead-next NULL){pq-phead NULL;pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}这里的队头出数据也就是头删操作要注意当删除的链表元素只剩一个时这里的头指针和尾指针同时指向这一个节点当删除这个节点的时候头指针和尾指针都会改变所以最好单独处理一下。
因为当只有一个节点的时候执行删除操作后头指针会变成空所以我们可以在头指针变成空的时候也把尾指针变成空所以这个代码也可以这样写。
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QNode* next pq-phead-next;free(pq-phead);pq-phead next;if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}想要获取队头元素只需要返回队头指针指向的元素的值 获取队列尾部元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}想要获取队尾元素只需要返回队尾指针指向的元素的值
获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}这里只需要返回控制队列结构里面的size就可以了如果不把size封装结构体里面就需要遍历链表求队列元素个数不但麻烦效率也低。 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}当头指针和尾指针同时指向空的时候链表一定为空。
3. 队列的全部代码实现
Queue.h
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int QDataType;//节点的结构
typedef struct QueueNode
{QDataType data;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);//获取队列中有效元素个数
int QueueSize(Queue* pq);//检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq);
Queue.c
#include Queue.h// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}QNode* QueueBuyNode(QDataType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}//队尾入队列
void QueuePush(Queue* pq,QDataType x)
{assert(pq);QNode* newcode QueueBuyNode(x);if (pq-phead NULL){assert(pq-ptail NULL);pq-phead pq-ptail newcode;}else{pq-ptail-next newcode;pq-ptail pq-ptail-next;}pq-size;
}// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead-next NULL){pq-phead NULL;pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}//获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}Test.c
#include Queue.hint main()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);printf(size : %d\n,QueueSize(q));while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}printf(\n);QueueDestroy(q);return 0;
}因为队列是后进先出的所以要访问队列里面的元素时必须要把队列当前元素取出才能访问下一个元素每可以看到在打印队列里面的内容时会把队列变成空那么队列里面的内容就没有了但时这也是实际当中的需求所以不会有什么影响。
运行结果如图
