大话数据结构--栈与队列

栈与队列

• 总目录
• 前言
• 四、栈与队列
• 4.1 初始栈与队列
• 4.2 栈的定义

• 4.2.1 栈的定义

• 1.一些要注意的点

• 4.2.2 进栈出栈变化形式

• 4.3栈的抽象数据类型
• 4.4栈的顺序存储结构及实现

• 4.4.1栈的顺序存储结构
• 4.4.2栈的顺序存储结构--进栈操作
• 4.4.3栈的顺序存储结构--出栈操作

• 4.5 两栈共享空间
• 4.6栈的链式存储结构及实现

• 4.6.1栈的链式存储结构
• 4.6.2栈的链式存储结构一进栈操作
• 4.6.3栈的链式存储结构一出栈操作

• 4.7栈的作用

• 4.8栈的应用—递归
• 4.8.1 斐波那契数列实现

• 用迭代实现
• 用递归实现

• 4.8.2递归定义

• 4.9 队列的定义
• 4.10队列的抽象数据类型
• 4.11 循环队列
• 4.11.1队列顺序存储的不足

• 4.11.2 循环队列的定义

• 4.12 队列的链式存储结构及实现

• 4.13.1队列的链式存储结构一入队操作
• 4.13.2队列的链式存储结构一出队操作

• 4.13总结回顾

总目录

​​一、数据结构概述​​二、算法概述
三、线性表

前言

​

提升编程基础能力
数据结构、操作系统、计租、网络
陆续会慢慢更新！

资料获取

四、栈与队列

4.1 初始栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许再一端进行插入操作、而在另一端进行删除操作的线性表

4.2 栈的定义

4.2.1 栈的定义

栈的结构类似与弹夹中的子弹，先进去的后出来，后进去的先出来。这就是数据结构中的栈。

生活中，栈这种后进先出数据结构的应用是非常普遍的。像常用的浏览器后面都会有后退键，你点击后可以按访问顺序的逆序加载浏览过的网页。

还有常用的Office都会有撤销的操作。不同软件具体实现代码会有所不同，原理都差不多

栈（stack）是限定仅在表位进行插入和删除操作的线性表

​ 把允许插入和删除的一端称为栈顶(top), 另一端称为栈底(bottom), 不
含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构

1.一些要注意的点

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得:栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹

栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹

4.2.2 进栈出栈变化形式

最先进栈的元素，是不是就只能是最后出栈呢?

答案是不一定，要看什么情况。栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

举例来说，如果现在是有3个整型数字元素1、2、3依次进栈，会有哪些出栈次序呢?

第一种: 1、2、3进，再3、2、1出。这是最简单的最好理解的一种，出栈
次序为321

第二种: 1进，1出，2进, 2出，3进，3出。也就是进一个就出一个，出
栈次序为123

第三种: 1进，2进，2出，1出，3进，3出。出栈次序为213

第四种: 1进，1出，2进，3进，3出，2出。出栈次序为132

第五种: 1进，2进，2出，3进，3出，1出。出栈次序为231

有没有可能是312这样的次序出栈呢?答案是肯定不会。因为3先出栈，就意味着，3曾经进栈，既然3都进栈了，那也就意味着，1和2已经进栈了，此时，2一定是在1的上面，就是更接近栈顶，那么出栈只可能是321,不然不满足123依次进栈的要求，所以此时不会发生1比2先出栈的情况。

4.3栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop,英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

ADT栈(stack)
Data
  同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
  InitStack (*s):初始化操作，建立一个空栈S。
  DestroyStack(*s) :若栈存在，则销毁它。
  ClearStack (*s) :将栈清空。
  StackEmpty(s) :若栈为空，返回true,否则返回false。
  GetTop(s,*e) :若栈存在且非空，用e返回S的栈顶元素。
  Push(*s,e):若栈S存在，插入新元素e到栈S中并成为栈顶元素。
  Pop(*S,*e) :删除栈S中栈顶元素，并用e返回其值。
  StackLength(s) :返回栈S的元素个数。
endADT

由于栈本身就是一个线性表，那么上一章讨论了线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

4.4栈的顺序存储结构及实现

4.4.1栈的顺序存储结构

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。线性表是用数组来实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好?

对，没错，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。

我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，它可以来回移动，意味着栈顶的top 可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize, 则栈顶位置top必须小于StackSize。 当栈存在一个元素时，top 等于0,因此通常把空栈的判定条件定为top等于-1。

typedef int SElemType;    /* SElemType 类型根据实际情况而定，这里假设为int */
typedef struct
{
SElemType data[MAXSIZE];
int top;    /*用于栈顶指针*/
} SqStack;

若现在有一个栈，StackSize 是5,则栈普通情况、空栈和栈满的情况示意图

4.4.2栈的顺序存储结构–进栈操作

对于栈的插入，即进栈操作，其实就是做了下面的处理

/*插入元素e为新的栈顶元素*/
Status Push ( SqStack *S, SElemType e)
{
  if (S->top == MAXSIZE -1)  //栈满
  {
    return ERROR;
  }
  s->top++;    /*栈顶指针增加一/
  S->data[S->top]=e;    /*将新插入元素赋值给栈顶空间,将To*/ 
  return OK;
}

4.4.3栈的顺序存储结构–出栈操作

/*插入元素e为新的栈顶元素*/
Status Push ( SqStack *S, SElemType e)
{
    if (S->top -- MAXSIZE -1)    //栈满
    {
        return ERROR;
    }
    *e = s->data[s->top]  /*将要删除的栈顶元素赋值给e*/
    s->top--;        /*栈顶指针减一/
    return OK;
}

两者没有涉及到任何循环语句，因此时间复杂度均是o(1)

4.5 两栈共享空间

​ 其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表
插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。

做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素,就是两端点向中间延伸。

其实关键思路是:它们是在数组的两端，向中间靠拢。top1 和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。

从这里也就可以分析出来，栈1为空时，就是top1等于-1时;而当top2等于n时，即是栈2为空时，那什么时候栈满呢?

想想极端的情况，若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2 等于0时，为栈2满。但更多的情况，其实就是刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即top1 + 1 == top2 为栈

代码实现如下：

typedef struct StackNode
{
  SElemType data;
  struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
  LinkStackPtr top;
  int count;
} LinkStack;

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下:

/*插入元素e为新的栈顶元素*/
Status Push ( SqDoubleStack *S, SElemType e,int stackNumber )
{
    if(s->top1+1==s->top2) /*栈已满，不能再push新元素了*/
        return ERROR;
    if ( stackNumber==1 )   /*栈1有元素进栈*/
        S->data[++S->top1]=e; /*若栈1则先top1+1后给数组元素赋值*/
    else if ( stackNumber==2)   /*栈2有元素进栈*/
        S->data[--s->top2]=e;/*若栈2则先top2-1后给数组元素赋值*/
    return OK;
}

​ 因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担
心溢出问题的。

对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber,

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR */
Status Pop ( SqDoubleStack *S, SElemType *e, int stackNumber )
{
    if( stackNumber==1 )
    {
        if (s->top1==-1)
            return ERROR;   /*说明栈1已经是空栈，溢出*/
        *e=S->data[s->top1--]; /*将栈1的栈顶元素出栈*/
    }
    else↓if( stackNumber==2 )
    {   
        if(s->top2==MAXSIZE )
            return ERROR;   /*说明栈2已经是空栈，溢出*/
        *e=S->data[s->top2++]; /* 将栈2的栈顶元素出栈*/
    }
    return OK;
}

4.6栈的链式存储结构及实现

4.6.1栈的链式存储结构

栈的链式存储结构，简称为链栈

栈只是栈顶来左插入和删除操作，栈顶放在链表的头部还是尾部？由于单链表有头指针，而栈顶指针也是必须的，可以把他们合二为一，所以最好的办法是把栈顶放在单链表的头部，所以对于链栈来说，是不需要头结点的

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。

代码实现

typedef struct StackNode
{
    SElemType data;
    struct用StackNode *next;
} StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
} Linkstack;

链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。

4.6.2栈的链式存储结构一进栈操作

对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针

/*插入元素e为新的栈顶元素*/Status Push ( Linkstack *S, SElemType e){ LinkStackPtr s= ( LinkStackPtr ) malloc (sizeof ( StackNode) ) ;  s->data=e;    s->next = s->top //把当前的栈顶元素赋值给新节点的直接后继    S->top=s; /*将新的结点s赋值给栈顶指针*/ S->count++;    //将新的结点s赋值给栈顶指针 return OK;}

4.6.3栈的链式存储结构一出栈操作

至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR */Status Pop ( LinkStack *S, SElemType *e){    LinkStackPtr P;    if ( StackEmpty(*S))      return ERROR;    *e=S->top->data;    p=S->top; /*将栈顶结点赋值给p*/    s->top=s->top->next;  /*使得栈顶指针下移一位，指向后一结点*/    free (p) ; /*释放结点p */    S->count--;    return OK;}

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为0(1)。对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为0(1)。 对于空间性能，顺序栈需要事先确定一个 固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

4.7栈的作用

用数组或链表直接实现功能不就行了吗?干吗要引入栈这样的数据结构呢?这个问题问得好。其实这和我们明明有两只脚可以走路，干吗还要乘汽车、火车、飞机一样。理论上，陆地上的任何地方，你都是可以靠双脚走到的，可那需要多少时间和精力呢?我们更关注的是到达而不是如何去的过程。栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。所以现在的许多高级语言，比如Java、 C#等都有对栈结构的封装，你可以不用关注它的实现细节，就可以直接使用Stack的push和pop方法，非常方便。

4.8栈的应用—递归

​ 栈有一个很重要的应用:在程序设计语言中实现了递归。那么什么是递归呢?
​ 当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”。为什么会有这么奇妙的现象呢?原来，A镜子里有B镜子的像，B镜子里也有A镜子的像，这样反反复复，就会产生一连串的“像中像”。这是一种递归现象！

哈哈哈好有意思啊！

4.8.1 斐波那契数列实现

就是那个兔子生兔子的问题啦，原来在b站学习的时候都会有讲这个例子~

斐波那契数列的特点就是：前面相邻两项之和，构成了后一项

用迭代实现

int main( ){    int i;    int a[40];    a[0]=0;    a[1]=1;    printf ("%d ",a[0]) ;    printf ("&=%d ",a[1]) ;    for (i=2;i< 40;i++ )    {        a[i]= a[i-1] + a[i-2];        printf ("%d ",a[i] ) ;    } return 0;}

用递归实现

int Fbi ( int i){ if(!i<2)   return i== 0?0 :1;  return Fbi (i-1)+ Fbi (i-2) ;/*这里Fbi就是函数自己，它在调用自己*/ }int main ( ){  int i;  for (int i= 0;i < 40;i++ )   printf ("&d "，Fbi(i)) ; return 0;

4.8.2递归定义

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得i<2的，这样就可以执行return i的语句而不用继续递归了。

对比了两种实现斐波那契的代码。迭代和递归的区别是:迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

4.9 队列的定义

生活中的实例

电脑有的时候会处于疑似死机的状态，鼠标点什么都没用，刚准备重启的时候它又突然好起来了，然后将我们点击的所有操作都按顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输入，而按先后次序排队等待造成的

还有平时我们打客服电话的时候，需要排队等待

​ 操作系统和客服系统中，都是应用了一种数据结构来实现刚才提到的先进先出的
排队功能，这就是队列。

队列（queue）是允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出（First In First Out）的线性表，简称FIFO

回顾我们上面学的栈是后进先出哦

队列在程序设计中用得非常频繁。前面我们已经举了两个例子，再比如用键盘进行各种字母或数字的输入，到显示器上如记事本软件上的输出，其实就是队列的典型

4.10队列的抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队
尾进行，删除数据只能在队头进行。

ADT队列( Queue )Data  同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。Operation    InitQueue (*Q) :初始化操作，建立一个空队列Q。    DestroyQueue (*Q) :若队列Q存在，则销毁它。    ClearQueue (*Q) :将队列Q清空。    QueueEmpty (Q) :若队列Q为空，返回true,否则返回false。    GetHead (Q,*e) :若队列Q存在且非空，用e返回队列e的队头元素。    EnQueue (*Q,e) :若队列Q存在，插入新元素e到队列Q中并成为队尾元素。    DeQueue (*Q,*e):删除队列Q中队头元素，并用e返回其值。    QueueLength(Q) :返回队列Q的元素个数endADT

4.11 循环队列

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。我们先来看队列的顺序存储结构。

4.11.1队列顺序存储的不足

我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O（1）

​ 与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着,
队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为
空，此时时间复杂度为0(n)

在现实中也是如此，一群人在排队买票，前面的人买好了离开，后面的人就要全部向前一步，补上空位，似乎这也没什么不好。

那能不能出队列的时候，后面的元素不存储再数值的前n个单元这一条件，出队列的性能就会大大增加。也就是说，对头不需要一定在下标为0的位置

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front 指针指向队头元素，rear 指针指向队尾元素的下一-个位置，这样当front等于rear时，此队列不是还剩-一个元素，而是空队列。

假设是长度为5的数组，初始状态，front 与rear指针均指向下标为0的位置。然后入队a1、a2、a3、 a4, front 指针依然指向下标为0位置，而rear指针指向下标为4的位置

出队a1、a2, 则front指针指向下标为2的位置，rear 不变,再入队as,此时front指针不变，rear 指针移动到数组之外。嗯?数组之外,那将是哪里?

问题还不止于此。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做**“ 假溢出”。**

现实当中，你上了公交车，发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做?立马下车，并对自己说，后面没座了，我等下一辆?没有这么笨的人，前面有座位，当然也是可以坐的，除非坐满了，才会考虑下一辆。

4.11.2 循环队列的定义

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

上面的例子继续，rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了

​ 接着入队a6,将它放置于下标为0处，rear指针指向下标为1处，若再入队a7，则rear指针就与front指针重合，同时指向下标为2的位
置

此时问题又出来了，我们刚才说，空队列时，front 等于rear, 现在当队列满时，也是front等于rear,那么如何判断此时的队列究竟是空还是满呢?

办法一个标志变量flag,当front == rear,且flag = 0时为队列空，当frnotallow== rear,且fag= 1时为队列满。

办法二是当队列空时，条件就是front = rear,当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。我们就认为此队列已经满了，也就是说，我们不允许如下右图的情况出现

队列满的条件是（rear + 1） % QueueSize == front(取模的目的就是为了整合rear与front大小为一个问题)

我们可以根据图，求出队列中的元素

当rear>front时，队列中的元素个数为rear - front

当rear<front时，队列中的元素个数为两段，一段为QueueSize - front,另一段为0 + rear

这两段加起来为rear - front + QueueSize

.通用的计算队列长度的公式为：

（rear - front + QueueSize） % QueueSize

循环队列的顺序结构代码如下：

typedef int QE1 emType; /* QElemType类型根据实际情况而定，这里假设为int *//*循环队列的顺序存储结构*/typedef struct{    QE1 emType data [MAXSIZE];    int front;/* 头指针*/    int rear;/*尾指针，若队列不空，指向队列尾元素的下一个位置*/} SqQueue;

初始化代码

/*初始化一个空队列Q*/Status InitQueue ( SqQueue *Q ){    Q->frnotallow=0;    Q->rear=0;  return  OK;}

循环队列求队列长度代码如下：

/*返回Q的元素个数，也就是队列的当前长度*/int QueueLength ( SqQueue Q){    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}

循环队列的入队列操作代码如下:

/*若队列未满，则插入元素e为Q新的队尾元素*/Status EnQueue ( SqQueue *Q, QElemType e ){if((Q->rear+1) %MAXSIZE == Q->front)   /*队列满的判断*/  return ERROR; Q->data[Q->rear]=e;   /* 将元素e赋值给队尾*/  Q->rear=(Q->rear+1)%MAXSIZE;  /*rear 指针向后移一位置，若到最后则转到数组头部*/return OK;}

循环队列的出队列操作代码如下:

/*若队列不空，则删除Q中队头元素，用e返回其值*/Status DeQueue ( SqQueue *Q, QElemType *e){    if (Q->front == Q->rear ); /*队列空的判断*/    return ERROR; *e=Q->data [Q->front];  /*将队头元素赋值给e */  Q->frnotallow= (q->front+1 ) &MAXSIZE; /* front 指针向后移一位置,若到最后则转到数组头部*/ return  OK;}

循环队列面临着数组可能会溢出的问题，下面来讨论不需要担心链式存储结构

4.12 队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。为了操作上的方便，将队头指针指向链队列的头结点，而队尾指针指向终端结点

空队列时，front 和rear都指向头结点

链队列的结构为:

typedef int QElemType;  /* QElemType 类型根据实际情况而定，这里假设为int */typedef struct QNode /*结点结构*/{    QElemType data;  struct QNode *next;}QNode, *QueuePtr;typedef struct /*队列的链表结构*/{    QueuePtr front,rear;  /* 队头、队尾指针*/}LinkQueue;

4.13.1队列的链式存储结构一入队操作

入队操作时，其实就是在链表尾部插入结点

/*插入元素e为Q的新的队尾元素*/Status EnQueue ( LinkQueue *Q，QElemType e){    QueuePtr s=( QueuePtr ) malloc (sizeof (QNode) ) ;    if(!s)/*存储分配失败*/     exit ( OVERFLOW) ;    s->data=e;    s->next-NULL;    Q->rear->next=s; /*把拥有元素e新结点s赋值给原队尾结点的后继，*/    Q->rear=s;     /* 把当前的s 设置为队尾结点，rear指向s,见上图中②*/    return OK;}

4.13.2队列的链式存储结构一出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点,若链表除头结点外只剩-一个元素时，则需将rear指向头结点

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为0(1)的， 不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一-些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间 上的开销，但也可以接受。所以在空间上，链队列更加灵活

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

4.13总结回顾

栈(stack) 是限定仅在表尾进行插入和删除操作的线性表。

队列(queue) 是只允许在一端进行插入操作， 而在另一端进行删除操作的线性表

它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。因此它们各自有各自的技巧来解决这个问题。

对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。

​ 对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是0(n)的时间复杂度变成了0(1)。
它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同