Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/6.操作受限的线性表 -- 队列 -- 顺序队列.md

6.1 设计模式一 -- 初始化尾指针指向下一个要插入的位置

#define MaxSize 10
typedef int ElemType;
typedef struct Queue {
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

/*
 创(初始化), front指向队头元素, rear指向下一个要插入的位置
 判空 front == rear
 判满 (rear+1) % MaxSize == front
 牺牲一个 sizeof(ElemType) 的空间
*/

void InitSqQueue(SqQueue &sqQueue) {
    sqQueue.front = 0;
    sqQueue.rear = 0;
}

bool IsEmpty(SqQueue sqQueue) {
    if (sqQueue.front == sqQueue.rear) {
        return true;
    } else {
        return false;
    }
}

bool EnSqQueue(SqQueue &sqQueue, ElemType x) {
    if ((sqQueue.rear + 1) % MaxSize == sqQueue.front) {
        return false;
    }
    sqQueue.data[sqQueue.rear] = x;
    sqQueue.rear = (sqQueue.rear + 1) % MaxSize;
    return true;
}

bool DeQueue(SqQueue &sqQueue, ElemType &x) {
    if (sqQueue.front == sqQueue.rear) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    sqQueue.front = (sqQueue.front + 1) % MaxSize;
    return true;
}

bool GetFront(SqQueue sqQueue, ElemType &x) {
    if (sqQueue.front == sqQueue.rear) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    return true;
}

6.2 设计模式二 -- size

#define MaxSize 10
typedef int ElemType;
typedef struct Queue {
    ElemType data[MaxSize];
    int front, rear;
    int size;
} SqQueue;

/*
 创(初始化), front指向队头元素, rear指向下一个要插入的位置(即队尾元素位置 + 1), size=0
 判空 size == 0
 判满 size == MaxSize
*/

void InitSqQueue(SqQueue &sqQueue) {
    sqQueue.front = 0;
    sqQueue.rear = 0;
    sqQueue.size = 0;
}

bool IsEmpty(SqQueue sqQueue) {
    if (sqQueue.size == 0) {
        return true;
    } else {
        return false;
    }
}

bool EnSqQueue(SqQueue &sqQueue, ElemType x) {
    if (sqQueue.size == MaxSize) {
        return false;
    }
    sqQueue.data[sqQueue.rear] = x;
    sqQueue.rear = (sqQueue.rear + 1) % MaxSize;
    sqQueue.size++;
    return true;
}

bool DeQueue(SqQueue &sqQueue, ElemType &x) {
    if (sqQueue.size == 0) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    sqQueue.front = (sqQueue.front + 1) % MaxSize;
    sqQueue.size--;
    return true;
}

bool GetFront(SqQueue sqQueue, ElemType &x) {
    if (sqQueue.front == sqQueue.rear) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    return true;
}

6.3 设计模式三 -- tag

#define MaxSize 10
typedef int ElemType;
typedef struct Queue {
    ElemType data[MaxSize];
    int front, rear;
    int tag;
} SqQueue;

/*
 创(初始化), front指向队头元素, rear指向下一个要插入的位置(即队尾元素位置 + 1), tag = 0
 执行出队操作, tag=0
 执行入队操作, tag=1
 判空 front == rear && tag == 0
 判满 front == rear && tag == 1
*/

void InitSqQueue(SqQueue &sqQueue) {
    sqQueue.front = 0;
    sqQueue.rear = 0;
    sqQueue.tag = 0;
}

bool IsEmpty(SqQueue sqQueue) {
    if (sqQueue.front == sqQueue.rear && sqQueue.tag == 0) {
        return true;
    } else {
        return false;
    }
}

bool EnSqQueue(SqQueue &sqQueue, ElemType x) {
    if (sqQueue.front == sqQueue.rear && sqQueue.tag == 1) {
        return false;
    }
    sqQueue.data[sqQueue.rear] = x;
    sqQueue.rear = (sqQueue.rear + 1) % MaxSize;
    sqQueue.tag = 1;
    return true;
}

bool DeQueue(SqQueue &sqQueue, ElemType &x) {
    if (sqQueue.front == sqQueue.rear && sqQueue.tag == 0) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    sqQueue.front = (sqQueue.front + 1) % MaxSize;
    sqQueue.tag = 0;
    return true;
}

bool GetFront(SqQueue sqQueue, ElemType &x) {
    if (sqQueue.front == sqQueue.rear && sqQueue.tag==0) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    return true;
}

6.4 设计模式四 -- 初始化尾指针指向队尾元素

#define MaxSize 10
typedef int ElemType;
typedef struct Queue {
    ElemType data[MaxSize];
    int front, rear;
    int size;
} SqQueue;

/*
 创(初始化), front指向队头元素, rear指向队尾元素, size=0
 判空 size == 0
 判满 size == MaxSize
*/

void InitSqQueue(SqQueue &sqQueue) {
    sqQueue.front = 0;
    sqQueue.rear = 0;
    sqQueue.size = 0;
}

bool IsEmpty(SqQueue sqQueue) {
    if (sqQueue.size == 0) {
        return true;
    } else {
        return false;
    }
}

bool EnSqQueue(SqQueue &sqQueue, ElemType x) {
    if (sqQueue.size == MaxSize) {
        return false;
    }
    //需要先将尾指针后移
    sqQueue.rear = (sqQueue.rear + 1) % MaxSize;
    sqQueue.data[sqQueue.rear] = x;
    sqQueue.size++;
    return true;
}

bool DeQueue(SqQueue &sqQueue, ElemType &x) {
    if (sqQueue.size == 0) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    sqQueue.front = (sqQueue.front + 1) % MaxSize;
    sqQueue.size--;
    return true;
}

bool GetFront(SqQueue sqQueue, ElemType &x) {
    if (sqQueue.size == 0) {
        return false;
    }
    x = sqQueue.data[sqQueue.front];
    return true;
}