数据结构-队列

队列(queue)是一种只允许再表的一段进行插入,而在另一端删除元素的线性表。

队列的特性:先进先出(FIFO)。典型例子为排队,先排的先受到服务先离开,后排的后受到服务后离开

队列的基本运算

InitQueue(&Q):
初始化队列Q

QueueEmpty():
判断队列是否为空

EnQueue(e):
将元素e放入队尾

DeQueue(e):
移走队头元素,由e带回该元素的值

GetFront():
获取队头元素的值,但不从队列中移走该元素

Length(): 计算并返回队列中元素的个数

队列分为链队列和循环队列

链队列——队列采用链式存储结构(单链表,单向循环链表)

循环队列——队列采用顺序存储结构

链队列的C语言实现

//单链表队列的存储结构
typedef struct QNode{      //链表结点类型
    QElemType data;  
    struct QNode *next;
}QNode, *QueuePtr;

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

链队列基本操作的实现

(1)初始化

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

(2)入队

Status EnQueue(LinkQueue &Q, QElemType e){
    //将元素e插入刀队列Q中
    p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        return (OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

(3)出队列

Status DeQueue(LinkQueue &Q, QElemType &e){
    //若队列不为空,则对头元素出队列,用e带回其值,返回OK
    //否则返回ERROR
    if (Q.rear == Q.front)
    return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)     //如果p到了队尾
        Q.rear = Q.front;
    free(p);
    return OK;
}

一句记忆:尾加头减(入队列是在队尾加入结点,出队列是将头节点上的节点弹出)

循环队列的存储结构

typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

循环队列的基本操作实现

(1)初始化

Status InitQueue(SqQueue &Q){    //构造一个空队列
    Q.base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType));
    if (!Q.base)
        return OVERFLOW;
    Q.front = Q.rear = 0;
    return OK;
}


队头元素指示Q.front = 0

队尾元素指示Q.rear = 0

队列满的条件:Q.rear = MAXSIZE

队列长度:Q.rear – Q.front

队头元素: Q.base[Q.front]

队尾元素: Q.base[Q.rear]

使用链队列会有假溢出的风险,故使用循环队列解决

解决思路:

将队列空间堪称是环形结构,初始时:Q.rear = Q.front = 0

当Q.rear等于MAXSIZE时,将其置为0,即令Q.rear = 0;或者Q.rear = Q.rear % MAXSIZE

(Q.front同理)

队头元素:Q.base[Q.front]

入队:

Q.base[Q.rear]= e;

Q.rear = (Q.rear + 1) % MAXSIZE;

当队列空间全部被占用(队满),此时 Q.rear == Q.front

出队:

e = Q.base[Q.front];

Q.front = (Q.front + 1) % MAXSIZE;

当队列元素全部出来(队空),此时 Q.front == Q.rear (不一定是位置0)

注:当 Q.rear == Q.front 时,可能是队列满,也可能是队列空,区分方法有:

方法(1)·设置一个队列长度计数器Q.length,初始值为0(队列空)

·当一个元素入队列时,Q.length加1

·当一个元素出队列时,Q.length减1

//循环队列的存储结构定义改变
typedef struct{
    QElemType *base;
    int front;
    int rear;
    int length;
}SqQueue;

方法(2):令队列空间中的一个单元闲置,使得在非空队列中Q.rear与Q.front不同

//循环队列的存储结构定义
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

此时:

队列满: (Q.rear + 1) % MAXSIZE == Q.front

队列空:    Q.rear == Q.front

队列长度: (Q.rear – Q.front + MAXSIZE) % MAXSIZE

(接上面的 循环队列基本操作的实现 )

(2)入队

Status EnQueue(SqQueue &Q, QElemType e){
    //将元素e插入队列Q的队尾
    if ((Q.rear + 1) % MAXSIZE == Q.front)
        return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

(3) 出队

Status DeQueue(SqQueue &Q, QElemType &e){
    //删除队列Q的队头元素并用e带回
    if (Q.front == Q.rear)
        return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注