一、前言本篇为数据结构的第五讲队列队列是先进先出的线性表允许删除的叫队头允许插入的叫队尾二、顺序队列循环队列1. 假溢出问题当不断出队时front向后移动数组前面会空出大量空闲位置但rear走到数组末尾后就算数组前面有空位也无法继续入队看起来 “满了”实际空间并没有用完这就是假溢出。2.循环队列判空、判满的3种方法空队列条件Q.rear Q.front满队列条件Q.rear Q.front牺牲一个空间引入一个标志变量区别空和不空使用计数器3. 循环队列入队入队a2,a1,a0核心代码if((rear 1) % maxSize front){ resize(); } rear (rear 1) % maxSize; data[rear] x;出队出a1,a0核心代码if(empty()) throw outOfRange(); // 若队列为空则无元素出队抛出异常outOfRange()。 front (front 1) % maxSize; return data[front];取队头核心代码if(empty()) throw outOfRange(); // 若队中无元素则抛出异常outOfRange() return data[(front 1) % maxSize]; // 取队首元素返回队首元素数值三、链队列1.入队核心代码Node *p new Node(value,top); top p; //将值为value的元素推入栈中2.出队核心代码if(empty()) throw outOfRange(); //若为空栈则无法出栈元素则抛出异常outOfRange() Node *p top; T value p-data; top top-next; delete p; //将栈顶元素出栈并返回元素值。 return value;3.取栈顶元素核心代码if(empty()) throw outOfRange(); // 若为空栈无法返回栈顶元素则抛出异常outOfRange() return top-data; // 取栈顶操作返回栈顶元素值4.求栈中元素个数核心代码Node *p top; int count 0; while(p){ count; p p-next; } return count;5.清空栈核心代码Node *p; while(top ! NULL){ // 将栈中元素逐一出栈并释放空间。 p top; top top-next; delete p; }四、总结本文围绕队列重点讲解了顺序队列循环队列与链队列两种实现方式并复刻了核心操作与关键细节。在顺序队列循环队列部分先解决了假溢出问题。同时针对循环队列判空与判满条件相同Q.rear Q.front的难点介绍了三种常用方法。最后给出了入队、出队和取队头操作的核心代码。在链队列部分我们基于链表实现了队列避免了顺序存储中可能出现的假溢出和空间浪费问题。总的来说顺序队列循环队列适合元素数量可预估、追求较高空间利用率的场景链队列则更灵活适合元素数量动态变化、需要频繁插入和删除的场景。理解两者的区别与适用场景有助于在实际开发中做出合理选择。
)
