银行排队问题之单窗口“夹塞”版,C语言

银行排队问题是一个经典的计算机科学问题，也被称为“环形链表的插入问题”。在这个版本中，我们考虑的是一个只有一扇门、多个等待区（通常表示为环形队列）的情况，比如银行只有一个窗口，客户可以随意插队到任意位置。这个场景模拟了现实生活中的银行服务，增加了复杂性。

在C语言中，我们可以使用动态数组或结构体来构建环形队列，每个节点包含一个客户的编号和一个指向下一个节点的指针。当新客户到达时，如果队伍为空，直接添加到队尾；如果队列已满并且有插队空间，可以在任意位置插入；如果有多个空位可以选择，通常选择插入到最后一个客户之后，避免频繁移动元素导致效率降低。

以下是基本的C语言实现步骤：

1. 定义一个结构体`Customer`，包含客户ID和指向下一个客户的位置。
2. 创建一个动态数组`queue`作为环形队列，以及两个指针`front`和`rear`分别代表队首和队尾。
3. 插入函数`enqueue()`，判断队列是否满，如果满且有插队空间，随机选择插入位置；否则，简单地将新客户添加到队尾。
4. 可能需要一个删除函数`dequeue()`，从队首移除客户，并更新队头指针。
5. 主程序循环接收新的客户请求并处理，直到队列关闭或者所有客户完成服务。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
    int id;
    struct Customer *next;
} Customer;

// 环形队列操作
void enqueue(Customer **front, Customer *rear, int customer_id);
void dequeue(Customer **front);

int main() {
    // 初始化队列
    int n = 10; // 队列最大容量
    Customer *queue[n], *front = queue, *rear = queue + n - 1;
    
    srand(time(0)); // 设置随机数种子

    // 模拟客户进入，处理插队情况
    for (int i = 0; i < n; ++i) {
        int client_id = rand() % n; // 随机生成客户ID
        enqueue(&front, rear, client_id);
        printf("Client %d joins the line at position %d\n", client_id, i);
    }

    return 0;
}

void enqueue(Customer **front, Customer *rear, int customer_id) {
    if (*front == rear) { // 如果队尾等于队头，表示队列满
        Customer *new_customer = malloc(sizeof(Customer));
        new_customer->id = customer_id;
        new_customer->next = *front; // 插入到队首
        *front = new_customer;
    } else {
        Customer *current = *front;
        while (current->next != rear) {
            current = current->next;
        }
        current->next = (Customer*)malloc(sizeof(Customer)); // 插入点随机选择
        current->next->id = customer_id;
        current->next->next = *front;
    }
}