表情包生成器在线制作网站,wordpress菜单横排,苏宁易购电器商城官网,学建设网站去哪里学C/C数据结构 - 队列 循环队列
快速入门
介绍
1. 队列的定义
队列是一种线性存储结构#xff0c;每次对队列的增删操作如下 增#xff1a;在队列尾部添加元素 删#xff08;取出#xff09;#xff1a;在队列头部删除元素 这种数据存储方式遵循“先进先出”#xff0…C/C数据结构 - 队列 循环队列
快速入门
介绍
1. 队列的定义
队列是一种线性存储结构每次对队列的增删操作如下 增在队列尾部添加元素 删取出在队列头部删除元素 这种数据存储方式遵循“先进先出”First In First Out的原则简称FIFO结构
2.队列的相关概念
1队头
2队尾
3空队列
4满队列
3. 队列相关操作
1入队push()
2出队pop()
3统计队列元素个数countSize()
4判断队列是否为空isEmpty()
5获取队头 getFront()
6获取队尾getBack()
示例代码1C库函数举例
C队列queue模板类的定义在queue头文件中,queue 模板类需要两个模板参数一个是元素类型一个容器类型元素类型是必要的容器类型是可选的默认为deque 类型。C队列Queue是一种容器适配器它给予程序员一种先进先出(FIFO)的数据结构。
1. 头文件队列声明队列方法
#include queuequeueint q;
int i 10;q.push(i) 在队尾压入新元素
q.pop() 删除队列首元素但不返回其值
q.size() 返回队列中元素的个数
q.empty() 如果队列为空返回true否则返回false
q.front() 返回队首元素的值但不删除该元素
q.back() 返回队列尾元素的值但不删除该元素2.示例
#include iostream
#include queue
#include stringusing namespace std;int main()
{queueint my_q;string log; for (int i 0; i 10; i) {my_q.push(i);}cout the front of q is my_q.front() endl; // 返回定义类型cout the back of q is my_q.back() endl; // 返回定义类型log my_q.empty() true ? empty:not empty; // 返回布尔cout my_q is log endl;cout my_q size is my_q.size() endl; // 返回整数while(!my_q.empty()) {cout cur pop data my_q.front();my_q.pop(); // 无返回值cout is poped endl;}return 0;
}示例代码2C语言静态队列循环队列定长队列
C语言中如果采用固定长度的一维数组来实现队列通常使用循环队列的形式避免普通队列由于顺序存储导致执行操作POP出队时带来的时间花费问题每次从数组头部删除元素出队后需要将头部以后的所有元素往前移动一个位置这是一个时间复杂度为On的操作。
循环队列的具体原理可以参考
https://blog.csdn.net/li1914309758/article/details/81363166
由于循环队列存在弊端
当队空时frontrear 当队满时frontrear 亦成立 因此只凭等式frontrear无法判断队空还是队满。 有两种方法处理上述问题 1另设一个标志位以区别队列是空还是满。 2少用一个元素空间约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即 队空时 frontrear 队满时 (rear1)%maxsizefront
1. 头文件定义
本示例代码采用第一种方式处理循环队列的队空队满问题。
typedef struct _queue {enum QUEUE_TYPE type;int qcapacity; // 容量int qsize; // 当前队列数据的数量int front; // 队头int back; // 队尾int *qdata;
} Queue;2. 源文件
#include stdio.h
#include stdbool.h
#include stdlib.h
#include string.h
#include DH_queue.hstatic Queue *static_queue(int len)
{Queue *queue (Queue *)malloc(sizeof(Queue));memset(queue, 0, sizeof(Queue));queue-qcapacity len;queue-qsize 0;queue-front 0;queue-back 0;queue-qdata (int *)malloc(sizeof(int) * len);memset(queue-qdata, 0, sizeof(int) * len);return queue;
}static int static_countSize(Queue *q)
{return q-qsize;
}static bool static_isEmpty(Queue *q)
{if (q-qsize 0) {return 1; }return 0;
}static bool static_isFull(Queue *q)
{if (q-qsize q-qcapacity) {return 1;}return 0;
}static int static_getFront(Queue *q)
{return q-qdata[q-front];
}static int static_getBack(Queue *q)
{int index ((q-back 0) ? q-qcapacity - 1 : q-back - 1);return q-qdata[index];
}static bool static_push(Queue *q, void *data)
{if (q-qsize q-qcapacity) {printf(queue is full, push fail\n);return false;}q-qdata[q-back] *(int *)data;q-qsize 1;q-back (q-back 1) % q-qcapacity;printf(q-back %d, q-back);return true;
}static bool static_pop(Queue *q, int *data)
{if (q-qsize 0) {printf(queue is empty, pop fail\n);return false;}int tmp 0;tmp q-qdata[q-front];q-qsize - 1;q-front (q-front 1) % q-qcapacity; return true;
}// 主函数测试代码
int main()
{// 创建队列Queue *my_queue static_queue(5);// 入列for (int i 0; i 6; i) {printf( %d\n, static_push(my_queue, i));}// 遍历for (int i 0; i 5; i) {printf(%d\n, my_queue-qdata[i]);}// 队头和队尾printf(my_q front %d, get front %d, back %d, get back %d\n, my_queue-front, static_getFront(my_queue), my_queue-back, static_getBack(my_queue));// 容积和队列元素printf(my_q capacity %d, qsize %d\n, my_queue-qcapacity, my_queue-qsize);// 队空和队满printf(my_q isEmpty %d, isFull %d\n, static_isEmpty(my_queue), static_isFull(my_queue));// 出队列for (int i 0; i 6; i) {printf( %d\n, static_pop(my_queue, i));}return 0;
}
