基于数组的队列实现：如何彻底删除元素而非置零？

嘿，我来帮你捋清楚这个队列实现的问题～

首先得点明你当前的核心矛盾：你用的是朴素顺序队列实现——每次删除队首元素就把整个数组左移一位，还把末尾位置置零，但这种做法不仅效率拉胯（每次删除要移动所有元素，时间复杂度O(n)），还错误地用「0」标记空闲位置，导致你误以为末尾的物理空间没法复用。其实数组的内存空间是固定存在的，根本不需要靠置零来「删除」元素，只要调整队列的有效范围标记就行。

下面给你两种可行的解决方案，从最优到次优排序：

1. 改用环形队列（循环队列）——最推荐的方案 #

这是数组实现队列的标准优化方式，完全不需要移动元素，靠维护两个指针（front 队首索引、rear 队尾下一个空闲位置索引）循环利用数组空间，所有操作都是O(1)时间复杂度，彻底解决你的问题。

核心逻辑：

• 初始化：front = rear = 0，数组容量设为MAX_SIZE
• 判断队列空：front == rear
• 判断队列满：(rear + 1) % MAX_SIZE == front（留一个空位区分空和满状态）
• 入队：如果队列不满，把元素放到array[rear]，然后rear = (rear + 1) % MAX_SIZE
• 出队：如果队列不空，直接取array[front]，然后front = (front + 1) % MAX_SIZE

举个简单的C语言示例片段：

#define MAX_SIZE 5
int queue[MAX_SIZE];
int front = 0, rear = 0;

// 入队函数
int enqueue(int val) {
    if ((rear + 1) % MAX_SIZE == front) {
        printf("队列已满\n");
        return -1;
    }
    queue[rear] = val;
    rear = (rear + 1) % MAX_SIZE;
    return 0;
}

// 出队函数
int dequeue() {
    if (front == rear) {
        printf("队列已空\n");
        return -1;
    }
    int val = queue[front];
    front = (front + 1) % MAX_SIZE;
    return val;
}

这种方式完全不需要左移数组，也不用置零，所有空闲位置都能被循环复用，从根源避免了你的问题。

2. 保留左移逻辑，但维护有效元素长度（仅作思路参考，不推荐） #

如果你一定要保留左移的实现方式，那别再用置零标记删除了，改用一个变量count记录当前队列中有效元素的个数：

• 初始化：count = 0
• 入队：如果count < MAX_SIZE，把新元素放到array[count]，然后count++
• 出队：如果count > 0，把数组从索引1到count-1的元素依次左移一位（覆盖索引0到count-2），然后count--

这样操作的话，数组中前count个位置是有效元素，后面的位置不管存的是什么都不用管——因为入队时直接覆盖到count的位置，根本不需要置零。你之前用memset(queue, 0, ...)是完全错误的，这会把所有有效元素都清空，而且完全没必要。

举个示例片段：

#define MAX_SIZE 5
int queue[MAX_SIZE];
int count = 0;

// 入队
void enqueue(int val) {
    if (count >= MAX_SIZE) {
        printf("队列已满\n");
        return;
    }
    queue[count] = val;
    count++;
}

// 出队
int dequeue() {
    if (count == 0) {
        printf("队列已空\n");
        return -1;
    }
    int val = queue[0];
    // 左移数组
    for (int i = 0; i < count - 1; i++) {
        queue[i] = queue[i + 1];
    }
    count--;
    // 这里不需要置零！count已经减1，后面的位置下次入队会被覆盖
    return val;
}

不过这种方式每次出队都要移动所有元素，当队列元素多的时候效率很低，所以还是优先推荐环形队列。

内容的提问来源于stack exchange，提问作者Ibrahim