《数据结构》-第三章 栈和队列（知识点总结-下）_数据结构队列和栈ppt下载

写在前面的话：

      适应范围：《数据结构》复习总结系列适用于考研、期末考试、考前复习，小白新手

      本系列参考书目： 《数据结构：c语言版》（严蔚敏）

---

【目录】

第三章 栈和队列-（队列）

一、队列

1.1 队列的定义与特点

1.2 队列的结构

1.3 队列的特点

二、队列的顺序存储

2.1 循环队列相关概念

2.2循环队列的存储结构表示

2.3 循环队列中基本操作的实现

2.3.1 队列的初始化

2.3.2 求队列长度（⭐⭐⭐）

2.3.3 入队（⭐⭐⭐）

2.3.4 出队（⭐⭐⭐）

三、 链队的链式存储

3.1 链队相关概念

3.2链队的存储结构表示

3.3 链队中基本操作的实现

3.3.1 链队的初始化

3.3.2 入队（⭐⭐⭐）

3.3.3 出队（⭐⭐⭐）

四、 双端队列（考研知识点）

---

第三章 栈和队列-（队列）

一、队列

1.1 队列的定义与特点

【定义】只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表。

1.2 队列的结构

【逻辑结构】作为只能对一端插入一端删除操作的线性表，其结构仍然遵循线性表的一对一关系

【存储结构】使用顺序存储-顺序表或链式存储-链表存储均可。

1.3 队列的特点

【特点】只能在队列一端进另一端出，且访问结点时先进先出（FIFO）

---

二、队列的顺序存储

2.1 循环队列相关概念

 【定义】 循环队列是队列的顺序表示方式，和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个整型变量front 和rear分别指示队列头元素及队列尾元素的位置(后面分别称为头指针和尾指针)。

【问题】如图所示，图一情况中，frint=0，rear=M时，若此时还有元素需要入队，此时空间已占满，则为真溢出；当front不为0，而rear因元素不断入队，rear=M时，此时空间还远远未满，但按照之前的判断方式此队列已满，此种情况为假溢出。那么如何解决这种情况呢？

【解决】正是为解决假溢出问题，将顺序队列进行头尾相接，转变为一个环状队列即循环队列。头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1"的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式”循环＂移动。

       此时对于“问题”中举出的实例解决方法就变成了队头元素是J5，在元素J6入队之前，在Q.rear的值为5，当元素J6入队之后，通过“模”运算，Q.rear = (Q.rear +1)%6，得到Q.rear的值为0,而不会出现“假溢出”状态。

      但在这种情况下，对于循环队列不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”。通常有以下几种处理方法。

【“模”运算】入队：  base[rear]=x;   rear=(rear+1)%M;

                    出队：  x=base[front];   front=(front+1)%M;

2.2循环队列的存储结构表示

【算法描述】

#define MAXQSIZE  100  //最大长度
Typedef struct {
   QElemType *base;  //初始化的动态分配存储空间
   int  front;            //头指针   
   int  rear;             //尾指针
}SqQueue;  

2.3 循环队列中基本操作的实现

2.3.1 队列的初始化

【算法思想】①为队列分配-一个最大容量为MAXSIZE的数组空间，base指向数组空间的首地址。
                     ②头指针和尾指针置为零，表示队列为空。

【算法描述】

Status InitQueue (SqQueue &Q){
    Q.base =new QElemType[MAXQSIZE]  //为队列分配MAXSIZE大小容量
   if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;               //队列置空
    return OK;
}

2.3.2 求队列长度（⭐⭐⭐）

【算法思想】为避免差值可能为负数,将尾指针和头指针差值加上MAXQSIZE,然后与MAXQSIZE求余。

【算法描述】

int  QueueLength (SqQueue Q){
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;                             
 }

2.3.3 入队（⭐⭐⭐）

【算法思想】①判断队列是否满，若满则返回ERROR。
                    ②将新元素插人队尾。
                    ③队尾指针加1。

【算法描述】

Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;   //判断队满
    Q.base[Q.rear]=e;   //新元素插入队尾
    Q.rear=(Q.rear+1)%MAXQSIZE;  //队尾指针+1
     return OK;
}

2.3.4 出队（⭐⭐⭐）

【算法思想】①判断队列是否为空，若空则返回ERROR。
                     ②保存队头元素。
                     ③队头指针加1。

【算法描述】

Status DeQueue (SqQueue &Q,QElemType &e){
   if(Q.front==Q.rear) return ERROR;   //判断是否队空
   e=Q.base[Q.front];                  //保存队头元素
   Q.front=(Q.front+1)%MAXQSIZE;      //队头指针+1
   return OK;
}

---

三、 链队的链式存储

3.1 链队相关概念

  链队是指采用链式存储结构实现的队列，通常链队用单链表来表示，一个链队显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。与单链表一样，为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。

3.2链队的存储结构表示

typedef struct QNode{
   QElemType   data;
   struct Qnode  *next;
}Qnode, *QueuePtr;
typedef struct {
   QueuePtr  front;            //队头指针   
   QueuePtr  rear;             //队尾指针
}LinkQueue;  

3.3 链队中基本操作的实现

3.3.1 链队的初始化

【算法思想】①生成新结点作为头结点，队头和队尾指针指向此结点。
                     ②头结点的指针域置空。

【算法描述】

Status InitQueue (LinkQueue &Q){
   Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); //生成新结点，并使用头尾指针都指向结点
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;    //头结点指针域置空
     return OK;
}

3.3.2 入队（⭐⭐⭐）

【算法思想】①为入队元素分配结点空间，用指针p指向。
                     ②将新结点数据域置为e。
                     ③将新结点插人到队尾。
                     ④修改队尾指针为p。

【算法描述】

Status EnQueue (LinkQueue & Q, QElemType e)
{
   p-new QNode;    //为入队元素分配结点空间，用指针p指向
   p->data=e;      //将新结点数据城置为e
   p->next=NULL;
   Q. rear ->next=P;//将新结点插入到队尾
   Q. rear=p;      //修改队尾指针
   return OK;
}

3.3.3 出队（⭐⭐⭐）

【算法思想】①判断队列是否为空，若空则返回ERROR。

                    ②临时保存队头元素的空间，以备释放。

                    ③修改队头指针,指向下一个结点。

                    ④判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值,指向头结点。

                    ⑤释放原队头元素的空间。

【算法描述】

Status DeQueue (LinkQueue &Q, QElemType &e)
{
    if(Q. front--Q.rear) return ERROR;  //若队列空，则返回ERROR
    p=Q. front->next;                   //p指向队头元素
    e=p->data;                          //e保存队头元素的值
    Q. front->next-p->next;             //修改头指针
    if(Q.rear--p) Q.rear-Q. front;      //最后一个元素被删，队尾指针指向头结点
    delete p;                           //释放原队头元素的空间
    return OK;
}

---

四、 双端队列（考研知识点）

   【双端队列】是指允许两端都可以进行入队和出队操作的队列，如图所示。其元素的逻辑结
构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

   【输出受限的双端队列】允许在一端进行插入和删除，但在另一端只 允许插入的双端队列称为
输出受限的双端队列，如图。

   【输入受限的双端队列】允许在一端进行插入和删除， 但在另一端端 只允许删除的双端队列称为输入受限的双端队列，如图。若限定双端队列从某个端点插入的元素只能从该端点删除，
则该双端队列就蜕变为两个栈底相邻接的栈。

（注：双端队列考题常以选择题或填空题出现，算法题出现概率不大）