[数据结构考研][3][栈和队列]

数据结构 数据结构 Comments

第三章 栈和队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
digraph demo{
    线性表->操作受限[dir=none];
    线性表->推广[dir=none];
    操作受限->栈[dir=none];
    操作受限->队列[dir=none];
    栈->顺序栈[dir=none];
    栈->链栈[dir=none];
    栈->共享栈[dir=none];
    队列->循环队列[dir=none];
    队列->链式队列[dir=none];
    队列->双端队列[dir=none];
    推广->数组[dir=none];
    数组->一维数组[dir=none];
    数组->多维数组[dir=none];
    多维数组->压缩存储[dir=none];
    多维数组->稀疏矩阵[dir=none];
}

3.1 栈

3.1.1 栈的基本概念

1 栈的定义

栈(Stack)，只允许在一端进行插入或删除操作的线性表

栈顶(Top)，线性表允许进行插入和删除的那一端

栈底(Bottom)，固定的，不允许进行插入和删除的那一端

空栈，不含任何元素的空表

栈是一种后进先出(Last In First Out, LIFO)的结构

2 栈的基本操作

InitStact(): 初始化空栈

StackEmpty(): 判断一个栈是否为空

Push(): 进栈，若栈未满，则将新元素加入使其成为新的栈顶

Pop(): 出栈，若栈未空，则弹出栈顶元素

GetTop(): 获得栈顶元素的值

ClearStack(): 摧毁栈，并释放栈所占的内存空间

3.1.2 栈的顺序存储结构

1 顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设附一个指针(top)指示当前栈顶的位置

栈的顺序存储类型可描述为

1
2
3
4
5
6
typedef struct 
{
    ElemType *elem;
    int length;
    int listsize;
}SqStack;
2 顺序栈的基本运算
  1. 初始化
1
2
3
4
5
6
7
8
Status InitStack(SqStack *s){
    s->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(!s->elem)
        return OVERFLOW;
    s->length = 0;
    s->listsize = LIST_INIT_SIZE;
    return OK;
}
  1. 判栈空
1
2
3
4
5
6
7
int StackEmpty(SqStack *s){
    if(0 == s->length){
        return 1;
    }else{
        return 0;
    }
}
  1. 进栈
1
2
3
4
5
6
7
8
Status Push(SqStack *s, ElemType e){
    if(s->length >= s->listsize && OVERFLOW == ReAllocStack(s)){
            return OVERFLOW;
    }
    s->elem[s->length] = e;
    s->length++;
    return OK;
}
  1. 出栈
1
2
3
4
5
6
7
8
Status Pop(SqStack *s, ElemType *e){
    if(StackEmpty(s)){
        return ERROR;
    }
    *e = s->elem[s->length-1];
    s->length--;
    return OK;
}
  1. 读栈顶元素
1
2
3
4
5
6
7
Status GetTop(SqStack *s, ElemType *e){
    if(StackEmpty(s)){
        return ERROR;
    }
    *e = s->elem[s->length-1];
    return OK;
}
3 共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

两个栈的栈顶指针都指向栈顶元素

  • top=-1时0号栈为空，top1=MaxSize时1号栈为空
  • 仅当两个栈顶指针相邻(top1-top0=1)，判断为栈满
  • 当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反

3.1.3 栈的链式存储结构

采用链式存储的栈称为链栈

  • 链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况
  • 通常用单链表实现，并规定所有操作都是再单链表的表头进行。

栈的链式存储类型可描述为

1
2
3
4
typedef struct LinkNode{
    ElemType data;          //数据域
    Struct LinkNode *next;  //指针栈
}*LinkStack;                //栈类型定义

3.1.4 其他

对于nn个不同的元素进栈，出栈序列的个数为

$$\frac{1}{n+1}C_{2n}^n=\frac{1}{n+1}\frac{2n!}{{n!}\times{n!}}$$

3.2 队列

3.2.1 队列的基本概念

1 队列的定义

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

  • 其操作的特性为先进先出
  • 队头(Front):允许删除的一端，又称队首
  • 队尾(Rear):允许插入的一端
  • 空队列: 不含任何元素的空表
2 队列常见的基本操作
  • InitQueue():初始化队列，构建一个空队列Q
  • QueueEmpty():判队列空
  • EnQueue():入队
  • DeQueue():出队
  • GetHead():读取队头元素

3.2.2 队列的顺序存储结构

1 队列的顺序存储

队列的顺序实现是值分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指示队头元素和队尾元素

2 循环队列

将顺序队列设想为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动为0

为了区分队空还是队满的情况

  1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元
  2. 类型中增设表示元素个数的数据成员
  3. 类型中增设tag数据成员，以区分是队满还是队空
3 循环队列的操作

当删除元素时，队头指针+1

当插入元素时，队尾指针+1

3.2.3 队列的链式存储

1 队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表

  • 出队时，首先判断队是否为空，若不空，则取出队头元素，将其从链表中摘除
  • 入队时，建立一个新节点，将新节点插入到链表的尾部，并改让Q.rear指向这个新插入的节点
2 链式队列的基本操作

略

3.2.4 双端队列

双端队列: 双端队列是指允许两端都可以进行入队和出队操作的队列，将队列的两端分别称为前端和后端，两端都可以入队和出队。

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

输入受限的双端队列:允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

思想如下

  • 初始设置一个空栈，顺序读入括号
  • 若是右括号，则或者使置于栈顶的元素得以消解，或者不合法输入
  • 若是左括号，则将其压入栈中
  • 当算法结束时，要保证栈为空

3.3.2 栈在表达式求值中的应用

中缀表达式

  • 通常表达式
  • 例如(a+b)*c

后缀表达式

  • 运算符在操作数后面，在后缀表达式中已经考虑了运算符的优先级，没有括号
  • 例如ab+c*

中缀表达式转后缀表达式

  1. 遇到操作数直接输出
  2. 遇到操作符
    1. 若优先级大于栈顶元素，则压入栈中
    2. 若优先级小于或等于栈顶元素，则弹出栈中操作符，直到优先级大于栈顶元素，然后压入栈中
  3. 遇到左括号，压入栈中
  4. 遇到右括号，弹出栈顶元素直到弹出一个左括号

3.3.3 栈在递归中的应用

可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换

3.3.4 队列在层次遍历中的应用

可以用队列实现二叉树的层次遍历，思路如下

  1. 根节点入队
  2. 若队空，则结束遍历，否则重复步骤3
  3. 队列中的第一个节点出队，访问它，若其有左孩子，左孩子入队；若其有右孩子，右孩子入队。

3.3.5 队列在计算机系统中的应用

  1. 解决主机与外部设备之间速度不匹配的问题
  2. 解决由多用户引起的资源竞争问题

3.4 特殊矩阵的压缩存储

T0UGH学生&编程爱好者

很拽很拽很拽很拽很拽很拽很拽很拽