在现实生活中，当人们去银行、行政大厅等企业和办事机构办理业务时，都需要从排队机领取排队号码，等待叫号。类似排队机这样的程序，其内部数据结构一般都会用到队列结构。

一、队列结构

队列结构和栈结构一样，都是特殊的线性表，但也有不同之处。栈结构只允许在表的一端插入和删除数据，而队列结构只允许在表的一端插入元素，而在另一端删除元素。允许插入元素的一端称为队尾，允许删除元素的一端称为队头。若给定一队列：

S = (a1，a2，……，an)

则称a1是队头元素，an是队尾元素，表中元素按an，……a2，a1的次序入队，出队的顺序是a1，a2，……，an。也就是说，队列结构的元素访问原则是先进先出，因此队列结构也称为先进先出的线性表，如图1所示。

图 1 队列结构

队列结构运算有入队、出队、访问队头元素、置队空四种基本运算。

（1）入队运算

该运算在长度为n的队列中，将元素置入队尾。若队列已满，返回出错信息。

（2）出队运算

该运算在长度为n的队列中，取出队首元素，并从队首删除该元素。若队列为空，返回出错信息。

（3）访问队首元素

该运算在长度为n的队列中，取出队首元素。若队列为空，返回出错信息。

（4）置队空

该运算将队列设置为空队列。

在程序中要实现队列结构，采用线性链表存储结构最为合适。每次的入队和出队运算无需移动队列元素，队列长度也可以动态变化。

下面的C语言代码实现了队列结构：

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;
void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}
int isFull(Queue *q) {
    return (q->rear == MAX_SIZE - 1);
}
int isEmpty(Queue *q) {
    return (q->front == -1 || q->front > q->rear);
}
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->data[q->rear] = value;
}
int dequeue(Queue *q) {
int value;
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    value = q->data[q->front];
    q->front++;
    if (q->front > q->rear) {
        q->front = q->rear = -1;
    }
    return value;
}
int main() {
    Queue q;
    initializeQueue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("%d\n", dequeue(&q));  // 输出 1
    printf("%d\n", dequeue(&q));  // 输出 2
    return 0;
}

上述代码使用一个数组来存储队列的元素，并使用两个整数front和rear来跟踪队列的开头和结尾。enqueue函数用于向队列添加元素，dequeue函数用于从队列中移除元素，isFull和isEmpty函数来检查队列是否已满或为空。

_{注意：在实际应用中，可能还需要对队列进行更复杂的操作和优化，例如处理队列溢出、使用动态数组来动态调整队列的大小等。}

二、数据结构设计

在银行业务办理自动叫号系统中，一般采用队列结构，因为它能够模拟顾客先来先服务的原则。

银行业务办理自动叫号系统需要满足以下功能：

顾客取号：当顾客到达银行时，系统分配一个唯一的号码给顾客。

号码显示：系统显示当前正在服务的顾客号码和下一个等待服务的顾客号码。

叫号：当柜台空闲时，系统自动叫下一个等待服务的顾客号码。

取消服务：如果顾客决定离开，可以取消其号码，并将其从队列中移除。

基于上述功能，定义的队列数据结构如下：

// 定义队列节点结构体
typedef struct QueueNode {
    int number; // 顾客号码
    struct QueueNode *next;
} QueueNode;
// 定义队列结构体
typedef struct Queue {
    QueueNode *front; // 队头指针
    QueueNode *rear; // 队尾指针
} Queue;

QueueNode为链表节点，number存储顾客号码，next指向链表的下一个节点。Queue为队列结构体，front指向队列的队头节点，rear指向队列的队尾节点。

三、取号和叫号

业务办理自动叫号有两个关键事件。一个事件是取号，当新的客户办理业务时，需要在排队机取号；一个事件是叫号，当业务办理窗口开始办理新业务时，需要叫号。取号事件是入队操作，叫号事件是出队操作。

// 入队操作：将新顾客号码添加到队尾
void enqueue(Queue *q, int number) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->number = number;
    newNode->next = NULL;
    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}
// 出队操作：从队头取出下一个服务的顾客号码
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1; // 返回错误码表示队列为空
    }
    QueueNode *temp = q->front;
    int number = temp->number;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL; // 如果队列为空，则更新队尾指针
    }
    free(temp); // 释放已服务顾客的节点内存
    return number;
}

四、服务号码维护

可以使用两个整数变量来分别记录当前服务号码和下一个服务号码。当柜台空闲时，更新这两个变量以反映队列中的下一个顾客号码。

// 当前服务号码，初始化为-1表示无人服务
int currentServiceNumber = -1;
 // 下一个服务号码，初始化为-1表示无等待顾客
int nextServiceNumber = -1;
// 当柜台空闲时，调用此函数更新当前服务号码和下一个服务号码
void updateServiceNumbers(Queue *q) {
if (!isEmpty(q)) {
// 从队列中取出下一个服务的顾客号码
        nextServiceNumber = dequeue(q); 
// 更新当前服务号码为下一个服务号
        currentServiceNumber = nextServiceNumber; 码
} else {
// 如果没有等待顾客，则当前服务号码置为-1
        currentServiceNumber = -1; 
    }
}