第四章 栈与队列

栈的定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。（指的是栈顶）栈顶：插入和删除的一端栈底：另外一段空栈：不含任何数据元素的栈栈又称：后进先出的线性表，简称LIFO结构

注意：栈元素具有线性表关系，即前驱后继关系。特殊之处就是这个线性表的插入和删除位置，只能在栈顶进行。栈底是固定的，最先进栈的只能在栈底。

栈的插入操作叫做进栈，也叫压栈、入栈。

栈的删除操作，叫做出栈，也叫弹栈。

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_88b7c7d20dbe75a35fa94bf1f5209ca7.png

栈的抽象数据类型

push：插入（进栈） pop：删除（出栈）

1
2
3
4
5
6
7
8
9
10
11
12
ADT 栈（stack）
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
operation
    InitStack(*S):初始化操作，建立一个空栈s。
    DestroyStack(*S):若栈存在，则销毁它。
    CleanrStack(*S):将栈清空。
    StackEmpyt(S):若栈为空，返回true，否则返回false。
    GetTop(S,*e):若栈存在且非空，用e返回s的栈元素
    Push(*S,e):若栈s存在，插入新元素e到栈s中并称为栈顶元素。
    StatckLengtg(S):返回栈s的元素个数。
endADT

栈的顺序存储结构及实现

栈的顺序存储结构

栈的顺序结构其实就是线性表顺序存储的简化，称为顺序栈。

1
2
3
4
5
typedef int SElemType; //SElemType类型根据实际情况
typedef struct{
      SElemType data[MAXSIZE];
      int top; //栈顶指针
}SqStack;

栈的顺序存储结构-进栈

1
2
3
4
5
6
7
8
9
//插入元素e为新的栈顶元素
Status Push(SqStack *S,SElemType){
      if(S->top == MAXSIZE -1){   //如果栈满
          return ERROR;
      }
      S->top++;     //栈顶指针加1
      S->data[S->top]=e;  //将新插入元素赋值给栈顶空间
      return OK;
}

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

1
2
3
4
5
6
7
8
9
//若栈不为空，则删除S的栈顶元素怒，用e返回其值，并返回OK，否则ERROR
Status Pop(SqStack *S,SElemType *e){
     if(S->top==-1){
          return ERROR;
     }
     *e=S->data[S->top];  //将要删除栈顶元素赋值给e
     S->top--;//栈顶指针减一
     return OK;
}

两站共享空间

1
2
3
4
5
6
typedef struct
{
      SElemType data[MAXSIZE];
      int top1; //栈1栈顶指针
      int top2; //栈2栈顶指针
}SqDoubleSatck;

两站共享空间的push方法

1
2
3
4
5
6
7
8
9
 Status Push(SqDoubleStack *S,SElemType e,int stackNumber){
       if(S->top1+1=S->top2)   //栈满了
            return ERROR;
       if(statckNumber==1)        //栈1有元素进栈
            S->data[++S->top1]=e   //如果是栈1则线top1+1后 给数组元素赋值
       else if(statckNumber==2)       //栈2有元素进栈
            S-data[--S->top2]=e   //如果是栈2，则线top2-1后 给数组元素赋值
       return OK;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber){
        if(statckNumber == 1)
        {
                 if(S->top = -1)
                   return ERROR;
                 *e = S->data[S->top1--1];    //将栈1的栈顶元素出栈
        }
        else if(stackNumber == 2){
                 if(S->top2==MAXSIZE)
                    return ERROR;
                 *e = S->data[S->top2++];  //栈2的栈顶元素出栈
        }
      return OK;
}

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

栈的链式存储结构

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

链栈代码定义：

1
2
3
4
5
6
7
8
9
10
typedef struct StackNode{
     SElemType data;
     struct StatckNode *next;
}

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

栈的链式存储结构–进栈操作

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_d97fb64974b580b71d63537e9a8e3737.png

1
2
3
4
5
6
7
8
Status Push(LinkStack *S,SElemType e){
      LinkStackPtr s=(LinkStackPrt)malloc(sizeof(StackNode));
      s->data=e;
      s->next=S->top;   //把当前栈顶元素赋值给新节点的直接后继。见图1
      S->top=s;     //把新的结点s赋值给栈顶指针，见图2
      S->count++;
      return OK;
}

栈的链式存储结构–出栈操作

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_b40efa6bd4b0f252e18cda94c2447f9e.png

1
2
3
4
5
6
7
8
9
10
11
Status Pop(LinkStack *S,SElemType *e){
       LinkStackPrt p;
       if(StackEmpty(*S))
           return ERROR;
       *e=S->top->data;
       p=S->top;     //将栈顶结点赋值给p，见图3
       S->top=S->top->next;   //使得栈顶指针下移一位，指向后一个结点，见图4
       free(p);               //释放结点p
       S->count--;
       return OK;
}

使用建议：

如果栈的使用过程中元素变化不可预料，有时候小，有时候大，使用链栈。

如果变化在可控范围内，使用顺序栈。

栈的作用

栈的引用同简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦我们要解决的问题核心。

栈的应用–递归

递归：把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数，称为递归函数。

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Fbi(int i){
      if(i<2){
           return i == 0 ? 0 : 1;
      }
      return Fbi(i-1)+Fbi(i-2);
}

int main(){
       int i;
       printf("递归显示斐波那契数列：\n");
       for(i = 0;i<40;i++)
           printf("%d",Fbi(i));
       return 0;
}

注意的是：每个递归定义必须至少有一个条件，满足递归不再进行，即不再引用自身而是返回值退出。

栈的应用–四则运算表达式求值

后缀（逆波兰）表示法的定义

一种不需要括号的后缀表达法，称为逆波兰

正常数学表达式：9+（3-1）x3+10÷2

后缀表达式：9 3 1-3 * + 10 2 / +

后缀原因在于所有的符号都是在要运算数字的后面。

后缀表达式的计算结果

后缀表达式：9 3 1-3 * + 10 2 / +

规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈，进行运算，运算结果在进栈。

中缀表达式转后缀表达式

正常数学表达式：9+（3-1）x3+10÷2也就是中缀表达式。

转换规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即后缀表达式的一部分。若是符号，判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素一次出栈并输出，将当前符号进栈，一直到输出后缀表达式为止。

队列的定义

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

队列是一种先进先出的线性表，简称FIFO。允许插入的一段称为队尾，允许删除的一端称为队头。

例如：q=(a1,a2,…,an)，那么a1就是队头元素，an就是队尾。

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_93a72f8e79c5d40fdb6c01b67fb7304b.png

队列的抽象数据类型

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

循环队列

队列顺序存储的不足

容易出现假溢出

循环队列的定义

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

办法1：设置一个标志了flag，当front=rear，且flag=0时为队列空，当front=rear，且flag=1时为队列满。

办法2：当队列空时，条件时front=rear。当队列满时，修改其条件，保留一个元素空间。也就是数，队列满时，数组还有一个空闲单元。

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_d63dbe79128fc6ec3c247812a0481301.png

在第二种方法中，由于rear可能比front大，也可以比front小，若队列的最大尺寸为QueueSize，那么队列满的条件时(rear+1)%QueueSize==front（取模的目的时为了整合rear与front大小为一个问题）。比如当QueueSize=5，左边的图front=0,而rear4，（4+1）%5=0，所以此时队列满，再比如右图，front=2而rear=1，所以（1+1）%5=2，所以队列也是满的，对于下图，ftont=2,而rear=0，(0+1)%5=1，1≠2，所以此时队列没有满。

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_b84b22038fb5eda0d58c83ca4f9cd977.png

当rear>front，即图1和图2，此时队列的长度为rear-front，但当rear<front，如上图和下图3，队列长度分为两段，一段QueueSize-front，另一段时0+rear，加在一起的长度为rear-front+QueueSzie。

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_bf18f7afca60ffc1063ab5041a9db5e2.png

所以通用计算队列长度公式为

(rear - front + QueueSize)%QueueSize

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

1
2
3
4
5
6
7
typedef int QElemType;
typedef struct
{
    QElemType data[MAXSIZE];
    int front;  //头指针
    int rear;   //尾指针，队列不为空，指向队列尾元素的下一个位置
}SqQueue;

循环队列的初始化代码

1
2
3
4
5
6
Status InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
    return OK;
}

循环队列求队列长度的代码

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

循环队列的入列操作：

1
2
3
4
5
6
7
8
9
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;
}

循环队列如队列操作代码：

1
2
3
4
5
6
7
8
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;
}

循环队列的出队列操作代码：

1
2
3
4
5
6
7
Status DeQueue(SqQueue *Q,QElemType *e)
{
     if(Q->front == Q->rear)
         return ERROR;
     *e=Q->data[Q->front];
     Q->front=(Q->front+1)%MAXSIZE;
}

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

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出，我们把它简称链队列。

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_e66f05dc08c49df39eccdee7590bd65c.png

将队头指针指向链队列的头结点，而队尾指针指向终端节点。空队列时，front和rear都指向头结点。

链队列的结构为：

1
2
3
4
5
6
7
8
9
10
11
12
typedef int QElemType;
typedef struct QNone     //结点结构
{
     QElemType data;
     struct QNone *next;
}QNone,*QueuePtr;


typedef struct
{
   QueuePtr front,rear;//队头、队尾指针
}

队列链式存储结构–入队操作

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

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_1755ae752128e08adedf1ea588953631.png

1
2
3
4
5
6
7
8
9
10
11
Status EnQueue(LinkQueue *Q,QElemType e)
{
     QueuePtr s=(QueuePtr)malloc(sizeof(QNone));
     if(!s)           //存储分配失败
       exit(OVERFLOW);
     s->data=e;
     s->next=NULL;
     Q->rear->next=s;  //把拥有元素e的新节点s赋值给原队尾结点的后继
     Q->rear=s;  ///把当前的s设置为队尾结点，rear指向s
     return OK;
}

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

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

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/10/image_c0572c9f7622349cdda81e110c46a2d6.png

1
2
3
4
5
6
7
8
9
10
11
12
13
Status DeQueue(LinkQueue *Q,QElemType *e)
{
      QueuePtr p;
      if(Q->front==Q->rear)   
          return ERROR;
      p=Q->front->next;//将要删除的队头结点暂存到p
      *e=p->data;     //将要删除的队头几点赋值给e
      Q->front->next=p-next; //将队头结点的后继p->next赋值给头结点后继
      if(Q->rear==p)   //若队头就是队尾，删除后将rear指向头结点
         Q-<rear=Q->front;
      free(p);
      retrun OK;
}

总结

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

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

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

对于队列：为了避免数组插入和删除时需要移动数据，于是引用了循环队列，使得队头和队尾进行数组中循环变化，结局了移动数据的时间损耗。