顺序队列C实现优化

顺序队列是一种线性数据结构，它按照元素的顺序存储，并通过两端的操作进行插入和删除。在C语言中实现顺序队列，我们通常使用数组作为底层数据容器。在这个"顺序队列C实现优化"中，重点是提高了空间效率，使得其空间复杂度达到O(1)，这意味着在进行队列操作时，不再需要额外分配或释放大量的内存。 1. **创建队列**：在C中，创建队列通常涉及到初始化一个数组，定义队列的头部和尾部指针。这个过程可以设置一个固定大小的数组，初始时头和尾指针都设为0，表示队列为空。 ```c typedef struct { int* data; // 存储元素的数组 int front; // 队头位置 int rear; // 队尾位置 int size; // 数组大小 } SeqQueue; SeqQueue* createQueue(int capacity) { SeqQueue* queue = (SeqQueue*)malloc(sizeof(SeqQueue)); if (!queue) return NULL; queue->data = (int*)malloc(capacity * sizeof(int)); if (!queue->data) { free(queue); return NULL; } queue->front = queue->rear = 0; queue->size = capacity; return queue; } ``` 2. **销毁队列**：销毁队列需要释放数组和结构体占用的内存。 ```c void destroyQueue(SeqQueue* queue) { free(queue->data); free(queue); } ``` 3. **清空队列**：清空队列只需将队头和队尾指针重置为0，保留数组空间。 ```c void clearQueue(SeqQueue* queue) { queue->front = queue->rear = 0; } ``` 4. **进队列**（enqueue）：在队尾添加元素，更新队尾指针。 ```c int enqueue(SeqQueue* queue, int item) { if ((queue->rear + 1) % queue->size == queue->front) { return -1; // 队列满，无法添加 } queue->data[queue->rear] = item; queue->rear = (queue->rear + 1) % queue->size; return 0; } ``` 5. **出队列**（dequeue）：移除队头元素并返回，更新队头指针。 ```c int dequeue(SeqQueue* queue) { if (queue->front == queue->rear) { return -1; // 队列空，无法移除 } int item = queue->data[queue->front]; queue->front = (queue->front + 1) % queue->size; return item; } ``` 6. **获取队头元素**（getFront）：返回队头元素，但不移除。 ```c int getFront(SeqQueue* queue) { if (queue->front == queue->rear) { return -1; // 队列空，无队头元素 } return queue->data[queue->front]; } ``` 7. **获取队列长度**（getQueueLength）：计算当前队列中的元素个数。 ```c int getQueueLength(SeqQueue* queue) { if (queue->front <= queue->rear) { return queue->rear - queue->front; } else { return queue->size - (queue->front - queue->rear); } } ``` 在优化后的实现中，可能采用了循环数组的方式处理队列满的情况，避免了动态扩容导致的空间复杂度提升。循环数组通过取模运算确保元素的正确存储和访问，从而保持了O(1)的空间复杂度。这样的设计对于需要高效处理大量数据的场景尤其有用，例如在操作系统调度、网络协议栈或者图形渲染等领域。通过以上代码，我们可以创建、管理并操作一个高效、空间利用率高的顺序队列。