数据结构-C语言版本（四）队列

数据结构中的队列：概念、操作与实战

第一部分 队列分类及常见形式

队列是一种遵循先进先出(FIFO, First In First Out)原则的线性数据结构。队列主要有以下几种实现形式：

1. 数组实现的队列（顺序队列）

#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int front;  // 队头指针int rear;   // 队尾指针
} ArrayQueue;

2. 链表实现的队列（链式队列）

typedef struct QueueNode {int data;struct QueueNode* next;
} QueueNode;typedef struct {QueueNode* front;QueueNode* rear;
} LinkedQueue;

3. 循环队列

解决顺序队列"假溢出"问题的实现方式

typedef struct {int data[MAX_SIZE];int front;int rear;
} CircularQueue;

4. 双端队列

可以在两端进行插入和删除操作的队列

typedef struct {int data[MAX_SIZE];int front;int rear;
} Deque;

5. 优先队列

元素带有优先级，出队按优先级顺序

typedef struct {int data[MAX_SIZE];int size;
} PriorityQueue;

第二部分 队列常见操作

1. 初始化队列

// 初始化顺序队列
void initArrayQueue(ArrayQueue *queue) {queue->front = 0;queue->rear = 0;
}// 初始化链式队列
void initLinkedQueue(LinkedQueue *queue) {queue->front = NULL;queue->rear = NULL;
}// 初始化循环队列
void initCircularQueue(CircularQueue *queue) {queue->front = 0;queue->rear = 0;
}

2. 入队操作

// 顺序队列入队
void enArrayQueue(ArrayQueue *queue, int value) {if(queue->rear >= MAX_SIZE) {printf("队列已满\n");return;}queue->data[queue->rear++] = value;
}// 链式队列入队
void enLinkedQueue(LinkedQueue *queue, int value) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->data = value;newNode->next = NULL;if(queue->rear == NULL) {queue->front = queue->rear = newNode;} else {queue->rear->next = newNode;queue->rear = newNode;}
}// 循环队列入队
void enCircularQueue(CircularQueue *queue, int value) {if((queue->rear + 1) % MAX_SIZE == queue->front) {printf("队列已满\n");return;}queue->data[queue->rear] = value;queue->rear = (queue->rear + 1) % MAX_SIZE;
}

3. 出队操作

// 顺序队列出队
int deArrayQueue(ArrayQueue *queue) {if(queue->front == queue->rear) {printf("队列为空\n");return -1;}return queue->data[queue->front++];
}// 链式队列出队
int deLinkedQueue(LinkedQueue *queue) {if(queue->front == NULL) {printf("队列为空\n");return -1;}QueueNode* temp = queue->front;int value = temp->data;queue->front = queue->front->next;if(queue->front == NULL) {queue->rear = NULL;}free(temp);return value;
}// 循环队列出队
int deCircularQueue(CircularQueue *queue) {if(queue->front == queue->rear) {printf("队列为空\n");return -1;}int value = queue->data[queue->front];queue->front = (queue->front + 1) % MAX_SIZE;return value;
}

4. 查看队头元素

// 查看顺序队列队头
int frontArrayQueue(ArrayQueue *queue) {if(queue->front == queue->rear) {printf("队列为空\n");return -1;}return queue->data[queue->front];
}// 查看链式队列队头
int frontLinkedQueue(LinkedQueue *queue) {if(queue->front == NULL) {printf("队列为空\n");return -1;}return queue->front->data;
}

5. 判断队列是否为空

// 判断顺序队列是否为空
int isEmptyArrayQueue(ArrayQueue *queue) {return queue->front == queue->rear;
}// 判断链式队列是否为空
int isEmptyLinkedQueue(LinkedQueue *queue) {return queue->front == NULL;
}// 判断循环队列是否为空
int isEmptyCircularQueue(CircularQueue *queue) {return queue->front == queue->rear;
}

6. 判断队列是否已满

// 判断顺序队列是否已满
int isFullArrayQueue(ArrayQueue *queue) {return queue->rear == MAX_SIZE;
}// 判断循环队列是否已满
int isFullCircularQueue(CircularQueue *queue) {return (queue->rear + 1) % MAX_SIZE == queue->front;
}

第三部分 队列编程题例子

1. 用队列实现栈

typedef struct {ArrayQueue q1;ArrayQueue q2;
} MyStack;MyStack* myStackCreate() {MyStack* stack = (MyStack*)malloc(sizeof(MyStack));initArrayQueue(&stack->q1);initArrayQueue(&stack->q2);return stack;
}void myStackPush(MyStack* obj, int x) {enArrayQueue(&obj->q1, x);// 将q2中的元素全部转移到q1while(!isEmptyArrayQueue(&obj->q2)) {enArrayQueue(&obj->q1, deArrayQueue(&obj->q2));}// 交换q1和q2ArrayQueue temp = obj->q1;obj->q1 = obj->q2;obj->q2 = temp;
}int myStackPop(MyStack* obj) {return deArrayQueue(&obj->q2);
}int myStackTop(MyStack* obj) {return frontArrayQueue(&obj->q2);
}int myStackEmpty(MyStack* obj) {return isEmptyArrayQueue(&obj->q2);
}

2. 用栈实现队列

typedef struct {ArrayStack s1;  // 用于入队ArrayStack s2;  // 用于出队
} MyQueue;MyQueue* myQueueCreate() {MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));initArrayStack(&queue->s1);initArrayStack(&queue->s2);return queue;
}void myQueuePush(MyQueue* obj, int x) {pushArrayStack(&obj->s1, x);
}int myQueuePop(MyQueue* obj) {if(isEmptyArrayStack(&obj->s2)) {while(!isEmptyArrayStack(&obj->s1)) {pushArrayStack(&obj->s2, popArrayStack(&obj->s1));}}return popArrayStack(&obj->s2);
}int myQueuePeek(MyQueue* obj) {if(isEmptyArrayStack(&obj->s2)) {while(!isEmptyArrayStack(&obj->s1)) {pushArrayStack(&obj->s2, popArrayStack(&obj->s1));}}return peekArrayStack(&obj->s2);
}int myQueueEmpty(MyQueue* obj) {return isEmptyArrayStack(&obj->s1) && isEmptyArrayStack(&obj->s2);
}

3. 滑动窗口最大值

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {if(numsSize == 0) {*returnSize = 0;return NULL;}*returnSize = numsSize - k + 1;int* result = (int*)malloc(*returnSize * sizeof(int));int deque[numsSize];int front = 0, rear = 0;for(int i = 0; i < numsSize; i++) {// 移除不在窗口内的元素while(front < rear && deque[front] < i - k + 1) {front++;}// 移除小于当前元素的元素while(front < rear && nums[deque[rear-1]] < nums[i]) {rear--;}// 添加当前元素deque[rear++] = i;// 窗口形成后记录最大值if(i >= k - 1) {result[i - k + 1] = nums[deque[front]];}}return result;
}

4. 设计循环双端队列

typedef struct {int *data;int front;int rear;int capacity;
} MyCircularDeque;MyCircularDeque* myCircularDequeCreate(int k) {MyCircularDeque* deque = (MyCircularDeque*)malloc(sizeof(MyCircularDeque));deque->data = (int*)malloc((k + 1) * sizeof(int));  // 多留一个空间判断满deque->front = 0;deque->rear = 0;deque->capacity = k + 1;return deque;
}int myCircularDequeInsertFront(MyCircularDeque* obj, int value) {if((obj->rear + 1) % obj->capacity == obj->front) {return 0;}obj->front = (obj->front - 1 + obj->capacity) % obj->capacity;obj->data[obj->front] = value;return 1;
}int myCircularDequeInsertLast(MyCircularDeque* obj, int value) {if((obj->rear + 1) % obj->capacity == obj->front) {return 0;}obj->data[obj->rear] = value;obj->rear = (obj->rear + 1) % obj->capacity;return 1;
}int myCircularDequeDeleteFront(MyCircularDeque* obj) {if(obj->front == obj->rear) {return 0;}obj->front = (obj->front + 1) % obj->capacity;return 1;
}int myCircularDequeDeleteLast(MyCircularDeque* obj) {if(obj->front == obj->rear) {return 0;}obj->rear = (obj->rear - 1 + obj->capacity) % obj->capacity;return 1;
}int myCircularDequeGetFront(MyCircularDeque* obj) {if(obj->front == obj->rear) {return -1;}return obj->data[obj->front];
}int myCircularDequeGetRear(MyCircularDeque* obj) {if(obj->front == obj->rear) {return -1;}return obj->data[(obj->rear - 1 + obj->capacity) % obj->capacity];
}int myCircularDequeIsEmpty(MyCircularDeque* obj) {return obj->front == obj->rear;
}int myCircularDequeIsFull(MyCircularDeque* obj) {return (obj->rear + 1) % obj->capacity == obj->front;
}

5. 最近的请求次数（RecentCounter）

typedef struct {int *requests;int front;int rear;int capacity;
} RecentCounter;RecentCounter* recentCounterCreate() {RecentCounter* counter = (RecentCounter*)malloc(sizeof(RecentCounter));counter->requests = (int*)malloc(10000 * sizeof(int));counter->front = 0;counter->rear = 0;counter->capacity = 10000;return counter;
}int recentCounterPing(RecentCounter* obj, int t) {obj->requests[obj->rear++] = t;while(obj->requests[obj->front] < t - 3000) {obj->front++;}return obj->rear - obj->front;
}void recentCounterFree(RecentCounter* obj) {free(obj->requests);free(obj);
}

6. 任务调度器

int leastInterval(char* tasks, int tasksSize, int n) {int count[26] = {0};for(int i = 0; i < tasksSize; i++) {count[tasks[i] - 'A']++;}// 找出最大出现次数int maxCount = 0;for(int i = 0; i < 26; i++) {if(count[i] > maxCount) {maxCount = count[i];}}// 计算有多少个任务具有最大出现次数int maxTasks = 0;for(int i = 0; i < 26; i++) {if(count[i] == maxCount) {maxTasks++;}}// 计算最小时间int result = (maxCount - 1) * (n + 1) + maxTasks;return result > tasksSize ? result : tasksSize;
}

队列作为一种基础数据结构，在操作系统调度、网络通信、广度优先搜索等领域有广泛应用。掌握队列的各种实现方式及其典型应用场景，对于解决实际问题具有重要意义。通过练习这些题目，可以深入理解队列的特性及其在算法中的应用。