万网做的网站咋样,如何构思公司网站,百度极速版推广员怎么申请,wordpress导航加tu队列的实现—超详细 文章目录 队列的实现---超详细一、队列的模型二、代码实现以及测试用例①队列初始化②入队③出队④输出队头⑤输出队尾⑥判断队列是否为空⑦队列的长度⑧队列的销毁⑨测试用例 一、队列的模型
队列#xff1a;只允许在一端进行插入数据操作#xff0c;在…队列的实现—超详细 文章目录 队列的实现---超详细一、队列的模型二、代码实现以及测试用例①队列初始化②入队③出队④输出队头⑤输出队尾⑥判断队列是否为空⑦队列的长度⑧队列的销毁⑨测试用例 一、队列的模型
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头。 所以我们可以思考一下这种结构如果用顺序表来实现一定是十分麻烦的因为顺序表的头删的时间复杂度是O(N)。所以我们应该要采取链表来实现队列结构。 至于是单链表还是带头双向循环链表其实都是无伤大雅的在这里我们选择单链表。 结构
typedef int SDataType;typedef struct Queue
{struct Queue* next;SDataType val;
}QU;其实这样我们已经把单链表构建出来了但是请大家思考两个问题: 如果是入队时难道我每次入队都需要去找一次尾吗 如果是计算队列长度时这是一个不在连续空间存储的数据结构我们如果简单的计算出长度呢 所以我们可以再次引入一个结构体将这个链表的头、尾和长度都计算出来。
typedef struct queue
{QU* phead;QU* tail;int size;
}q;二、代码实现以及测试用例
①队列初始化
void QIni(q* p)
{assert(p);p-phead p-tail NULL;p-size 0;
}②入队
void QPush(q* p, QDataType x)
{assert(p);QU* newnode (QU*)malloc(sizeof(QU));if (newnode NULL){perror(malloc);exit(-1);}newnode-next NULL;newnode-val x;if (p-tail NULL){p-phead p-tail newnode;}else{p-tail-next newnode;p-tail newnode;}p-size;
}③出队
void QPop(q* p)
{assert(p);assert(p-phead);QU* tmp p-phead-next;free(p-phead);p-phead tmp;if (p-phead NULL){p-tail NULL;//很关键}p-size--;
}
④输出队头
QDataType QFront(q* p)
{assert(p);assert(p-phead);return p-phead-val;
}⑤输出队尾
QDataType QBack(q* p)
{assert(p);assert(p-tail);return p-tail-val;
}⑥判断队列是否为空
bool QEmpty(q* p)
{assert(p);return p-phead NULL;
}⑦队列的长度
int QSize(q* p)
{assert(p);return p-size;
}⑧队列的销毁
void QDestroy(q* p)
{assert(p);//assert(p-phead);QU* tmp p-phead;while (tmp){QU* tmp2 tmp-next;free(tmp);tmp tmp2;}p-phead p-tail NULL;p-size 0;
}⑨测试用例
void test2()
{q p;QIni(p);QPush(p, 1);QPush(p, 2);QPush(p, 3);QPush(p, 4);QPush(p, 5);while (!QEmpty(p)){printf(%d , QFront(p));QPop(p);}printf(\n);QDestroy(p);
}int main()
{test2();return 0;
}
