C++ 循环队列

总结归纳队列实际上就是现实生活中的排队队头的人先走新来的人排到队尾。先进先出后进后出。队列的实现需要一个队头指针一个队尾指针用于入队和出队。对于循环队列初始化时需将 Q.front Q.rear 0Q.front 指向队头Q.rear 指向新元素入队的位置。循环队列物理上仍然是申请一片连续的内存空间但通过 (Q.rear 1) % MaxSize Q.front 的判断条件从逻辑上模拟环状空间从而实现循环队列。代码中值得一提的是 GetLength(SqQuene Q, ElemType len) 函数获取队列长度当有元素出队时实际上只是将 Q.front 前移从逻辑上出队原先的队头仍然存在当下次有新元素入队时直接进行覆盖所以长度的遍历应从 Q.front 开始而在队列的初始化中我们设置的是 Q.front Q.rear 0 例如当队列中有一个元素时Q.front 0而 length 1所以我们需要将这个 1 补回来才是真正的队列长度。以往的 GetLength 代码总是通过指针来进行遍历而循环队列能不能用指针获取长度我的看法是不可以如果可以麻烦告诉我。之前的数据结构能用指针遍历是因为 struct 结构体中就定义了指针所以可以申请一个结构体指针指向该结构体通过 p p-next 来进行遍历而循环队列的实质仍然是一片连续的内存空间诚然你可以申请一个数组指针 int *p Q.data但又回到了刚才的问题在已有元素出队的情况下Q.data 的第一个元素就不是队头这会影响到队列长度的判断。而对于链式数据结构删了就是删了直接 delete / free 就没有这个问题。代码语言javascriptAI代码解释// 获取队列长度 bool GetLength(SqQuene Q, ElemType len) { if (Q.front Q.rear) { len 0; } else { len Q.front; // 指向队头 while ((len 1) % MaxSize ! Q.rear) { len; } len len - Q.front 1; // 如果有元素出队会导致Q.front不为0影响长度的判断且初始化队列时Q.front置为0同样影响长度 } return true; }代码实现代码语言javascriptAI代码解释/* 循环队列 */ #include iostream #define MaxSize 10 // 队列中元素的最大个数 using namespace std; typedef int ElemType; struct SqQueue { ElemType data[MaxSize]; // 队列中元素的最多个数 int front, rear; // 队头指针队尾指针 }; // 初始化队列 void InitQueue(SqQueue Q) { Q.front Q.rear 0; } // 队列判空 bool QueueEmpty(SqQueue Q) { if (Q.front Q.rear) { return true; } else { return false; } } // 入队 bool EnQueue(SqQueue Q, ElemType x) { if ((Q.rear 1) % MaxSize Q.front) { // 队满 return false; } else { Q.data[Q.rear] x; // 赋值给下一队尾 Q.rear (Q.rear 1) % MaxSize; // 在逻辑上将存储空间变为“环状”物理上仍然是静态数组 return true; } } // 出队 bool DeQueue(SqQueue Q, ElemType x) { if (Q.rear Q.front) { // 队空 return false; } else { x Q.data[Q.front]; Q.front (Q.front 1) % MaxSize; // 队头指针后移 return true; } } // 获取队头元素 bool GetHead(SqQueue Q, ElemType x) { if (Q.rear Q.front) { // 队空 return false; } else { x Q.data[Q.front]; return true; } } // 获取队列长度 bool GetLength(SqQueue Q, ElemType len) { if (Q.front Q.rear) { len 0; } else { len Q.front; // 指向队头 while ((len 1) % MaxSize ! Q.rear) { len; } len len - Q.front 1; // 如果有元素出队会导致Q.front不为0影响长度的判断且初始化队列时Q.front置为0同样影响长度 } return true; } int main() { SqQueue Q; InitQueue(Q); ElemType head, pop, length; for (int i 1; i 6; i) { EnQueue(Q, i); } GetHead(Q, head); cout 队头元素 head endl; GetLength(Q, length); cout 队列长度 length endl; DeQueue(Q, pop); cout 出队元素 pop endl; GetHead(Q, head); cout 队头元素 head endl; GetLength(Q, length); cout 队列长度 length endl; }