南京网站设计与制作,qq企业邮箱 wordpress,wordpress文章字体大小,网站管理助手 伪静态1.队列的定义:
和栈相反,队列(queue)是一种先进先出(first in first out,缩写为FIFO)的线性表.它只允许在表的一端进行插入,而在另一端删除元素. 在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front).
2.循环队列的设计图示: 3.循环队列的结构设计:
ty…1.队列的定义:
和栈相反,队列(queue)是一种先进先出(first in first out,缩写为FIFO)的线性表.它只允许在表的一端进行插入,而在另一端删除元素. 在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front).
2.循环队列的设计图示: 3.循环队列的结构设计:
typedef struct SqQueue
{int *base;//指向动态内存;int front;//队头指针,队头元素的下标int rear;//队尾指针,当前可以插入数据的下标(队尾后一个元素的下标)//int queuesize;//队列的总容量,要做到自动扩容就必须增加这个成员;
}SqQueue,*PSqQueue;
4.循环队列的实现
//初始化
static bool IsFull(PSqQueue pq)
{return (pq-rear 1) % SIZE pq-front;//return pq-rear 1 pq-front;//error,需要处理成环形;
}//往队列中入数据(入队操作)
bool Push(PSqQueue pq, int val)
{assert(pq ! NULL);if (pq NULL)return false;if (IsFull(pq))//如果队满则入队失败{return false;}pq-base[pq-rear] val;//pq-rear;//error,必须要处理成环形;pq-rear (pq-rear 1) % SIZE;return true;
}
//获取队头元素的值,但是不删除
bool GetTop(PSqQueue pq, int* rtval)
{assert(pq ! NULL);if (pq NULL)return false;if (IsEmpty(pq)){return false;}*rtval pq-base[pq-front];return true;
}
//获取队头元素的值,但是删除
bool Pop(PSqQueue pq, int* rtval)
{assert(pq ! NULL);if (pq NULL)return false;if (IsEmpty(pq)){return false;}*rtval pq-base[pq-front];//pq-front;//errorpq-front (pq-front 1) % SIZE;return true;
}
//判空
bool IsEmpty(PSqQueue pq)
{assert(pq ! NULL);if (pq NULL)return false;return pq-front pq-rear;
}
//获取队列中有效元素的个数
//重点,考点:公式
int GetLength(PSqQueue pq)
{assert(pq ! NULL);if (pq NULL)return -1;return (pq-rear - pq-front SIZE) % SIZE;
}
//清空所有的数据
void Clear(PSqQueue pq)
{pq-front 0;pq-rear 0;
}
//销毁
void Destroy(PSqQueue pq)
{assert(pq ! NULL);if (pq NULL)return;free(pq-base);pq-base NULL;pq-front 0;pq-rear 0;
}
5.循环队列的总结
1)队列:先进先出的一种线性结构,入队(插入)的一端称为队尾,出队(删除)的一端称为队头
2)队列的存储方式有两种,一种为顺序结构(顺序队列),两一种为链式结构(链式队列) 3)顺序队列一定会设计成环形队列,原因是线性队列的入队为O(1),出队为O(n),而环形队列的入队为O(1),出队为O(1)
4)浪费一个空间不使用,主要是为了区分队空和队满的情况:空是队头和队尾相同,满是rear(队尾指针)再往后走一步为front(队头指针) (浪费一个空间) 5)队满的处理方式:1.固定长度,队满则入队失败(处理简单,不实用),采用1,和书本一致.2,长度不固定,队满则自动扩容(实现稍微复杂)
