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

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

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

一 队列逻辑结构

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 链队列

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

未完待续

时间: 2013-09-13