数据结构

数据结构笔记——队列

概念

  • 是一种先进来的先出去的线性表

  • 再表尾插入，再表头删除

循环队列

typedef struct{
    QElemType *base;//数组
    int front;
    int rear;

}SqQueue;

链式队列

typedef struct QNode{
    QElemType data;
    QNode *next;
}QNode;

typedef struct LinkedQueue{
    QNode *front; //链表的头指针
    QNode *rear; //指向链表的最后一个节点
}LinkedQueue;

基本操作

循环队列

在对队列进行操作的时候，我们为了解决假溢出的情况，我们可以将整个队列看作一个环状，本质是当游标到达尾部后复位

//入队
base[rear] = x;
rear = (rear + 1) % M;
//出队
base[front] = x;
front = (front + 1) % M;

那么如何判断队列已经满了呢？我们少使用一个元素空间，那么档队列为空时front==rear ，队列满时(rear+1)%M==front

循环队列初始化

Status InitQueue(SqQueue *Q){
    Q->base=(QElemType*)malloc(sizeof(QElemType)*MAXQSIZE);
    if(Q->base==NULL){
        return OVERFLOW;
    }
    Q->front=Q->rear=0;
    return OK;
}

循环队列求长度

int QueueLenth(SqQueue *Q){
    return((Q->rear-Q->front+MAXQSIZE)%MAXQSIZE);
}

循环队列入队

Status EntryQueue(SqQueue *Q,QElemType e){
    if((Q->rear +1)%MAXQSIZE==Q->front){ //队列已满
        return ERROR;
    }
    Q->base[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXQSIZE;
    return OK;
}

循环队列出队

Status OutQueue(SqQueue *Q,QElemType *e){
    if(Q->rear ==Q->front){ //队列为空
        return ERROR;
    }
    *e=Q->base[Q->front];
    Q->front=(Q->front+1)%MAXQSIZE;
    return OK;
}

链队入队

Status EntryQueue_L(LinkedQueue *Q,QElemType e){
    QNode *node=(QNode*)malloc(sizeof(QNode));
    if(node==NULL){
        return OVERFLOW;
    }
    node->data=e;
    node->next=NULL;
    Q->rear->next=node;
    Q->rear=node;
    return OK;
}

链队出队

Status OutQueue_L(LinkedQueue *Q,QElemType *e){
    if(Q->front==Q->rear){
        return ERROR;
    }
    QNode *node=Q->front->next;
    *e=node->data;
    Q->front->next=node->next;
    if(Q->rear==node){ //队列中最后一个离开，则变为空队列
        Q->rear=Q->front;
    }
    free(node);
    return OK;
}

Comment