(18)王道数据结构-队列的定义和基本操作

基本结构

只允许在一端进行插入，在另一端删除的线性表，先进入队列的元素先出队

概念

队头： 允许删除的一端 队尾： 允许插入的一端

操作

InitQueue(&Q): 初始化队列，构造一个空队列Q DestroyQueue(&Q): 销毁队列，销毁并释放队列Q所占用的内存空间 EnQueue(&Q, x): 入队，若队列Q未满，将x加入，使之成为新的队尾 DeQueue(&Q, &x): 出队，若队列Q非空，删除队头元素，并用x返回 GetHead(Q, &x): 读队头元素，若队列Q非空，则将队头元素赋给x

其他操作

QueueEmpty(Q): 判断列空，若队列Q为空返回true，否则返回false

普通队列

#include<stdio.h>
#define MaxSize 10  //定义队列中元素最大个数
typedef struct {    
    int data[MaxSize];  //用静态数组存放队列元素
    int front, rear;    //队头指针和队尾指针
} SqQueue;
void InitQueue(SqQueue &Q);
bool QueueEmpty(SqQueue Q);
bool EnQueue(SqQueue &Q, int x);
bool DeQueue(SqQueue &Q, int &x);
bool GetHead(SqQueue Q, int &x);
int main(void) {
    SqQueue Q;
    int x;
    InitQueue(Q);
    
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    
    GetHead(Q, x);
    printf("x=%d\n", x);
    
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    printf("x=%d\n", x);
    return 0;
}

//初始化队列
void InitQueue(SqQueue &Q) {
    //初始时，队头和队尾指针指向0
    Q.rear=Q.front = 0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue Q) {
    if (Q.rear == Q.front) {    //队空条件
        return true;
    } else {
        return false;
    }
}

//入队
bool EnQueue(SqQueue &Q, int x) {
    if (Q.rear == MaxSize) { //队满不入队
        return false;
    }
    Q.data[Q.rear] = x;   //将x插入队尾
    Q.rear = Q.rear + 1;  //队尾指针后移
    return true;
}

//出队
bool DeQueue(SqQueue &Q, int &x) {
    if (Q.rear == Q.front) {    //队空不出队
        return false;
    }
    x = Q.data[Q.front];
    Q.front = Q.front + 1;
}

//获取队头元素
bool GetHead(SqQueue Q, int &x) {
    if (Q.rear == Q.front) {    //队空不出队
        return false;
    }
    x = Q.data[Q.front];
    return true;
}

循环队列

#include<stdio.h>
#define MaxSize 10  //定义队列中元素最大个数
typedef struct {    
    int data[MaxSize];  //用静态数组存放队列元素
    int front, rear;    //队头指针和队尾指针
} SqQueue;
void InitQueue(SqQueue &Q);
bool QueueEmpty(SqQueue Q);
bool EnQueue(SqQueue &Q, int x);
bool DeQueue(SqQueue &Q, int &x);
bool GetHead(SqQueue Q, int &x);
int main(void) {
    SqQueue Q;
    int x;
    InitQueue(Q);
    
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 7);
    EnQueue(Q, 8);
    EnQueue(Q, 9);
    EnQueue(Q, 10);
    EnQueue(Q, 11);
    EnQueue(Q, 12);
    
    GetHead(Q, x);
    printf("x=%d\n", x);
    
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    DeQueue(Q, x);
    printf("x=%d\n", x);
    return 0;
}

//初始化队列
void InitQueue(SqQueue &Q) {
    //初始时，队头和队尾指针指向0
    Q.rear=Q.front = 0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue Q) {
    if (Q.rear == Q.front) {    //队空条件
        return true;
    } else {
        return false;
    }
}

//入队
bool EnQueue(SqQueue &Q, int x) {
    if (Q.rear == MaxSize) { //队满不入队
        return false;
    }
    Q.data[Q.rear] = x;   //将x插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;  //队尾指针后移
    return true;
}

//出队
bool DeQueue(SqQueue &Q, int &x) {
    if (Q.rear == Q.front) {    //队空不出队
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
}

//获取队头元素
bool GetHead(SqQueue Q, int &x) {
    if (Q.rear == Q.front) {    //队空不出队
        return false;
    }
    x = Q.data[Q.front];
    return true;
}