美文网首页
数据结构之队列

数据结构之队列

作者: jokerlee | 来源:发表于2020-05-18 12:09 被阅读0次

    一.循环队列

    1.构建结构

    //定义队列的结构
    typedef struct{
        //队头
        int front;
        //队尾
        int real;
        //队空间(静态空间)
        SElemType data[MAXSIZE];
    } SqQueue;
    
    

    2.初始化队列

    //初始化队列
    Status InitQueue(SqQueue *queue){
        queue->front = queue->real = 0;
        return OK;
    }
    

    3.清空队列

    //清空队列
    Status ClearQueue(SqQueue *queue){
        if (!queue) {
            return ERROR;
        }
        queue->front = 0;
        queue->real = 0;
        return OK;
    }
    
    

    4.判断是否为空队列

    //判断队列是否为空
    Status EmptyQueue(SqQueue queue){
        if (queue.front == queue.real) {
            return TRUE;
        }
        return FALSE;
    }
    
    

    5.获取队列的长度

    //获得队列的长度
    int GetQueueLength(SqQueue queue){
        return (queue.real - queue.front + MAXSIZE)%MAXSIZE;
    }
    

    6.便利队列

    //遍历队列
    Status TraversalQueue(SqQueue queue){
        printf("队列内容是:\n");
        //从队头开始遍历
        int i = queue.front;
        //因为是循环队列,所以从队头开始查到队尾结束,%MAXSIZE是为了取具体位置
        while ((i + queue.front)%MAXSIZE != queue.real) {
            printf("%d\n",queue.data[i]);
            i = (i+1)%MAXSIZE;
        }
        return OK;
    }
    
    

    7.入队

    //入队
    Status PushQueue(SqQueue *queue, SElemType data){
        if ((queue->real + 1)%MAXSIZE == queue->front) {//队满了
            return ERROR;
        }
        queue->data[queue->real] = data;
        //以为你是循环队列,所以real不能一直++,估要+1后%MAXSIZE
        queue->real = (queue->real + 1)%MAXSIZE;
        return OK;
    }
    

    8.出队

    //出队
    Status PopQueue(SqQueue *queue, SElemType *data){
        if (queue->front == queue->real) {//空队列
            return ERROR;
        }
        *data = queue->data[queue->front];
        printf("出队的是:%d\n",*data);
        queue->front = (queue->front + 1)%MAXSIZE;
        return OK;
    }
    

    二.链式队列

    无需关心队列是否满了
    内存空间不连续
    链式需要关心节点的释放

    1.节点结构

    //构造队列结点
    typedef struct QNode {
        SElemType data;
        struct QNode *next;
    }QNode,*QListNode;
    //构造队列
    typedef struct{
        QListNode front;
        QListNode real;
        //用来记录队列的长度
        int count;
    } SQueue;
    

    2.初始化链式队列

    //初始化链式队列
    Status InitNodeQueue(SQueue *queue){
        queue->front = queue->real = (QListNode)malloc(sizeof(QNode));
        if (!queue->front) {
            return ERROR;
        }
        //队头指向Null
        queue->front->next = NULL;
        queue->count = 0;
        return OK;
    }
    

    3.判断是否为空的链式队列

    //是否是空的链式队列
    Status EmptyNodeQueue(SQueue queue){
        if (queue.front == queue.real) {
            return TRUE;
        }
        return FALSE;
    }
    

    4.清空队列

    //将链式队列清空
    Status ClearNodeQueue(SQueue *queue){
        if (queue->front == queue->real) {//如果是空队列
            printf("空队列\n");
            return ERROR;
        }
        queue->real = queue->front;
        queue->count = 0;
        QListNode p = queue->front->next,temp;
        queue->front->next = NULL;
        while (p) {
            temp = p;
            free(p);
            p = temp->next;
        }    return OK;
    }
    

    5.链式队列的长度

    //获得链式队列的长度
    int GetNodeQueueLenght(SQueue queue){
        /*
         //方法一
        if (queue.front == queue.real) {//空队列
            return 0;
        }
        int i = 1;
        QListNode p = queue.front->next;
        while (p) {
            p = p->next;
            if (p) {
                i++;
            }
        }
        return i;
        */
        //方法二:
        return queue.count;
    }
    

    6.便利链式队列

    //遍历链式队列
    Status TraversalNodeQueue(SQueue queue){
        if (queue.front == queue.real) {
            printf("空队列\n");
            return ERROR;
        }
        printf("队列内容:");
        QListNode p = queue.front->next;
        while (p) {
            printf("%4d",p->data);
            p = p->next;
        }
        printf("\n");
        return OK;
    }
    

    7.链式队列入队

    //入队
    Status PushNodeQueue(SQueue *queue, SElemType data){
        //链式队列无需判断队满
        QListNode temp = (QListNode)malloc(sizeof(QNode));
        temp->data = data;
        temp->next = NULL;
        //修改队尾指向的结点
        queue->real->next = temp;
        //更新队尾
        queue->real = temp;
        //队的长度自增1
        queue->count++;
        return OK;
    }
    

    8.链式队列出队

    //出队
    Status PopNodeQueue(SQueue *queue, SElemType *data){
        if (queue->front == queue->real) {
            printf("空队列\n");
            return ERROR;
        }
        //获得队头结点
        QListNode temp = queue->front->next;
        *data = temp->data;
        //更新队头指向的结点
        queue->front->next = temp->next;
        free(temp);
        return OK;
    }
    

    相关文章

      网友评论

          本文标题:数据结构之队列

          本文链接:https://www.haomeiwen.com/subject/rzhuohtx.html