循環隊列利用標志域 tag 區分滿空態的完整實現與常見錯誤

帶 tag 域的循環隊列結構

#define MAXSIZE 50
typedef char ElemType;
typedef struct {
    ElemType data[MAXSIZE];
    int front, rear;
    int tag; // 0: 空, 1: 滿
} SqQueue;

關鍵操作實現

初始化

void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;
    Q->tag = 0;
}

入隊

bool EnQueue(SqQueue *Q, ElemType x) {
    if (Q->front == Q->rear && Q->tag == 1) return false; // 滿
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    if (Q->front == Q->rear) Q->tag = 1; // 變滿
    return true;
}

出隊

bool DeQueue(SqQueue *Q, ElemType *x) {
    if (Q->front == Q->rear && Q->tag == 0) return false; // 空
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    if (Q->front == Q->rear) Q->tag = 0; // 變空
    return true;
}

提問者代碼中的致命錯誤

while ((c = getchar()) != '\n' );  // 此處多餘分號導致循環體為空！
EnQueue(&Q, c);                    // 只執行一次，且 c 已為 '\n'

分號導致 while 循環無執行體，直接跳過輸入處理，後續入隊操作使用的是換行符。去掉分號即可修復。

tag 機制優勢

傳統循環隊列犧牲一個存儲單元區分滿/空（(rear+1)%MAX == front 為滿），引入 tag 後可利用全部 MAXSIZE 個空間，邏輯更直觀。