能否用线性队列实现输入受限Deque？可行性验证及代码分析

问题核心 #

能否不使用循环队列，而是用线性队列实现输入受限Deque？该方案是否可行（尽管并非最优选择）？

可行性结论 #

可行。线性队列可以通过元素后移的方式模拟队首插入操作，从而实现输入受限Deque的核心功能，只是队首插入的时间复杂度会升高至O(n)。

代码验证与解析 #

以下是修正格式并补充中文注释的实现代码：

#include <stdio.h>
#define SIZE 5

// 定义线性队列结构
struct QUEUE{
    int queue[SIZE];
    int front, rear;
} q;

// 判断队列是否已满
int isFull(){
    if(q.rear == SIZE - 1) return 1;
    return 0;
}

// 判断队列是否为空
int isEmpty(){
    if(q.front == -1 || q.front > q.rear) return 1;
    return 0;   
}

// 队尾插入元素
void enqueue_back(){
    if(!isFull()){
        int ele;
        printf("\n请输入要插入队尾的元素: ");
        scanf("%d", &ele);
        q.queue[++q.rear] = ele;
    } else {
        printf("\n队列已满。");
    }
    // 处理初始空队列的情况
    if (q.front == -1){
        q.front++;
    }  
}

// 队首插入元素
void enqueue_front(){
    // 处理初始空队列的情况
    if (q.front == -1){
        q.front++;
    } 
    if(!isFull()){
        // 将现有元素全部后移一位，腾出队首位置
        for (int i = q.rear + 1; i > q.front; i--){
            q.queue[i] = q.queue[i-1];
        }
        int ele;
        printf("\n请输入要插入队首的元素: ");
        scanf("%d", &ele);
        q.queue[q.front] = ele;
        q.rear++;
    } else {
        printf("\n队列已满。");
    }
}

// 队首删除元素
void dequeue(){
    if(!isEmpty()){
        ++q.front;
    } else {
        printf("\n队列已空。");
    }
}

关键逻辑说明 #

• 队尾插入：直接在rear指针下一位添加元素，时间复杂度O(1)，和普通线性队列逻辑一致。
• 队首插入：通过循环将队列所有元素后移一位，腾出队首位置后插入新元素，最后rear指针后移。此步骤需要遍历整个队列，时间复杂度为O(n)。
• 队首删除：仅需将front指针后移一位，时间复杂度O(1)。
• 空/满判断：isFull通过rear是否到达数组末尾判断；isEmpty通过front为初始值或front超过rear判断。

方案局限性 #

虽然该方案可行，但存在明显不足：

• 队首插入的时间复杂度为O(n)，数据量较大时效率低下。
• 线性队列空间利用率低，删除元素后front指针前的空间无法复用，易出现"假溢出"（队列实际有剩余空间但rear已到数组末尾）。

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