数据结构（队列） |
您所在的位置：网站首页 › 溢出现象出现在什么情况 › 数据结构（队列） |
数据结构（队列）
|
目录 队列的实现 顺序队列的几种溢出情况 队列的顺序存储结构 循环队列 循环队列初始化 求队列长度 入队 出队 取队头元素 链队列 链式存储结构 初始化 入队 出队 取队头元素 队列是一种先进先出的线性表，只允许在队尾插入，在队头删除元素。 队列也分为顺序队列和链队列 队列的实现 顺序队列的几种溢出情况（1） "下溢"现象：当队列为空时，出队运算产生的溢出现象。“下溢”是正常现象。 （2）"真上溢"现象：当队列满时，进栈运算产生空间溢出的现象。“真上溢”是一种出错状态。是一种错误。 （3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，使被删元素的空间永远无法重新利用。不能做入队操作。这种现象称为"假上溢"现象。 队列的顺序存储结构在队列的存储结构中，需要设置front和rear两个整形变量来分别指示队头元素和队尾元素（又称头指针和尾指针）。 typedef struct { QElemType *base;//初始化时动态分配存储空间 int front;//头指针 int rear;//尾指针 } SqQueue; 循环队列当入队次数足够多时，我们会发现数据不能如队列了，但队列中还有剩余空间，这是由队列的特点决定的（可以称为假溢出）。所以引入了循环队列。 循环队列指的是队列的实现方式，用一个头尾相接的循环链表，或者逻辑上头尾相接的数组（读取最后一个元素的下一个元素时会跳转到第一个元素），将队列安置在其中，空间被循环使用。
1. 循环队列初始化也就是为队列分配一个预定义大小的存储空间。 2. 再让base指针指向首地址 3. 将rear和front指针置空 Status InitQueue(SqQueue &Q) {//构造一个空队列Q Q.base = new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXSIZE的数组空间 if (!Q.base) exit(OVERFLOW); //存储分配失败 Q.front = Q.rear = 0; //头指针和尾指针置为零，队列为空 return OK; } 求队列长度1. 对于非循环队列，尾指针和头指针之差就是队列的长度 2. 对于循环队列，差值可能为负数，所以要进行求余运算 int QueueLength(SqQueue Q) {//返回Q的元素个数，即队列的长度 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; } 入队入队，也就是在队尾插入新元素 1. 判断队列是否为栈满 2. 将新元素插入队尾 3. 队尾指针加一 Status EnQueue(SqQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素 if ((Q.rear + 1) % MAXQSIZE == Q.front) //尾指针在循环意义上加1后等于头指针，表明队满 return ERROR; Q.base[Q.rear] = e; //新元素插入队尾 Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针加1 return OK; } 出队出队，也就是删除队头元素 1. 判断队列是否空栈 2. 引入变量，暂时保存队头元素 3. 头指针加一 Status DeQueue(SqQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值 if (Q.front == Q.rear) return ERROR; //队空 e = Q.base[Q.front]; //保存队头元素 Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1 return OK; } 取队头元素1. 判断非空 2. 取头元素 SElemType GetHead(SqQueue Q) {//返回Q的队头元素，不修改队头指针 if (Q.front != Q.rear) //队列非空 return Q.base[Q.front]; //返回队头元素的值，队头指针不变 } 链队列一般，链队列采用单链表来表示。和之前一样，要设置两个指针表示队头元素和队尾元素，并让头指针始终指向头结点。 链式存储结构 typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 } LinkQueue; 初始化构造一个有头结点的空队列 1. 创建头结点 2. 让front和rear指向头结点 3. 头结点指针域置空 Status InitQueue(LinkQueue &Q) {//构造一个空队列Q Q.front = Q.rear = new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点 Q.front->next = NULL; //头结点的指针域置空 return OK; } 入队链队列元素入队列时不需要判断队满 1. 为入队元素开辟存储空间 2. 将新结点插到表尾 3. 修改rear指针 Status EnQueue(LinkQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素 QueuePtr p; p = new QNode; //为入队元素分配结点空间，用指针p指向 p->data = e; //将新结点数据域置为e p->next = NULL; Q.rear->next = p; //将新结点插入到队尾 Q.rear = p; //修改队尾指针 return OK; } 出队需要判断是否空栈 Status DeQueue(LinkQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值 QueuePtr p; if (Q.front == Q.rear) return ERROR; //若队列空，则返回ERROR p = Q.front->next; //p指向队头元素 e = p->data; //e保存队头元素的值 Q.front->next = p->next; //修改头指针 if (Q.rear == p) Q.rear = Q.front; //最后一个元素被删，队尾指针指向头结点 delete p; //释放原队头元素的空间 return OK; }
取队头元素
SElemType GetHead(LinkQueue Q) {//返回Q的队头元素，不修改队头指针
if (Q.front != Q.rear) //队列非空
return Q.front->next->data; //返回队头元素的值，队头指针不变
}
|
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |