队列

WhYqZz2025-09-032025-09-23

队列的概念

队列(Queue)是指允许在一段插入，另一端删除的线性表

重要术语

队头：允许删除的一端
队尾：允许插入的一端
空队列：队列里没有任何数据元素
特点：先进先出(FIFO)First In First Out

队列的基本操作

队列的顺序实现

队列的定义

#define MAXSIZE 10
typedef struct{
    int data[MAXSIZE];
    int front,rear;//队头指针和队尾指针
}SqQueue;

队列的初始化

void InitQueue(SqQueue &Q){
    Q.front=0;
    Q.rear=0;
}

判断队列是否为空

bool QueueEmpty(SqQueue Q){
    if(front==rear)return true;
    else return false;
}

入队

bool EnQueue(SqQueue &Q,int x){
    if((Q.rear+1)%MAXSIZE==Q.front)return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MAXSIZE;//用模运算将储存结构逻辑上变成了“环状”（循环队列）
}

出队

bool DeQueue(SqQueue &Q,int &x ){
    if(Q.front==Q.rear)return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MAXSIZE;
    return true;
}

查

bool GetHead(SqQueue Q,int &x){
    if(Q.front==Q.rear)return false;
    x=Q.data[Q.front];
    return true;
}

队列元素个数

(rear+MAXSIZE-front)%MAXSIZE

判断队列为空/已满

构造循环队列，在插入时front不能等于rear，浪费一片储存空间。

定义一个size，记录当前队列长度

typedef struct{
    int data[MAXSIZE];
    int front,rear;
    int size;
}SqQueue;
//初始化时front=rear=0，size=0
//插入成功size++,删除成功size--
//队满条件size==MAXSIZE

设置tag变量，记录最近进行的是删除还是插入操作

typedef struct{
    int data[MAXSIZE];
    int front,rear;
    int tag;
//初始化时front=rear=0，tag=0
//插入成功tag=1,删除成功tag=0
//只有插入才能队满，删除才能队空
//队满条件front==rear&&tag==1,队空条件front==rear&&tag==0
}

其他出题方法

当rear指向队尾元素而不是该插入的位置时，代码会有稍微改变
插入：

1 2	Q.rear=(Q.rear+1)%MAXSIZE; Q.data[Q.rear]=x

初始化时rear=MAXSIZE-1

队列的链式实现

链队的定义

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

链队的初始化

带头结点

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
bool QueueEmpty(LinkkQueue Q){
    if(Q.front==Q.rear)return true;
    else return false;
}//判断是否为空

不带头结点

void InitQueue(LinkQueue &Q){
    Q.front=NULL;
    Q.rear=NULL;
}
bool QueueEmpty(LinkQueue Q){
    if(Q.front==NULL)return true;
    else return false;
}//判断是否为空

入队

带头结点

bool EnQueue(LinkQueue &Q,int x){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    if(s==NULL)return false;
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
    return true;
}

不带头结点

bool EnQueue(LinkQueue &Q,int x){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    if(s==NULL)return false;
    s->data=x;
    s->next=NULL;
    if(Q==NULL){
        Q.front=s;
        Q.rear=s;
    }
    else{
        Q.rear->next=s;
        Q.rear=s;
    }
    return true;
}

出队

带头结点

bool DeQueue(LinkQueue &Q,int &x){
    if(Q.front==Q.rear)return false;
    LinkNode *p=Q.front->next;
    x=Q.front->data;
    Q.front->next=p->next;
    if(Q.rear==p)Q.front=Q.rear;
    free(p);
    return true;
}

不带头结点

bool DeQueue(LinkQueue &Q,int &x){
    if(Q.front==NULL)return false;
    LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
    p=Q.front;
    x=Q.front->data;
    Q.front=p->next;
    if(Q.front==Q.rear){
        Q.front=NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;
}