郸城网站建设,如何制作一个单页网站,网站数据库5g,网站与公众号的区别文章目录1 循环队列定义2 循环队列基本操作3 循环队列代码实现4 补充1 循环队列定义
循环队列#xff1a;即顺序存储的队列#xff0c;是为了避免“假溢出”而利用%运算符将队列首尾相接连成一个环状的队列#xff0c;称为循环队列。
引入循环队列克服顺序队列中存在的“假…
文章目录1 循环队列定义2 循环队列基本操作3 循环队列代码实现4 补充1 循环队列定义
循环队列即顺序存储的队列是为了避免“假溢出”而利用%运算符将队列首尾相接连成一个环状的队列称为循环队列。
引入循环队列克服顺序队列中存在的“假上溢”现象。
假上溢 因为在入队和出队操作中头尾指针只增加不减小致使被删元素的空间永远无法重新利用。因此尽管队列中实际的元素个数远远小于向量空间的规模但也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”。 简而言之就是数组中有空位置却不能再做入队出队操作 2 循环队列基本操作
队空与队满 为什么要分析队空队满的条件 循环队列是顺序存储的队列而顺序队列在做入队时要先判断队列是否已满即是否已经用完预分配的空间出队时要判断队列是否已空。 约定 front指向队列中实际头元素的位置 rear 指向队列中实际尾元素的后一位置 入队 rearrear1%MAXSIZE
queue[rear]x出队 frontfront1%MAXSIZE
xqueue[front]队空frontrear 队满front(rear1)% MAXSIZE 3 循环队列代码实现
#include stdio.h
#include stdlib.h
#include time.h
#define MAXSZIE (20)typedef int ElementType;
typedef struct SqQueue {ElementType data[MAXSZIE];int front;int rear;
} *Queue;Queue InitQueue(void)
{Queue Q (Queue)malloc(sizeof(struct SqQueue));Q-front 0;Q-rear 0;return Q;
}int IsEmpty(Queue Q)
{return Q-front Q-rear;
}int IsFull(Queue Q)
{return (Q-rear 1) % MAXSZIE Q-front;
}void EnQueue(Queue Q, ElementType e)
{if (IsFull(Q)) {return;}Q-data[Q-rear] e;Q-rear (Q-rear 1) % MAXSZIE;
}void DeQueue(Queue Q, ElementType *e)
{if (IsEmpty(Q)) {return;}*e Q-data[Q-front];Q-front (Q-front 1) % MAXSZIE;
}int main(void)
{ElementType e;Queue Q InitQueue();srand((unsigned)time(NULL));for (int i 0; i 10; i) {e rand() % 100;EnQueue(Q, e);}while (!IsEmpty(Q)) {DeQueue(Q, e);printf(%d , e);}
}4 补充
为什么要设计堆栈它有什么独特用途 ① 调用函数或子程序非它莫属 ② 递归运算的有力工具 ③ 用于保护现场和恢复现场 ④ 简化了程序设计的问题。 为什么要设计队列它有什么独特用途 ① 离散事件的模拟模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列 ② 操作系统中的作业调度一个CPU执行多个作业 ③ 简化程序设计。 什么叫“假溢出” 如何解决 答在顺序队中当尾指针已经到了数组的上界不能再有入队操作但其实数组中还有空位置这就叫“假溢出”。 解决假溢出的途径———采用循环队列。 线性表、栈、队的异同点 相同点 逻辑结构相同都是线性的都可以用顺序存储或链表存储栈和队列是两种特殊的线性表即受限的线性表只是对插入、删除运算加以限制。 不同点 ① 运算规则不同线性表为随机存取 而栈是只允许在一端进行插入和删除运算因而是后进先出表LIFO 队列是只允许在一端进行插入、另一端进行删除运算因而是先进先出表FIFO。 ② 用途不同线性表比较通用堆栈用于函数调用、递归和简化设计等队列用于离散事件模拟、OS作业调度和简化设计等。
