数据结构-栈与队列

数据结构与算法-栈与队列部分,栈与队列是数据结构重要思想之一，之后的抽象数据类型中诸多算法与方法会利用其特点

---

“花也好。星星也好。世间所有美丽的事物，都是为了比喻你而存在。”

介绍

• 前言：

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

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

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

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

• 栈的插入操作，叫作进栈，也称压栈,入栈
• 栈的删除操作，叫作出栈

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

  举例:3个整型数字元素1，2，3依次进栈，会有哪些出栈次序呢？？？

  321，123，213，132，231

  没有312

---

栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，由于它的特殊性，特别是插入和删除操作，我们改名为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):若栈存在，插入新元素e到栈S中并成为栈顶元素
    Pop(*S,*e):删除栈S中栈顶元素，并用e返回其值
    StackLength(S):返回栈S的元素个数
endADT

同理：思考一下何时用S，S，e，e

---

栈的顺序存储结构及实现

若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。若栈存在一个元素时，top等于0，因此通常把空栈的判定条件定位top等于-1

栈的结构定义

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

• 进栈操作(push)

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

• 出栈操作(pop)

  /*若栈不空，则删除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;
  }

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

---

两栈共享空间

栈的顺序存储缺陷：必须事先确定数组存储空间大小

不理解：栈1为空时，就是top1等于-1时，而当top2等于n时，即是栈2为空时；若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。

两个栈相遇之时，就是两个指针相差1之时，即top1 + 1== top2为栈满

/*两栈共享空间结构*/
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;/*栈1栈顶指针*/
    int top2;/*栈2栈顶指针*/
}SqDoubleStack;

对于两栈共享空间的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;
}

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

注意前提条件:两个具有相同数据类型的栈

---

栈的链式存储结构及实现

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

有栈顶在头部，那对于链栈来说，是不需要头结点的

对于链栈，基本不存在栈满的情况，除非内存已经没有可以使用的空间，对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL

/*链栈的结构代码*/
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;/*ptr指pointer,即指针*/

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

• 栈的链表存储结构——进栈操作

  /*插入元素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++;
      return OK;
  }

• 栈的链式存储结构——出栈操作

  /*若栈不空，则删除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);
      S->count--;
      return OK;
  }

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)

---

栈的应用

• 递归之斐波那契数列(Fibonacci)

  /*迭代法实现*/
  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;
}

我们把一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称作递归函数，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出

• 栈的应用之四则运算表达式求值
  逆波兰(Reverse Polish Notation,RPN):一种不需要括号的后缀表达法，这种后缀表示法，巧妙解决了程序实现四则运算的难题
• 例子：对于”9+(3-1)X3+10/2”如果用后缀表示法应该是”9 3 1 - 3 * + 10 2 / +”
• 计算规则:从左到右遍历表达式的每个数字和符号，遇到是数字就出栈，遇到是符号，就将处以栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最后获得最终结果
• 中缀表达式转后缀表达式规则:从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止

---

队列的定义

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

  队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头.

---

队列的抽象数据类型

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

---

循环队列

• 队列顺序存储的不足

  假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，数组下标为0的一端即是队头

  所谓的入队列操作，就是在队尾插入一个元素，不需要移动任何元素，时间复杂度为O(1)

  与栈不同的是，队列元素的出列在队头，即下标为0的地方，队列所有元素都得前移，那时间复杂度为O(n)，之后利用指针改善

  这里的实现和线性表的顺序存储结构完全相同，不再详述

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

• 定义：我们把队列的这种头尾相接的顺序存储结构称为循环队列。
  我们刚才说，空队列时，front等于rear，现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？

  法一是设置一个标志变量flag,当front == rear，且flag=0时队列空，当flag=1时为队列满

  法二是当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个元素空间。

• 重点讨论法二:由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置就是满的情况，也可能相差整整一圈。若队列的最大尺寸为QueueSize，那么队列满的条件是:(rear+1)%QueueSize == front
• 队列长度: 当rear > front时，队列长度就是rear-front。但当rear < front时，队列长度分为两段，一段是Queue-front，另一段是0+rear，加在一起就是rear-front+Queue，由此通用的计算队列长度公式为: (rear-front+Queue)%Queue

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

循环队列的初始化代码如下

/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q)
{
    Q->front = 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];
    Q->front=(Q->front+1)%MAXSIZE;/*front指针向后移一个位置，若到最后则转到数组头部*/
    return OK;
}

可以发现，单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临数组可能溢出的问题，所以我们需要研究一下不需要担心队列长度的链式存储结构。

---

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

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

  重点：为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点

• 链队列的结构为：

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

• 队列的链式存储结构——入队操作

  /*插入元素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赋值给原队尾结点的后继，把当前的s设置为队尾结点，rear指向s*/
      Q->rear=s;
      return OK;
  }

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

  /*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
  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);
      return OK;
  }

对于循环队列与链队列的比较，可以从两方面考虑

时间上，它们的基本操作都是常数时间，即O(1)，不过循环队列是事先申请好空间，使用期间不释放，而链队列每次申请和释放结点会存在一些时间开销，如果入队出队频繁，还是有细微差异的

空间上，循环队列必须有一个固定长度，所以就有存储元素个数和空间浪费的问题,空间上链队列更灵活

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

---

总结回顾

stack跟queue均可以用线性表的顺序存储结构来实现，但是都存在着顺序存储的一些弊端,由此它们各自有各自的技巧解决问题

• 对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化利用数组的空间。
• 对于队列来说，未来避免数组插入和删除时需要移动数据，则引入了循环队列，使得本来插入和删除是O(n)的时间复杂度变成了O(1)
  它们也可以通过链式存储结构来实现，实现原则跟线性表差不多。