队列

1.定义

队列是一种先进先出的线性表

2.链队列——队列的链式表示和实现

ADT QUEUE 表示

//—————— 单链队列 —————— 队列的连式存储结构
typedef struct QNode{
    QElementType data;
    struct QNode *next;
}QNode, *QueuePtr;	//节点的结构体，引出节点数据结构Qnode，引出指针用于下面的队列整体指示

typedef struct{
    QueuePtr front;	//队头指针
    QueuePtr rear;	//队尾指针
}LinkQueue;

// —————— 基本操作原型说明 ——————
Status InitQueue(LinkQueue &Q);		//构造一个空队列
Status DestroyQueue(LinkQueue &Q);	//销毁队列Q
Status ClearQueue(LinkQueue &Q);	//清除为空队列
Status QueueEmpty(LinkQueue Q);		//判断是否为空队列 （不进行修改，不引用Q）
int QueueLength(LinkQueue Q);		//返回Q的元素个数
Status GetHead(LinkQueue Q,QElementType &e);	//用e返回对头元素，返回值给出成功与否
Status EnQueue(LinkQueue &Q,QElementType e);	//插入元素e到Q中
Status DeQueue(LinkQueue &Q,QElementType &e);	//删除 队头元素 用e返回值
Status QueueTraverse(LinkQueue Q,visit());	//对每个元素调用visit()

核心算法：

Status InitQueue(LinkQueue &Q){
    //构造一个空队列Q
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)exit(OVERFLOW);	//存储分配失败
    Q.front -> next = NULL;
    return OK;
}

Status DestroyQueue(LinkQueue &Q){
    //销毁队列Q
    while(Q.front){//当存在队头
        Q.rear = Q.front ->next; //队尾指向队头的下一元素
        free(Q.front);	//将队头释放
        Q.front = Q.rear;
    }
    //具体流程 
    //首先Q.rear指向上图队头元素，头结点被释放
    //Q.front = Q.rear 都指向了队头元素
    //此时堆头元素不为空
    //然后Q.rear指向上图对头元素的下一个元素，原对头元素被释放
    //Q.front = Q.rear 都指向了原对头元素的下一个元素
    //如此循环， 也就是从头结点开始逐个释放内存
   	//...
    //Q.front = Q.rear 都指向了队尾元素
    //Q.front不为空，Q.rear指向NULL，队尾元素被释放，此时队列全部内存释放
    //最后Q.front = Q.rear = NULL;
    return OK;
}

Status EnQueue(LinkQueue &Q, QElemenType e){
    //插入元素e为Q的新的队尾元素，注意先进先出原则
    p = (QueuePtr) malloc (sizeof(QNode)); //给要插入的元素分配内存，注意传入参数是QElementType
    if(!p) exit(OVERFLOW);
    p -> data = e;
    p -> next = NULL;
    Q.rear ->next = p; //Q.rear -> next 指向p （先将p连在队尾元素上）
    Q.rear = p;	//Q.rear 指向p （再将队尾指针现在指向p）
    
}

Status DeQueue(LinkQueue &Q,QElementType &e){
    //如果队列不为空，则删除Q的队头元素，用e返回其值，并返回OK
    //否则返回ERROR
    if(Q.front == Q.rear) return ERROR; //Q.front == Q.rear 意味着队列为空，都指向头结点，无队头元素无队尾元素
    p = Q.front -> next;	//用p临时保存队头元素的地址 （用p临时指向队头元素）
    e = p -> data;	//用e返回队头元素的值
    Q.front ->next = p -> next;	//头结点指向的队头元素为新队头元素
    if(Q.rear == p) Q.rear == Q.front;	//如果删去的队头元素就是队尾元素，那么队尾指针指回头结点
    free(p);	//操作完成，释放p指向的队头元素的内存 （如果是引用计数，这时候只有临时指针p引用了该队头元素，也就可以理解为被抛弃了）
    return OK;
}

3.循环队列——队列的顺序表示和实现

注意：

• 仅靠 Q.front = Q.rear 无法判断队列是空还是满。解决办法：
  • 另外设一个标志位来区别队列是空还是满
  • 少用一个元素空间，约定“队列头指针在队列为指针的下一位置上，作为队列满的标志
• 循环队列必须设定一个最大队列长度（顺序表实现），如果用户无法预估队列的最大长度，宜采用链队列

ADT表示

//—————— 循环队列 —————— 队列的顺序存储结构
#define MAXQSIZE 100	//最大队列长度
typedef struct{
    QElementType *base;	//初始化的动态分配 连续的 存储空间 (初始动态分配队列空间长度) 往后的指针可以通过int加减来指向位置（因为是连续的）
    int front;	//头指针，若队列不空，指向队列头元素
    int rear;	//为指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

//—————— 循环队列的基本操作算法描述 ——————
Status InitQueue(SqQueue &Q){
    //构造一个空队列Q
    Q.base = (QElementType *) malloc (MAXQSIZE * sizeof(QElementType));
    if(!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

int QueueLength(SqQueue Q){
    //返回Q的元素个数，即队列长度
    return(Q.rear - Q.front + MAXQSIZE) & MAXQSIZE; //很专业的计数法
}

Status EnQueue(SqQueue &Q, QElementType e){
    //插入元素e为Q的队尾元素
    if((Q.rear + 1) % MAXQSIZE == Q.front ) return ERROR;	//队列满，不能插入
    Q.base[Q.rear] = e;	//队列尾插入元素
    Q.rear = (Q.rear + 1) % MAXQSIZE;	//尾指针后移
    return OK;
}