队列会"跑"出去

10 分钟

用刚才那种"两个位置一直往后走"的队列,玩久了会出问题。你不停地入队又出队,head 和 tail 就像两个人手拉手一路往数组后头走,永远不回头。走过的前半段格子明明空着,却再也用不上了——空间白白浪费,最后还会走到数组尽头出界。

#include <iostream>
using namespace std;
int a[5];
int head = 0, tail = 0;
int main() {
    // 反复进出后,head、tail 都跑到后面去了
    for (int i = 0; i < 4; i++) { a[tail++] = i; head++; }
    cout << "head=" << head << " tail=" << tail << endl; // 4 4
    // 数组只有 5 格,再入队一次 tail 就要到 5,出界了
    return 0;
}

问题的根子是:位置只会加、不会绕回来,前面腾出的空间收不回来,数组再大也总有走到头的一天。下一节就用"绕圈"的办法,把这些浪费的格子重新利用起来。

小纸条

怎么解决这个浪费?

登录 后可看答案

队列会"跑"出去 · C++ 入门 · op599 课程