佛山按天网站优化服务,做宣传的视频网站有哪些,品牌建设10步通达,wordpress hexo主题制作目录
一、队列的定义
二、队列的顺序储存结构
2.1顺序队列的定义
2.2循环队列定义
2.3循环队列的基本操作
三、队列的链式储存结构
3.1链队列的定义
3.2链队列的基本操作 一、队列的定义
队列是一种线性表#xff0c;其特殊性在于队列的基本操作是线性表的子表。队列…目录
一、队列的定义
二、队列的顺序储存结构
2.1顺序队列的定义
2.2循环队列定义
2.3循环队列的基本操作
三、队列的链式储存结构
3.1链队列的定义
3.2链队列的基本操作 一、队列的定义
队列是一种线性表其特殊性在于队列的基本操作是线性表的子表。队列按先进先出的规则进行操作故称其为操作受限的线性表。
队列queue是只允许在一端进行插入操作在另一端进行删除操作的线性表简称“队”。
允许插入的一端称为队尾rear允许删除的一端称为队头(front)。
向队列中插入新的数据元素称为入队新入队的元素就成为了队列的队尾元素。
从队列中删除队头元素称为出队其后继元素成为新的队头元素。
注出队的方向应该与入队的方向一致。
以下为一个简单的队列实现代码
#include stdio.h
#include stdlib.h#define MAX_SIZE 100// 定义队列结构体
typedef struct {int items[MAX_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue *q) {q-front -1;q-rear -1;
}// 检查队列是否为空
int isEmpty(Queue *q) {return q-front -1;
}// 检查队列是否已满
int isFull(Queue *q) {return (q-rear MAX_SIZE - 1);
}// 入队操作
void enqueue(Queue *q, int value) {if (isFull(q)) {printf(Queue is full\n);return;}if (q-front -1) {q-front 0;}q-rear;q-items[q-rear] value;
}// 出队操作
int dequeue(Queue *q) {int item;if (isEmpty(q)) {printf(Queue is empty\n);return -1;}item q-items[q-front];if (q-front q-rear) {q-front -1;q-rear -1;} else {q-front;}return item;
}int main() {Queue q;initQueue(q);enqueue(q, 10);enqueue(q, 20);enqueue(q, 30);printf(%d dequeued from queue\n, dequeue(q));printf(%d dequeued from queue\n, dequeue(q));return 0;
}二、队列的顺序储存结构
队列作为一种特殊的线性表也同样存在两种存储结构顺序存储结构和链式存储结构可以分别用数组和链表来实现队列。
2.1顺序队列的定义
用一组地址连续的存储单元依次存放从队头到队尾的数据元素称为顺序队列。
需要附设两个指针队头指针front和队尾指针rear分别指向队头元素和队尾元素。
以下为实现代码
#include stdio.h
#include stdlib.h#define MAX_SIZE 100// 定义队列结构体
typedef struct {int items[MAX_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue *q) {q-front 0;q-rear -1;
}// 检查队列是否为空
int isEmpty(Queue *q) {return (q-rear q-front);
}// 检查队列是否已满
int isFull(Queue *q) {return (q-rear MAX_SIZE - 1);
}// 入队操作
void enqueue(Queue *q, int value) {if (isFull(q)) {printf(Queue is full\n);return;}q-rear;q-items[q-rear] value;
}// 出队操作
int dequeue(Queue *q) {int item;if (isEmpty(q)) {printf(Queue is empty\n);return -1;}item q-items[q-front];q-front;return item;
}// 获取队列长度
int queueLength(Queue *q) {if (isEmpty(q)) {return 0;}return (q-rear - q-front 1);
}int main() {Queue q;initQueue(q);enqueue(q, 10);enqueue(q, 20);enqueue(q, 30);printf(%d dequeued from queue\n, dequeue(q));printf(%d dequeued from queue\n, dequeue(q));printf(Queue length: %d\n, queueLength(q));return 0;
}接下来介绍在此过程中可能出现的假溢出的现象
“假溢出”如果在插入E的基础上再插入元素F将会插入失败。因为rearMAXSIZE尾指针已经达到队列的最大长度。但实际上队列存储空间并未全部被占满这种现象叫做“假溢出”。
假溢出的原因是顺序队列进行队头出队、队尾入队造成数组前面会出现空闲单元未被充分利用。 2.2循环队列的定义
为了解决可能出现的假溢出现象使得队列中的储存空间可以得到充分利用一个巧妙的方法就是使用循环队列的方法将顺序队列看作一个头尾相接的循环结构。
故可以得出循环队列的定义是队列头尾相接的顺序储存结构称为循环队列。
循环队列的实现代码
#include stdio.h
#include stdlib.h#define MAX_SIZE 100// 定义队列结构体
typedef struct {int items[MAX_SIZE];int front;int rear;int size;
} Queue;// 初始化队列
void initQueue(Queue *q) {q-front 0;q-rear -1;q-size 0;
}// 检查队列是否为空
int isEmpty(Queue *q) {return (q-size 0);
}// 检查队列是否已满
int isFull(Queue *q) {return (q-size MAX_SIZE);
}// 入队操作
void enqueue(Queue *q, int value) {if (isFull(q)) {printf(Queue is full\n);return;}q-rear (q-rear 1) % MAX_SIZE;q-items[q-rear] value;q-size;
}// 出队操作
int dequeue(Queue *q) {int item;if (isEmpty(q)) {printf(Queue is empty\n);return -1;}item q-items[q-front];q-front (q-front 1) % MAX_SIZE;q-size--;return item;
}int main() {Queue q;initQueue(q);enqueue(q, 10);enqueue(q, 20);enqueue(q, 30);printf(%d dequeued from queue\n, dequeue(q));printf(%d dequeued from queue\n, dequeue(q));return 0;
}但是循环队列也是会出现问题
问题当循环对列为空或满时都是队尾指针等于队头指针即rearfront 。当rearfront时该是判满还是判空呢
解决方案
方案一设置一个计数器开始时计数器设为0新元素入队时计数器加1元素出队计数器减1。当计数器MAXSIZE时队满计数器0时队空。
方案二保留一个元素空间当队尾指针指的空闲单元的后继单元是队头元素所在单元时队满。
队满的条件为Q.rear1%MAXSIZEQ.front
队空的条件为 Q.rearQ.front
2.3循环队列的基本操作
typedef int ElemType
#define MAXSIZE 1024/*循环队列的顺序存储结构*/
typedef struct
{ElemType data[MAXSIZE];int front; //头指针int rear; //尾指针
}SqQueue;/*初始化一个空队列*/
int Init_SeQueue(SeQueue *Q)
{Q(SeQueue *)malloc(sizeof(SeQueue));if(Q!NULL){Q-front0;Q-rear0;}return 1;
}/*求队列长度*/
int QueueLength(SeQueue *Q)
{return (Q-rear-Q-frontMAXSIZE)%MAXSIZE;
}/*判空*/
int SeQueue_Empty(SeQueue *Q)
{return Q-rearQ-front;
}/*判满*/
int SeQueue_Full(SeQueue *Q)
{return (Q-rear1)%MAXSIZEQ-front;
}/*入队操作*/
int Enter_SeQueue(SeQueue *Q,ElemType e)
{if(SeQueue_Full(Q)){return 0;}Q-data[Q-rear]e;Q-rear(Q-rear1)%MAXSIZE;return 1;
}/*出队操作*/
int Delete_SeQueue(SeQueue *Q,ElemType e)
{if(SeQueue_Empty(Q)){return 0;}eQ-data[Q-front];Q-front(Q-front1)%MAXSIZE;return 1;
}
三、队列的链式存储结构
3.1链队列的定义
采用链式储存结构的队列称为链队列。
为了使操作更加方便将队头指针指向链队列的头结点而队尾指针指向终端结点。
空队列时front和rear都指向头结点即frontrear
代码实现链队列结构
typedef int ElemType/*结点结构*/
typedef struct QNode
{ElemType data;struct QNode *next;
}QNode,*QueuePtr;/*链队列结构*/
typedef struct
{QueuePtr front,rear;//队头、队尾指针
}LinkQueue;
3.2链队列的基本操作
typedef int ElemType/*结点结构*/
typedef struct QNode
{ElemType data;struct QNode *next;
}QNode,*QNodePtr;/*链队列结构*/
typedef struct
{QNodePtr front,rear;//队头、队尾指针
}LinkQueue,*LinkQueuePtr;/*初始化一个空队列*/
int Init_LinkQueue(LinkQueuePtr Q)
{Q(LinkQueuePtr)malloc(sizeof(LinkQueue));QNodePtr head(QueuePtr)malloc(sizeof(QNode));if(head!NULL Q!NULL){head-nextNULL;Q-fronthead;Q-rearhead;}return 1;
}/*判空*/
int LinkQueue_Empty(LinkQueuePtr Q)
{return Q-frontQ-rear;
}/*入队操作*/
int Enter_LinkQueue(LinkQueuePtr Q,ElemType e)
{QNodePtr s(QNodePtr)malloc(sizeof(QNode));if(sNULL){return 0} //初始化新结点s-datae;s-nextNULL;//建立新联系Q-rear-nexts;Q-rears;return 1;
}/*出队操作*/
int Delte_LinkQueue(LinkQueuePtr Q,ElemType *e)
{QNodePtr p;if(LinkQueue_Empty(Q)){return 0} //保留删除结点的信息pQ-front-next;*ep-data;//建立新联系Q-front-nextp-next;if(Q-rearp){Q-rearQ-front)}free(p);return 1;
}
以上就是有关队列的知识及代码实现。
