[全网最细数据结构完整版]第七篇:3分钟带你吃透队列
目录
2.1定义队列基本结构 struct QueueNode 和 struct Queue
1->队列的概念及结构
队列概念:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
- 入队列：进行插入操作的一端称为队尾
- 出队列：进行删除操作的一端称为队头
2->队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2.1定义队列基本结构 struct QueueNode 和 struct Queue
#pragma once
//Queue.h
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//链式结构：表示队列
typedef struct QueueNode
{
struct QueueNode* _next;//指向下一个结点
int _data;//数据域
}QNode;
//队列的结构
typedef struct Queue
{
QNode* _phead;//指向队列头部的结点
QNode* _ptail;//指向队列尾部的结点
int _size;//队列中结点的个数
}Queue;
//1.队列初始化
void QueueInit(Queue* pq);
//2.队列销毁
void QueueDestroy(Queue* pq);
//3.队列插入数据
void QueuePush(Queue* pq, int x);
//4.队列删除数据
void QueuePop(Queue* pq);
//5.获取队列头部数据
int QueueFront(Queue* pq);
//6.获取队列尾部数据
int QueueBack(Queue* pq);
//7.获取队列有效元素的个数
int QueueSize(Queue* pq);
//8.判断队列是否为空,空返回true,非空返回false
bool QueueEmpty(Queue* pq);2.2队列初始化函数 QueueInit 函数
//1.队列初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->_phead = NULL;
pq->_ptail = NULL;
pq->_size = 0;
}2.3队列销毁函数 QueueDestroy 函数
//2.队列销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->_phead;
while (cur != NULL)
{
QNode* next = cur->_next;
free(cur);
cur = next;
}
pq->_phead = pq->_ptail = NULL;
pq->_size = 0;
}2.4队列插入数据函数 QueuePush 函数
//3.队列插入数据
void QueuePush(Queue* pq, int x)
{
assert(pq);
//申请结点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed");
return;
}
newnode->_data = x;
newnode->_next = NULL;
//插入数据
//两种情况
//1.没有结点
//2.有结点
if(pq->_phead == NULL && pq->_ptail == NULL)
{
pq->_phead = pq->_ptail = newnode;
}
else
{
pq->_ptail->_next = newnode;
pq->_ptail = newnode;
}
pq->_size++;
}2.5判断队列是否为空,空返回true,非空返回false
//4.判断队列是否为空,空返回true,非空返回false
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->_size == 0;
}
//5.队列删除数据
void QueuePop(Queue* pq)
{
assert(pq);
//得有数据才能删除对吧
assert(!QueueEmpty(pq));
//分为两种情况
//1.只有一个结点
//2.多个结点
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--;
}2.6队列删除数据 QueuePop 函数
//5.队列删除数据
void QueuePop(Queue* pq)
{
assert(pq);
//得有数据才能删除对吧
assert(!QueueEmpty(pq));
//分为两种情况
//1.只有一个结点
//2.多个结点
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--;
}
2.7获取队列头部数据 QueueFront 函数
//6.获取队列头部数据
int QueueFront(Queue* pq)
{
assert(pq);
assert(pq->_phead);
return pq->_phead->_data;
}2.8获取队列尾部数据 QueueBack 函数
//7.获取队列尾部数据
int QueueBack(Queue* pq)
{
assert(pq);
assert(pq->_ptail);
return pq->_ptail->_data;
}2.9获取队列有效元素的个数 QueueSize 函数
//8.获取队列有效元素的个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->_size;
}
3->测试我们自己写的栈
测试代码如下:
#include "Queue.h"
void testQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePush(&q, 6);
while (!QueueEmpty(&q))
{
int num = QueueFront(&q);
printf("%d->",num);
QueuePop(&q);
}
QueueDestroy(&q);
}
int main()
{
testQueue();
return 0;
}
看下控制台输出:欧耶!我们自己写的栈可以正常运行
4->扩展知识,在Linux专栏讲解
另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统专栏讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
5->做几道选择题
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A 12345ABCDE B EDCBA54321 C ABCDE12345 D 54321EDCBA 2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（） A 1,4,3,2 B 2,3,4,1 C 3,1,4,2 D 3,4,2,1 3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作 后， front=rear=99 ，则循环队列中的元素个数为（ ） A 1 B 2 C 99 D 0或者100 4.以下( )不是队列的基本运算？ A 从队尾插入一个新元素B 从队列中删除第i个元素C 判断一个队列是否为空D 读取队头元素的值
队头不存放数据) A (rear - front + N) % N + 1 B (rear - front + N) % N C ear - front) % (N + 1)
5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设D (rear - front + N) % (N - 1)
答案:
1.B
2.C 3.D 4.B5.B
6->您的专属鼓励师
有些事情，你永远都没有办法做到“顶尖”，因为智力跟不上.但是所有的事情，你都可以做到“高段”，因为它需要的是时间的累积和精力的打磨.不聪明与聪明之间的区别，是很微妙的.有时候我们只会通过一次两次的结果，来判断整个人、整件事，其实这是不明智的.从小，邻居和亲戚在谈论我的时候，都会觉得我很聪明。但是只有我自己知道，我从来没有聪明过，只是看上去比较聪明而已.
修行之路确实枯燥,但是我们把问题搞懂以后就发现他是那样的美妙!一遍学不会没关系吖,多看几遍,我也是学了好多遍呢,小伙伴们肯定学的又快又好!!!最后希望写的内容对小伙伴们有所帮助,我写的如果有哪里不对的地方请在评论区或者私信指出来哦!让我们一起进步吖,任何疑问包括心情不好都可以找我聊聊,我很乐意当你的倾听者吖.
原文地址：https://blog.csdn.net/2301_78182852/article/details/143649553
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！