第四章：栈和队列

发表于 | 分类于 |

配图
苟有恒，何必三更眠五更起；最无益，莫过一日曝十日寒。

一、栈的定义

是限定仅在表尾进行插入和删除的操作的线性表。允许插入和删除的一端成为栈顶，另一端成为栈底，不含任何数据元素的栈称为空栈，栈又称后进先出（Last In First Out）的线性表，简称LIFO结构。

栈的插入操作叫进栈、压栈或入栈；删除操作叫出栈、也有叫弹栈。如下图所示：
栈

二、栈的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
ADT 栈
DATA
   //同线性表。元素具有相同类型，相邻元素具有前驱和后继关系。
Operation
    InitStack(* s);    //初始化操作，建立一个空栈s
    DestoryStack(* s);    //若栈存在，销毁它
    ClearStack(* s);        //清空栈
    StackEmpty(* s);    //栈为空犯回true，否则false。
    GetTop(S,* e);        //栈存在且不为空，用e返回s的栈顶元素
    Push(*S,e);        //栈s存在，则插入新元素e到栈s并成为栈顶元素
    Pop(*S, *e);        //删除栈顶元素，并用e返回它的值
    StackLength(S);    //返回栈S的元素个数
endADT

三、栈的顺序存储结构及实现

栈的顺序存储其实也是线性表顺序存储的简化，称为顺序栈。线性表是用数组来实现的，栈则用一个top变量来指示栈顶元素在数组中的位置，如同物理中使用的游标卡尺的游标。当栈存在一个元素时，top为0，因此空栈的判定条件定为top为-1。

1、栈的顺序存储结构——进栈操作

1
2
3
4
5
6
7
8
Status Push(SqStack *S,SElemType e){
    if(S - >top == MAXSIZE - 1){
        return ERROR;
   }
    S - >top++;
    S ->data[S - > top] = e;
    return OK;
}

2、栈的顺序存储结构——出栈操作

1
2
3
4
5
6
7
8
Status Pop(SqStack * S,SElemType *e){
    if(S - > top == -1){
       return ERROR;   
   }        
    * e = S - >data[S ->top];
    S->top--;
    return OK;
}

时间复杂度均为O（1）;

四、两栈共享空间

两栈共享空间

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

两栈共享空间的结构代码：

1
2
3
4
5
typedef struct{
    SElemType data[MAXSIZE];
    int top1;
    int top2;
}SqDoubleStack;

可以看出，当栈1为空时，top1等于-1；top2等于n时，栈2为空。当top1等于n-1时，栈1满了，top2等于0时，栈2满了。但其实，栈满更多的情况是两个指针相差1时，即top1+1 == top2时。

1、 插入元素代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
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){
        S->data[--S->top2] = e;
   }
    return OK;
}

2、 删除元素代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//若栈不空，则删除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;
}

五、栈的链式存储结构及其实现

链栈结构代码如下:

1
2
3
4
5
6
7
8
9
typedef struck StackNode{
    SElemType data;
    struck StackNode *next;
}StackNode, *LinkStackPtr;
typedef struck LinkStack{
    LinkStackPtr top;
    int count;
}LinkStack;

1、进栈操作

1
2
3
4
5
6
7
8
Status Push(LinkStack *S,SElemType e){
    LinkStackPtr s = (LinkStackPtr) malloc(sizeof(StackNode));
    s ->data = e;
    s - >next = S ->top;
    S->top = s;
    S->count ++;
    return OK;
}

2、 出栈操作

1
2
3
4
5
6
7
8
9
10
11
12
Status Pop(LinkStack *S,SElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*S)){
        return ERROR;
   }
    * e = S ->top ->data;
    p = S->top;
    s ->top = S - >top ->next;
    free(p);
    s ->count --;
    return OK;
]

如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好使用链栈，如果是在可控范围内，建议使用顺序栈。

六、栈的应用

1、递归

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

递归的经典例子是斐波那契数列（Fibonacci）。兔子出生两个月后有繁殖能力，一对兔子每隔有能生成一对兔子，假设兔子不死，一年繁殖多少兔子？通过推测的话，可以得出下表内容。可以看出兔子对数为：前面相邻两项之和，构成了后一项。

递归运算

如果用数学函数定义就是：

数学函数

如果用递归来实现的话

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Fbo(int i){
    if(i<2){
        return i==0?0:1;
    }
    return  Fbi(i-1) + Fbi(i-2);
}
int main(){
    int i;
    for(int i = 0;i < 40 ; i++){
        print(“%d”,Fbi(i));
   }
    return 0;
}

2、四则运算表达式求值

1、 后缀(逆波兰)表示法定义

一种不需要括号的后缀表达法，也称为逆波兰（Reverse Polish Notation，RPN）表示。

举个例子“9 + （3 - 1）X 3 + 10 /2”的后缀表达式为“9 3 1 - 3 * + 10 2 / +”。叫后缀的原因是所有符号都是在要运算的数字后面出现。

使用思路：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈进行运算，运算结果进栈，一直到最终获得结果。

2、 中缀表达式转后缀表达式

平时使用的标准的四则运算表达式也叫作中缀表达式。如中缀表达式“9 + （3-1） 3 +10 /2”的后缀表达式为“9 3 1 - 3 + 10 2 / +”。

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

将中缀表达式转为后缀表达式（栈用来进出运算符号）
将后缀表达式进行运算得出结果（栈用来进出运输的数字）

七、队列的定义

只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表。简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

八、队列的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
ADT队列
DATA
   //同线性表。元素具有相同类型，相邻元素具有前驱和后继关系。
Operation
    InitQueue(* s);    //初始化操作，建立一个空队列s
    DestoryQueue(* s);    //若队列存在，销毁它
    ClearQueue(* s);        //清空队列
    QueueEmpty(* s);    //队列为空犯回true，否则false。
    GetHead(S,* e);        //栈存在且不为空，用e返回s的队头元素
    EnQueue(*S,e);        //若s存在，插入元素e成为队尾元素
    DeQueue(*S,e);        //删除队列S中的头元素，并用e返回它的值
    QueueLength(S);    //返回队列S的元素个数
endADT

九、循环队列

1、队列顺序存储的不足

假设一个队列有n个元素，顺序存储的队列需要建立一个大于n的数组，并把队列所有元素存储在数组前n个单元，数组下标为0的一端是队头。入队操作就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O（1）。与栈不同的是，队列元素出列是在对头，下标为0的位置，也就意味着队列所有元素都得向前移动，以保证队头下标为0，此时时间复杂度为O（n）。

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

当出现如下图情况时，数组就会出现越界了。

数组越界

即0和1还空闲着，后续的元素却没地方插入了，这种现象叫做“假溢出”。解决假溢出的办法就是后面满了则从头开始，也就是头尾相接的循环。这种头尾相接的顺序存储结构称为循环队列。

这里有个问题：当队列满了或者队列为空时，front都等于rear，那怎么判断是空是满呢？两个办法：

  • 设置一个标志变量flag，当front==rear时，flag==0则为空，否则为满。
  • 当front==rear时，队列为空，当队列满时，修改其条件，保留一个元素空间。也就是说，队列满时，数组还有一个空闲空间。如果队列最大尺寸为QueueSize，那么队列满的条件则是（rear+1）%QueueSize == front。

当rear>front时，队列长度为rear- front；当rear<front时，队列的长度分为两段，一段是QueueSize - front，另一段是0+rear，加在一起，队列长度为rear - front+QueueSize。因此通用的计算队列长度的公式是：（rear-front + QueueSize）%QueueSize。

2、循环队列的顺序结构代码

1
2
3
4
5
6
7
typedef int QElemType;
typedef struct{
    QElemType data[MAXSIZE];
    int front;
    int rear;
}SqQueue

3、初始化代码

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

4、循环队列求队列长度代码

1
2
3
int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

5、入队操作代码

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;
    Q->rear = (Q - > rear + 1)%MAXSIZE;
    return OK;
}

6、出列操作代码

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

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

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

1、链队列的结构

1
2
3
4
5
6
7
8
9
10
typedef int QElemType;    //根据实际情况定
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front,rear;
}LinkQueue;

2、入队操作

是在链表尾部插入结点的。

1
2
3
4
5
6
7
8
9
10
11
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;
    Q - >rear = s;
    return OK;
}

3、出队操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status DeQueue(LinkQueue *Q,QElemType *e){
    QueuePtr p;
    if(Q ->front == Q->rear){
        return ERROR;
     } 
    p = Q ->front -> next;
    *e = p -> data;
    Q ->front ->next = p ->next;
    if(Q -> rear == p){
       Q ->rear = Q ->front; 
     }
    free(p);
    return OK;
}

在可以确定队列长度最大值的情况下，建议使用循环队列，无法预估长度的话就使用链队列。

黄自豪 wechat
欢迎我的公众号！
如果你觉得文章对你有帮助，可点击下面的打赏按钮，支持一下！
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多