MENU

数据结构 - 队列

March 25, 2021 • Read: 187 • 数据结构

定义

队列(Queue)是只允许在一端进行插入,在另一端删除的线性表

重要术语:队头、队尾、空队列

image-20210323191859113

特点:先进先出(First In First Out

基本操作

InitQueue(&Q):初始化队列,构造一个空队列Q

DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间

EnQueue(&Q,x):入队,若队列未满,将x加入,使之成为新的队尾

DeQueue(&Q,&x):出队,若队列Q非空,删除队头元素,并用x返回。

GetHead(Q,&x):读队头元素,若队列Q非空,则将队头元素赋值给x.

存储结构

顺序存储结构

定义

// 队列的顺序存储定义

#define MaxSize 10        // 定义队列中元素的最大个数
typedef struct {        
    int data[MaxSize];    // 用静态数组存放队列元素
    int front, rear;    // 队头指针和队尾指针
}SqQueue;

初始化

// 初始化队列
void InitQueue(SqQueue &Q) {
    // 初始时 队头  队尾指针指向0
    Q.rear = Q.front = 0;
}

判断队列为空

// 判断队列是否为空
bool QueueEmpty(SqQueue Q) {
    if (Q.rear == Q.front) {
        return true;    // 队空的条件
    }
    else {
        return false;
    }
}

入队

// 入队
bool EnQueue(SqQueue &Q, int x) {
    if ((Q.rear+1)%MaxSize==Q.front) {        // 队列已满的条件:队尾指针的在下一个位置的队头,即 (Q.rear+1)%MaxSize==Q.front
        return false;        // 队满报错
    }
    Q.data[Q.rear] = x;        // 将x插入队尾
    Q.rear = (Q.rear + 1)%MaxSize;    // 队尾指针后移   当队尾指针指向队尾,队头还有位置的时候,
                                    // 可以使用取余的操作,将元素放在队头    
    return true;
}

上面的逻辑情况类似是现实了一个循环队列,为了和队列为空的情况,一般会牺牲一个节点为代价

image-20210324204731945

队列的元素个数为:(rear+MaxSize-front)%MaxSize

若要求不能浪费队列中的每一块存储空间,可以如下的修改队列的定义

typedef struct {
    ElemType data[MaxSize];
       int front, rear; 
    int size;    // 队列当前长度,初始化的时候可以 front = rear = 0; size =0 
}SqQueue;

出队

// 出队
bool DeQueue(SqQueue &Q, int &x) {
    if (Q.rear == Q.front) {
        return false;    // 判断为空
    }
    x = Q.data[Q.front];    // 队头元素出队
    Q.front = (Q.front + 1) % MaxSize;    // 队头指针后移
    return true;
}

获取队头元素

// 获取队头元素的值,用x返回
bool getHead(SqQueue Q,int &x) {
    if (Q.rear = Q.front) {
        return false;    // 队空报错
    }
    x = Q.data[Q.front];
    return true;
}

链式储存结构

这种存储结构分别有两种:带头节点和不带头结点的形式!

定义

typedef struct LinkNode { //链式队列节点
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct {    // 链式队列
    LinkNode * front, *rear;        //队列的队头指针和队尾指针
}LinkQueue;

初始化

 // 初始化(带头节点)
void InitQueueWithHead(LinkQueue &Q) {
    // 初始时 front rear 都指向头节点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

// 初始化(不带头结点)
void InitQueueNoHead(LinkQueue &Q) {
    Q.front = NULL;
    Q.rear = NULL;
}

判断为空

// 判断队列是否为空(带头节点)
bool IsEmptyWithHead(LinkQueue Q) {
    if (Q.front==Q.rear) {
        return true;
    }
    else {
        return false;
    }
}

// 判断队列是否为空(不带头节点)
bool IsEmptyNoHead(LinkQueue Q) {
    if (Q.front==NULL) {
        return true;
    }
    else {
        return false;
    }
};

入队

// 入队(带头节点)
void EnQueueWithHead(LinkQueue &Q,int x) {
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;        // 入队的节点为最后一个节点
    Q.rear->next = s;    // 新节点插到rear之后
    Q.rear = s;        // 修改表尾指针
}

// 入队(不带头节点)
void EnQueueNoHead(LinkQueue &Q, int x) {
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if (Q.front == NULL) {    // 在空队列中插入第一个元素
        Q.front = s;        // 修改队头指针为插入的元素
        Q.rear = s; // 修改队尾指针为插入的元素
    }
    else {
        Q.rear->next = s;    // 将新节点指向插入到rear的结点之后
        Q.rear = s;
    }
}

出队

// 出队(带头节点)
bool DeQueue(LinkQueue &Q, int &x) {
    if (Q.front==Q.rear) {
        return false;        // 空队
    }
    LinkNode *p = Q.front->next;
    x = p->data;            // 用变量x返回头节点
    Q.front->next = p->next;// 修改头节点的next指针
    if (Q.rear==p) {        // 此次是最后一个节点出队
        Q.rear = Q.front;    // 修改rear指针
    }
    free(p);                // 释放节点空间
    return true;
}

// 出队(不带头节点)
bool DeQueue(LinkQueue &Q, int &x) {
    if (Q.front == NULL) {
        return false;        // 当前为空队
    }
    LinkNode *p = Q.front;  // p指向此次出队的节点
    x = p->data;            // 用变量x返回队头元素    
    Q.front = p->next;        // 修改front指针    
    if (Q.rear == p) {        // 如果当前出队的队尾节点 
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(p);                // 释放节点空间
    return true;
}

双端队列

定义: 双端队列:只允许从两端插入、两端删除的线性表

输入受限的双端队列:只允许在一端插入、两端删除的线性表
输出受限的双端队列:只允许在一端删除、两端插入的线性表

版权声明:文章转载请注明来源,如有侵权请联系删除!

Last Modified: April 12, 2021
Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. 感谢分享 赞一个

    1. @北京艺术培训#(献花)