链式存储队列

543 阅读2分钟

队列的链式存储结构,简单看来和线性表的单链表非常相似,只不过,链式存储的队列,只可以在队尾rear入队,队头front出队。

同样为了方便,在队列前添加头结点。

   1.1 链式存储队列结构设计:

// 结点结构
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QListNode;
// 队列链表结构
typedef struct {
    QListNode front; // 队头
    QListNode rear;  // 队尾
}SqQueue;
   1.2 初始化队列 

将队列的front,rear都指向新建的头结点。


// 初始化
Status InitQueue(SqQueue *Q){    
    Q->front = Q->rear = (QListNode)malloc(sizeof(QListNode));
    if (!Q->front) {
        return ERROR;
    }
    Q->front->next = NULL;  // 头结点的指针域置空 此处Q->rear的next同样指向空
    return OK;
}


   1.3 添加入队,只需要调整rear就可以,front始终指向头结点。


// 添加元素
Status EnterQueue(SqQueue *Q,QElemType e){
    
    if (!Q) {
        return ERROR;
    }
    
    QListNode temp = (QListNode)malloc(sizeof(QNode));
    if (!temp) {
        return ERROR;
    }
    temp->data = e;
    temp->next = NULL;  // 要将新结点的next指向空,以免脏数据
    
    Q->rear->next = temp;
    Q->rear = temp;     // 调整rear 指向最新的结点
    return OK;
}



   1.4 删除出队

删除要注意两个条件:

  • 删除前判断队列是否是空的
  • 判断要删除的是不是最后一个元素


// 删除
Status DeleteQueue(SqQueue *Q,QElemType *e){
    if (!Q) {
        return ERROR;
    }
    if (Q->front == Q->rear) {  // 判断是否为空
        printf("队列已空\n");
        return ERROR;
    }

    QListNode temp = Q->front->next;
    *e = temp->data;
    Q->front->next = temp->next; // 要把头结点的next指向要删除结点的next
    
    if (Q->rear == temp) {   // 假如要删除的是最后一个,要把rear指向头结点
        Q->rear = Q->front;
    }
    
    free(temp);    
    return OK;
}


   1.5 遍历所有元素

// 遍历
Status QueueTrave(SqQueue Q){

    QListNode temp = Q.front->next;
    while (temp) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
    
    return OK;
}


   1.6 队列长度

通过遍历每一个结点,计算遍历的次数,来获取队列的长度。

获取队列长度也可以在设计队列时,添加count,每次入列出列进行count加减

// 队列长度  
int QueueLength(SqQueue Q){
    if (Q.front != Q.rear) {
        QListNode temp = Q.front->next;
        int count = 0;
        while (temp) {
            count++;
            temp = temp->next;
        }
        return count;
    }
    return 0;
}


   1.7 队列清空

  1. 将rear重新指向头结点
  2. 遍历所有的结点,free掉
  3. 将front的next指向为null

// 清空
Status ClearQueue(SqQueue *Q){
    if (!Q) {
        return ERROR;
    }
    
    if (Q->front == Q->rear) { // 判断队列是否为空
        return ERROR;
    }
    Q->rear = Q->front;  
    
    QListNode temp = Q->front->next;
    while (temp) {
        QListNode p = temp->next;
        free(temp);
        temp = p;
    }
    
    Q->front->next = NULL;
    return OK;
}


   1.8 销毁队列

// 销毁
Status DestoryQueue(SqQueue *Q){
    
    QListNode temp = Q->front;
    while (temp) {
        QListNode p = temp->next;
        free(temp);
        temp = p;
    }
    
    /*  销毁不用在意front rear ,所以也可以不用太多其它的参数,如下
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }*/
    
    return OK;
}