当前位置：首页 > article >正文

队列—学习

article 2025/2/3 21:27:02

1. 手写队列的实现

使用数组实现队列是一种常见的方法。队列的基本操作包括入队（enqueue）和出队（dequeue）。队列的头部和尾部分别用 head 和 tail 指针表示。

代码实现

const int N = 10000;  // 定义队列容量，确保够用
int que[N];           // 队列，用数组模拟
int head = 0;         // head始终指向队头。que[head]是队头。开始时队列为空，head = 0
int tail = -1;        // tail始终指向队尾。que[tail]是队尾。开始时队列为空，tail = -1

操作

入队：que[++tail] = data; 先将 tail 指针加1，然后将数据 data 放入队列。
出队：head++; 将 head 指针加1，表示队头元素出队。
读队头：que[head]; 读取队头元素。

2. 数组溢出问题

如果队列中的数据过多，tail 超过数组容量 N，会导致数组溢出。为了避免这个问题，可以使用循环队列。

3. 约瑟夫问题的实现

约瑟夫问题可以通过队列来模拟报数过程。以下是实现代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 10000; 
int que[N];
int head = 0, tail = -1;

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        que[++tail] = i;  // 初始化队列，将所有人入队
    }

    while ((tail - head + 1) != 0) {  // 队列不为空
        for (int i = 1; i < m; i++) {  // 报数，将前m-1个人重新入队
            que[++tail] = que[head];
            head++;
        }
        cout << que[head] << " ";  // 输出第m个人
        head++;  // 第m个人出队
    }
    cout << endl;
    return 0;
}