数据结构学习笔记--队列

引子：只有学习才是激情的生命，才是燃烧的岁月，才是完美的人生

声明：本笔记由《嵌入式系统软件设计中的数据结构》产生，旨在提升自己的软件设计水平，绝无侵权行为，望转载者备注说明

一 队列逻辑结构

1 是一种只允许在表的一端-“队尾“进行插入，而在另一端-”队头“进行删除的线性表。实则为线性表的一种特例。也称为先进先出表
2 当队列中没有结点时称为空队列。队列的修改是依照先进先出的原则进行的

二 队列的基本运算

置空队 SetNull(Q)：将队列 Q 置成空的队列

判队空 Empty(Q)：若 Q 为空队列，返回”真“，否则为”假“

取头结点 GetFront(Q)：读取队列 Q 的头结点的值，队列中的结点保持不变

入队 InQuery(Q, x)：将结点 x 插入到队列 Q 的队尾

出队 DeQuery(Q)：删除队列头结点

三 队列分类

1 顺序队列 

 采用顺序存储结构，实则为运算受限的顺序表，可用一维数组来存放结点数据

 front 指示队列当前队头结点的数组下标的位置

 rear 指示队列当前队尾结点的数组下标的位置

 结构描述

 +++++++++++++++++++++++++++++++++++++++++++++++

  #define maxsize 1024                                                                

  typedef int datatype;                                                                    

  typedef struct                                                                                    

  {                                                                                                       

     datatype data[maxsize];    //存放数据元素的一维数组                                                       

     int front;                                //头结点                                                       

     int rear;                                 //尾结点                                                       

  }sequery;                                                                                       

++++++++++++++++++++++++++++++++++++++++++++++++

顺序队列的队头和队尾的标志位置分析

front指向当前队列头结点的前一个位置

rear指向当前队列尾结点的位置

队列的溢出情况分析

出队运算：front++；//头指针 +1

当空队时，front = rear，若再做出队操作，会产生“下溢”

入队运算：rear++；//尾指针 +1

                    data[rear] =  x; //x 入队

当队满时，再做入队操作会产生“上溢”

假上溢 原因：被删除的结点（出队结点）的空间永远不能再使用

2 循环队列

将顺序队列首尾相连，即 data[0] 接在 data[max - 1] 之后

循环队列克服假上溢：

若当前尾指针等于数组的上界（max - 1），再做入队操作时，令尾指针等于数组的下界（0）

入队：rear = (rear + 1) % max;

            data[rear] = x;

出队：front = (front + 1) % max;

循环队列队空队满情况：

少用一个结点空间，即头结点指向的空间不使用

队空：front = rear

队满：(rear + 1) % max = front;

循环队列的运算

+++++++++++++++++++++++++++++++++++++++++++++++++++++

/* 置空队 */

void SetNull(sequeue * sq)

{

    sq- front = 0;

    sq- rear = 0;

}

/* 判队空 */

int Empty(sequeue * sq)

{

    if (sq- rear == sq- front)

        return 1;

    else

        return 0;

}

/* 取头结点 */

datatype GetFront(sequeue *sq)

{

    if (Empty(sq))

    {

        printf("queue is null");

        return(NULL);

        /**

         * For GCC Warning

         */

    }

    else

        return(sq- data[(sq- front+1)%max]);

}

/* 入队 */

int InQueue(sequeue * sq, datatype x)

{

    if ((rear + 1)%max == sq- front)

    {

        printf("queue is full");

        return(NULL);

    }

    else

    {

        sq- rear = (sq- rear+1)%max;

        sq- data[sq- rear] = x;

        return 1;

    }

}

/* 出队 */

datatype DeQueue(sequeue * sq)

{

    if (Empty(sq))

    {

        printf("queue is full");

        return(NULL);

    }

    else

    {

        sq- front = (sq- front+1)%max;

        return(sq- data[sq- front]);

    }

}

+++++++++++++++++++++++++++++++++++++++++++++++++++++

3 链队列

采用链式存储的队列，类似单链表，但其操作受限，只允许在表头删除节点和在表为插入节点

未完待续

Java数据结构之队列 队列是一个有序列表，可以用数组或是链表来实现。 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
Qz学算法-数据结构篇(稀疏数组、队列) 数据结构包括：线性结构和非线性结构。所以博主会通过这两个角度来对线性结构和非线性结构进行梳理归纳。本篇是稀疏数组和队列
【奇妙的数据结构世界】用图像和代码对队列的使用进行透彻学习 | C++ 简单来说，数据结构是一种辅助程序设计并且进行优化的方法论，它不仅讨论数据的存储与处理的方法，同时也考虑到了数据彼此之间的关系与运算，从而极大程度的提高程序执行的效率，减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用，选择合适正确的数据结构，可以让算法发挥出更大的性能，给设计的程序带来更高效率的算法。