郴州网络推广公司推荐,随州网站seo,大宗商品现货电子交易平台,教修图的网站队列 目录
目录
队列
一、队列基础知识
二、队列的基本操作
1.顺序存储
编辑 #xff08;1#xff09;顺序存储
#xff08;2#xff09;初始化及队空队满
#xff08;3#xff09;入队
#xff08;4#xff09;出队
#xff08;5#xff09;打印队列
1顺序存储
2初始化及队空队满
3入队
4出队
5打印队列
6循环队列
7顺序可运行总代码
2.链式存储
(1)链式存储定义
(2)初始化
(3)进队
(4)出队
(5)打印链队
(6)链队可运行总代码
3.双端队列。
(1)输入受限的双端队列
(2)输出受限的双端队列
(3)例题 一、队列基础知识 简介队列是一种先进先出FIFO的线性数据结构是一种只允许在一端进行插入操作队尾在另一端进行删除操作的数据结构队头。插入操作在队列的末尾进行删除操作在队列的前端进行即队头元素先出队后插入的元素排在队尾。 队列是一种广泛应用于计算机科学领域的数据结构常用于实现消息队列、任务队列、缓冲队列等。在算法设计中队列可以用于广度优先搜索BFS、模拟银行排队等问题。同时队列还常与栈结构搭配使用实现更复杂的算法和数据结构。
二、队列的基本操作 简介队列可以使用数组或链表实现。常见的队列操作包括入队enqueue、出队dequeue、获取队头元素front、获取队列长度size等。
1.顺序存储 简介就是数组两个标记队头和队尾的变量构成的结构体。 优点简单易实现。 缺点容易出现假溢出问题队列未满时向队列尾插入元素却因为队列头指针没有移动而导致队列满的情况。 1顺序存储 即一个一维数组和两个标记队头和队尾的变量。
代码如下
//队列的顺序存储
#define MaxSize 10
typedef struct
{int data[MaxSize];int front;int rear;// int count;//记录队列中实际元素个数,可先不用
}SqQueue;
2初始化及队空队满 初始化
//队列初始化
void QueueInit(SqQueue *q)
{q-front0; q-rear0;
} 队空当队头和队尾相等的时候便为空。不仅仅限制于都等0因为两个变量都在一直变化。
//队空
bool QueueEmpty(SqQueue *q)
{if(q-front q-rear )return true;
} 队满这里面队满不好判定当rearMaxSize-1时会出现假溢出现象不算队满。不过可以在队列顺序存储时结构体里面加一个计时器出队一次count--入队一次count当countMaxSize-1时队满。
typedef struct
{int data[MaxSize];int front;int rear;int count;
}SqQueue;
//队满
bool QueueFull(SqQueue *q)
{if(q-count MaxSize-1)return true;
}
3入队 从队尾rear处进行遍历入队赋值。随后rear1后撤。
//入队
void EnQueue(SqQueue *q,int x)
{//如果队满了 if(QueueFull(q)false)exit(-1);//给队尾处赋值 q-data[q-rear]x;//移动队尾标记 q-rear;//数据数1 q-count;
}
4出队
//出队
void OutQueue(SqQueue *q,int *e)
{//判断非法情况是否为空 if(q-front q-rear)exit(-1);//取出队头元素赋值给e *eq-data[q-front];//队头指针 q-front;//元素个数-1 q-count--;
}
5打印队列
void QueuePrint(SqQueue *q)
{int i0;printf(目前队列中有%d个数据\n,q-count);//从队头遍历到队尾 for(iq-front;iq-rear;i){printf(%d ,q-data[i]); }printf(\n);
}
6循环队列 简介由于普通的顺序存储队列存在假溢出现象导致出队后出现的空缺没法补上这时候循环队列就出手了。它则是多了个取余操作每次模数组最大值给溢出的数字控制在最大值之内达到循环形成了一个环。 即每一次标记队头和队尾遍历变换时变为了q-front(q-front1)%MaxSize;q-rear(q-rear1)%MaxSize; 此外循环队列在判断队满时一般两种操作 一个是牺牲最后一个格子当rear1front时此时队满。 另一个操作则是像我最开头在结构体定义里面加一个记录实际数据的计数器每次出队入队计数器进行相应的加减。当计数器等于MaxSize时队满。 此外循环队列的长度计算为[MaxSize-(q-rear - q-front)]%MaxSize;但如果之前在结构体里面加了一个计数器则直接打印计数器即可。 下面时循环队列的操作。 入队只不过比之前入队多了一个判断队满的判断以及移动队尾指针时取余
void CycEnQueue(SqQueue *q,int x)
{//如果队满了 if(QueueFull(q)1) //可以在结构体中加个计数器exit(-1);//if(q-rear1 q-front) //也可以牺牲一个存储单元用来判断队满// exit(-1);//给队尾处赋值 q-data[q-rear]x;//移动队尾标记 q-rear(q-rear1)%MaxSize;//数据数1 q-count;
} 出队
void CycOutQueue(SqQueue *q,int *e)
{//判断非法情况是否为空 if(q-front q-rear)exit(-1);//取出队头元素赋值给e *eq-data[q-front];//队头指针 q-front(q-front1)%MaxSize;//元素个数-1 q-count--;
} 7顺序可运行总代码
#include stdio.h
#include stdlib.h
//队列
//队列的顺序存储
#define MaxSize 10
typedef struct
{int data[MaxSize];int front;int rear;//计数器 int count;
}SqQueue;
//队列初始化
void QueueInit(SqQueue *q)
{q-front0; q-rear0;q-count0;
}
//队空
int QueueEmpty(SqQueue *q)
{if(q-front q-rear )return 1;
}
//队满
int QueueFull(SqQueue *q)
{if(q-count MaxSize-1)return 1;elsereturn -1;
}
//入队
void EnQueue(SqQueue *q,int x)
{//如果队满了 if(QueueFull(q)1)exit(-1);//给队尾处赋值 q-data[q-rear]x;//移动队尾标记 q-rear;//数据数1 q-count;
}
void CycEnQueue(SqQueue *q,int x)
{//如果队满了 if(q-rear1 q-front)exit(-1);//给队尾处赋值 q-data[q-rear]x;//移动队尾标记 q-rear(q-rear1)%MaxSize;//数据数1 q-count;
}
//出队
void OutQueue(SqQueue *q,int *e)
{//判断非法情况是否为空 if(q-front q-rear)exit(-1);//取出队头元素赋值给e *eq-data[q-front];//队头指针 q-front;//元素个数-1 q-count--;
}
void CycOutQueue(SqQueue *q,int *e)
{//判断非法情况是否为空 if(q-front q-rear)exit(-1);//取出队头元素赋值给e *eq-data[q-front];//队头指针 q-front(q-front1)%MaxSize;//元素个数-1 q-count--;
}
//打印队列
void QueuePrint(SqQueue *q)
{int i0;printf(目前队列中有%d个数据\n,q-count);//从队头遍历到队尾 for(iq-front;iq-rear;i){printf(%d ,q-data[i]); }printf(\n);
} //队列的链式存储 int main()
{//创建队列 SqQueue q;//初始化队列 QueueInit(q);//打印队列 QueuePrint(q);//入队 EnQueue(q,0); EnQueue(q,1); EnQueue(q,2); EnQueue(q,3); QueuePrint(q);//出队 int e0;OutQueue(q,e);QueuePrint(q);printf(出队%d\n,e);return 0;
}
2.链式存储 简介使用链表数据结构实现每个节点都包含一个元素和指向下一个节点的指针。 链表队列的优点可以动态地调整队列长度。 链表队列的缺点需要更多的内存空间存储指针信息。另外由于需要动态申请和释放内存链表实现的队列在操作上比数组实现的队列稍慢
(1)链式存储定义 简介由单链表构成然后由队头指针和队尾指针进行操作因此定义两个结构体一个结构体是定义队列结点类型的一个则是封装队头队尾指针。
/链队结点
typedef struct Linknode
{int data;struct Linknode* next;
}LinkNode;
//链队的头指针和尾指针
typedef struct
{LinkNode* front;LinkNode* rear;
}LinkQueue;
(2)初始化
这里面初始化默认带头节点就是为了是开头操作和其他情况操作一致。
/链队初始化
void InitQueue(LinkQueue* q)
{//创建头节点LinkNode* s (LinkNode*)malloc(sizeof(LinkNode));if (s NULL)exit(-1);else{s-next NULL;q-front q-rear s;q-rear-next NULL;}//return q;
}
初始化的时候头节点定义完后队头指针和队尾指针都指向它并且队尾指针的指针域指向空。
(3)进队
进队时也是先定义一个队列结点用来加入队。随后用队尾指针进行相关操作。先连接结点再更新队尾指针。
//入队
void EnQueue(LinkQueue* q, int x)
{//创建结点LinkNode* s (LinkNode*)malloc(sizeof(LinkNode));if (s NULL)exit(-1);else{s-data x;s-next NULL;//队尾所指向的结点的指针域指向存储s结点地址q-rear-next s;//更新尾指针q-rear s;}}
(4)出队
出队时先判断是否为空队随后再进行出队操作出队时先定义一个指针指向需要出队的元素因为这里由头节点而队头指针始终指向头节点因此标记出队元素指针为队头指针的指针域即头节点的后继节点为实际出队结点。随后头节点的指针域指向出队结点的后继并判断当前出队的元素是否为最后一个结点即如果q-rear p则让队内初始化为空即队头指针和队尾指针相等。随后释放掉P结点。
//出队
void DeQueue(LinkQueue* q, int* e)
{//判断非法情况空队 if (q-front q-rear)exit(-1);//给出队元素赋值 *e q-front-next-data;//标记出队元素 LinkNode* p q-front-next;//队头指针后移到出队元素后继节点 q-front-next p-next;//判断是否仅有一个结点 if (q-rear p){q-rear q-front;}free(p);//return q;
}
(5)打印链队
定义一个工作指针
工作指针从实际第一个元素结点开始即头节点的后继节点。
void LinkQueuePrint(LinkQueue* q)
{LinkNode* pos q-front-next;//队头元素指向头节点int i 0;while (pos !NULL){printf(%d-, pos-data);pos pos-next;}printf(NULL\n);
}
(6)链队可运行总代码
#include stdio.h
#include stdlib.h
#include string.h
//链队结点
typedef struct Linknode
{int data;struct Linknode* next;
}LinkNode;
//链队的头指针和尾指针
typedef struct
{LinkNode* front;LinkNode* rear;
}LinkQueue;
//链队初始化
void InitQueue(LinkQueue* q)
{//创建头节点LinkNode* s (LinkNode*)malloc(sizeof(LinkNode));if (s NULL)exit(-1);else{s-next NULL;q-front q-rear s;q-rear-next NULL;}//return q;
}
//入队
void EnQueue(LinkQueue* q, int x)
{//创建结点LinkNode* s (LinkNode*)malloc(sizeof(LinkNode));if (s NULL)exit(-1);else{s-data x;s-next NULL;//队尾所指向的结点的指针域指向存储s结点地址q-rear-next s;//更新尾指针q-rear s;}//return q;
}
//出队
void DeQueue(LinkQueue* q, int* e)
{//判断非法情况空队 if (q-front q-rear)exit(-1);//给出队元素赋值 *e q-front-next-data;//标记出队元素 LinkNode* p q-front-next;//队头指针后移到出队元素后继节点 q-front-next p-next;//判断是否仅有一个结点 if (q-rear p){q-rear q-front;}free(p);//return q;
}
void LinkQueuePrint(LinkQueue* q)
{LinkNode* pos q-front-next;//队头元素指向头节点int i 0;while (pos !NULL){printf(%d-, pos-data);pos pos-next;}printf(NULL\n);
}
int main()
{LinkQueue q ;InitQueue(q);EnQueue(q, 0);EnQueue(q, 1);EnQueue(q, 2);EnQueue(q, 3);LinkQueuePrint(q);int e 0;DeQueue(q, e);printf(e%d\n, e);LinkQueuePrint(q);DeQueue(q, e);printf(e%d\n, e);LinkQueuePrint(q);return 0;
}
3.双端队列。
这一部分了解思想即可主要用于计算选择和填空。 简介 双端队列Double-ended Queue是一种特殊的队列它允许在队列两端进行插入和删除操作。双端队列可以看作是两个栈首尾相接构成的数据结构。在双端队列中可以在队列头部和尾部进行元素的插入和删除操作因此它的操作有从队头插入元素、从队头删除元素、从队尾插入元素、从队尾删除元素等。
双端队列可以用数组或链表实现。在数组中实现时需要注意队列头部和尾部指针的位置。当队列长度大于数组长度时需要进行扩容操作。在链表中实现时只需要维护头结点和尾结点即可。
双端队列的应用非常广泛比如操作系统中的进程调度队列、窗口滑动中的数据缓存等场景都可以使用双端队列来实现。
说白了就是再原来队列的基础上多了好几个功能即两端都可以进行入队和出队操作。 之后便引申出了一个题型。输入受限的双端队列输出受限的双端队列。
(1)输入受限的双端队列 即一段仅能输出另一端输入输出都可以就是仅能输出那一段不能输入就是输入受限。 这里记住一个技巧若1234为入队序列那么输入受限的话有这样公式..1..2..3..4,即先先出4的话2就不能紧跟着出。因为2位于1 3中间。这种技巧是可以得到不可能得到的序列
(2)输出受限的双端队列 即一段仅能输入另一端不限制就是仅能输入那一段不能输出就是输出受限。 技巧若1234入队序列那么有这样公式12...3..4,这时4输出了那么3一定不会12之间因为12是紧挨着的。这种技巧是可以得到不可能得到的序列
(3)例题 有一双端队列输入序列为1234分别求出一下条件的输出序列 1.能由输入受限得到输出得不到。 2.能由输出受限得到输入得不到。 3.输入输出都得不到
解应用题的话需要一个个证明有些多我觉得一般都是选择和填空因此我们采用技巧取做。 技巧可以得到输入受限不可能得到的序列和输出受限不可能得到的序列随后我们让这两个求差集即可。
输入受限得不到 规律..1..2..3..4,那么4先出则2一定不会紧跟着出来
所以不可能得到的为4213 和 4231
输出受限得不到的 规律12...3..4,那么4先出。则3一定不会再12中间因为12是紧邻着的
所以不可能得到的为4132 和 4231
随后我们根据条件去筛选即可。
(1)输入得到输出得不到。 我们从输出得不到的里面去筛选输入可以得到的
所以为4,1,3,2因为4,2,3,1在输入受限中也得不到所以排除。
(2)输出得到输入得不到我们从输入得不到的里面去筛选输出可以得到的所以为 4,2,1,3,因为4,2,3,1输出也得不到所以排除。
(3)输入输出都得不到因此我们找这俩的交集所以为4,2,3,1 至此队列基本理论结束以后记得常来复习。基本操作要滚瓜烂熟先明白整体再去记忆具体。
