推广平台有哪些渠道,台州百度搜索优化,企业管理咨询有限公司是做什么的,低价网站建设教程一、队列
1#xff09;队列定义 队列(Queue)是只允许在一端进行插入操作#xff0c;而在另一端进行删除操作的线性表。 允许插入的端是队尾#xff0c;允许删除的端是队头。队列是一个先进先出(FIFO)的线性表#xff0c;相应 的也有顺序存储和链式存储两种方式。
2#…一、队列
1队列定义 队列(Queue)是只允许在一端进行插入操作而在另一端进行删除操作的线性表。 允许插入的端是队尾允许删除的端是队头。队列是一个先进先出(FIFO)的线性表相应 的也有顺序存储和链式存储两种方式。
2循环队列 顺序存储就是用数组实现比如有一个个元素的队列数组下标0的一端是队 头入队操作就是通过数组下标一个个顺序追加不需要移动元素但是如果删除 队头元素后面的元素就要往前移动对应的时间复杂度就是O(n)性能自然不 高。 为了提高出队的性能就有了循环队列需要有两个指针front指向队头rear指 向对尾元素的下一个位置元素出队时front往后移动如果到了对尾则转到头部 同理入队时rear后移如果到了对尾则转到头部这样通过下标front出队时就不 需要移动元素了。 同时规定当队列为空时front和rear相等那么队列什么时候判断为满呢按照 循环操作rear依次后移然后再从头开始也是出现rear和front相等时队列满。 这样跟队列空的情况就相同了为了区分这种情况规定数组还有一个空闲单元 时就表示队列已满 也就是队头指针在队尾指针的下一位置时队满。 因为rear 可能在front后面也可能循环到front前面所以队列满的条件就变成了 (rear1)%maxsize front 。 对于队列的元素个数计算为(rear -frontmaxsize)%maxsize。
3用数组实现的顺序存储循环队列
4) 链式队列 循环队列要事先申请好空间整个过程都不能释放而且要有固定的长度如果长度事先无法估计这种方式显然不够灵活所以就引入了链式存储队列其实就是 线性表的单链表只是它只能对尾进队头出。并且规定队头指针指向链队列的头结点对尾指针指向终端节点当队列为空时front和rear都指向头结点。(尾插头删) 入队操作就是在链表尾部插入结点出队操作就是头结点的后继结点出队然后将头结点的后继后移。如果最后除了头结点外只剩一个元素了就把rear也指向头结点。 二、队列的操作步骤
1.构建静态数组队列结构 1)建立结构体 2)初始化队列 3)入队 4)出队 5)遍历 #includestdio.h
#include stdlib.h
#include string.h
#includestdbool.h
#includeassert.h//静态数组构建队列结构
#define SIZE 5
typedef int ele_type;typedef struct queue
{ele_type arr[SIZE];int front;int real;
} Queue;//初始化队列
void init(Queue* que)
{assert(que);memset(que-arr, 0, sizeof(ele_type) * SIZE);que-front 0;que-real 0;
}//插入元素--入队
bool push_queue(Queue* que, ele_type val)
{assert(que);if ((que-real 1) % SIZE que-front)return false;que-arr[que-real] val;que-real;que-real que-real % SIZE;return true;}//删除元素--出队
bool pop_queue(Queue* que, ele_type* rtval)
{assert(que);if (que-front que-real)return false;*rtval que-arr[que-front];que-front que-front % SIZE;return true;}//遍历队列
void print_queue(Queue* que)
{if (que-front que-real)return;if (que-front que-real){for (int i que-front; i que-real; i){printf(%d\n, que-arr[i]);}}else{for (int i que-front; i SIZE; i){printf(%d\n, que-arr[i]);}for (int i 0; i que-real; i){printf(%d\n, que-arr[i]);}}}//获取数组长度
int get_queue_size(Queue* que)
{return ((que-real - que-front SIZE) % SIZE);}//清空数组
void Clear_queue(Queue* que)
{que-front que-real 0;}int main()
{Queue q;init(q);push_queue(q, 11);push_queue(q, 12);push_queue(q, 13);push_queue(q, 14);ele_type temp;pop_queue(q, temp);printf(temp%d\n, temp);pop_queue(q, temp);printf(temp%d\n, temp);pop_queue(q, temp);printf(temp%d\n, temp);push_queue(q, 15);push_queue(q, 16);printf(\n);print_queue(q);printf(ele num%d\n, get_queue_size(q));return 0;
}
运行结果: 2.构建链表队列结构 1)建立结构体 2)初始化队列 3)入队 4)出队 5)遍历 #includestdio.h
#include stdlib.h
#include string.h
#includestdbool.h
#includeassert.h//静态数组构建队列结构
#define SIZE 5
typedef int ele_type;typedef struct queue
{ele_type arr[SIZE];int front;int real;
} Queue;//初始化队列
void init(Queue* que)
{assert(que);memset(que-arr, 0, sizeof(ele_type) * SIZE);que-front 0;que-real 0;
}//插入元素--入队
bool push_queue(Queue* que, ele_type val)
{assert(que);if ((que-real 1) % SIZE que-front)return false;que-arr[que-real] val;que-real;que-real que-real % SIZE;return true;}//删除元素--出队
bool pop_queue(Queue* que, ele_type* rtval)
{assert(que);if (que-front que-real)return false;*rtval que-arr[que-front];que-front que-front % SIZE;return true;}//遍历队列
void print_queue(Queue* que)
{if (que-front que-real)return;if (que-front que-real){for (int i que-front; i que-real; i){printf(%d\n, que-arr[i]);}}else{for (int i que-front; i SIZE; i){printf(%d\n, que-arr[i]);}for (int i 0; i que-real; i){printf(%d\n, que-arr[i]);}}}//获取数组长度
int get_queue_size(Queue* que)
{return ((que-real - que-front SIZE) % SIZE);}//清空数组
void Clear_queue(Queue* que)
{que-front que-real 0;}int main()
{Queue q;init(q);push_queue(q, 11);push_queue(q, 12);push_queue(q, 13);push_queue(q, 14);ele_type temp;pop_queue(q, temp);printf(temp%d\n, temp);pop_queue(q, temp);printf(temp%d\n, temp);pop_queue(q, temp);printf(temp%d\n, temp);push_queue(q, 15);push_queue(q, 16);printf(\n);print_queue(q);printf(ele num%d\n, get_queue_size(q));return 0;
}
运行结果:
