本章通常以选择题的形式考查，题目不算难，但命题的形式比较灵活，其中栈(出入栈的过程、出栈序列的合法性)和队列的操作及其特征是重点。由于它们均是线性表的应用和推广，因此也容易出现在算法设计题中。此外，栈和队列的顺序存储、链式存储及其特点、双端队列的特点、栈和队列的常见应用，以及数组和特殊矩阵的压缩存储都是读者必须掌握的内容。

1 栈

栈指的是只允许在一段进行操作的线性表，如图所示

栈顶：线性表允许插入删除的一端，比如有某个栈S=(a1,a2,a3,a4,a5)，则进栈顺序是a1->a5，出栈顺序是a5->a1（先进后出）
栈底：固定端，不允许插入删除

空栈即不包含任何元素

1.1 栈的顺序存储实现（顺序栈）

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

#define MaxSize 50  // 定义栈中元素的最大个数
typedef strudct{
        ElemType data[MaxSize];  // 存放栈元素
    int top;  // 栈顶指针
}SqStack;

栈顶元素S.top，初始设置为-1
栈顶元素S.data[S.top]

1.2 顺序栈的基本操作

Initstack(&S)：初始化一个空栈S。

stackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回false。

Push(&S，x)：进栈，若栈 S 未满，则将加入使之成为新栈顶。

Pop(&S，&x)：出栈，若栈S 非空，则弹出栈顶元素，并用x返回。

GetTop(S,&x)：读栈顶元素，若栈S 非空，则用x返回栈顶元素。

Destroystack(&S)：销毁栈，并释放 S 占用的存储空间 (“&”表示引用调用)。

在解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数。

1.2.1 初始化栈

void Initstack(&S){
    S.top = -1;
}

1.2.2 判栈空/栈满

栈空条件：S.top==-1

bool stackEmpty(&S){
    if(S.top == -1) return true;
    else return false
}

栈满条件：S.top==MaxSize-1

bool stack(&S){
    if(S.top==MaxSize-1) return true;
    else return false;
}

1.2.3 进栈

void Push(&S, x){
    if(S.top==MaxSize-1) return false;  // 判断栈满
    S.data[++S.top] = x;
    return true;
}

1.2.4 出栈

void Pop(&S){
    if(S.top == -1) return false;  // 判断栈空
    S.top -= 1;
    return true;
}

1.2.5 读取栈顶元素

void GetTop(&S){
    if(S.top == -1) return false;
    x = S.data[S.top];
    return true;
}

1.3 共享栈

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

两侧都设置栈顶指针，当top0==-1时栈0为空，当top1==MaxSize时栈1为空
当top0-top1=0时栈满

1.4 栈的链式结构实现——链栈

通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

规定链栈没有头结点，Lhead直接指向栈顶元素。

链式存储结构类型：

typedef struct Linknode{
        ElemType data;
        struct LinkNode *next;
}*LiStack;

1.5 顺序栈和链栈的对比

顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。

链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。

1.6 栈在括号匹配中的应用

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

中缀表达式A+B*(C-D)-E/F 所对应的后缀表达式为ABCD-*+EF/-（中缀表达式如何变成后缀表达式？）

通过后缀表示计算表达式值的过程为:

顺序扫描表达式的每一项，然后根据它的类型做如下相应操作:

若该项是操作数，则将其压入栈中;
若该项是操作符<op>则连续从栈中退出两个操作数 Y和，形成运算指令X<op>Y，并将计算结果重新压入栈中。

例如上图的计算过程应该如下：

1.8 栈在递归中的应用（P90）

2 队列

队列也是一种受限的线性表，其要求在一段进行插入，另一端进行删除。

队头：允许删除的一端
队尾：允许插入的一端
特性：先进先出

2.1 队列的顺序存储结构

顺序存储结构描述

#define MaxSize 50  // 定义队列中元素的最大数
typedef struct{
        ElemType data[MaxSize];  // 存放队列指针
        int front, rear;  // 队头指针和队尾指针
}SeQueue;

当front==rear==0为空队列，如图(a)。但是rear==MaxSize不能判断为满队列，如图(d)，这种情况叫做假溢出。

2.2 循环队列

为了解决假溢出的问题提出循环队列。将顺序队列臆造为一个环状的空间即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

队满和队空的处理方案有三个：

2.2.1 方案一

牺牲一个单元来区分队空和队满，如图(d)

队满条件：(Q.rear+1)%MaxSize==Q.front
队空条件：Q.front==Q.rear
队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize

2.2.2 方案二

增设元素个数的的数据单元，两种情况都存在Q.front==Q.rear

队空条件：Q.size==0
队满条件：Q.size==MaxSize

2.2.3 方案三

类型中增设 tag 数据成员，以区分是队满还是队空。tag 等于 0时，若因删除导致Q.front==Q.rear，则为队空;tag等于1时，若因插入导致Q.front==Q.rear，则为队满。

2.3 队列的链式存储结构

实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点(注意与顺序存储的不同)。

2.3.1 不带头结点的链式队列

存储类型可描述为：

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front, *next;
}*LinkQueue;

当font==NULL==read==NULL时为空链式队列

2.3.2 带头结点的链式队列

不带头结点的链式队列在两端操作会与中间操作不同，为了统一操作，一般使用带有头结点的链式队列

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。

初始化

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode)*malloc(sizeof(LinkNode));  // 建立头结点
    Q.front -> next = NULL;
}

判队空

bool isEmpty(LinkQueue*Q, ElemType x){
    if(Q.front==Q.rear) return true;
    return false;
}

入队

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode*s=(LinkNode *)malloc(sizeof(LinkNode));
    //创建新结点，插入到链尾
    S->data=x;s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

出队

bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front==Q.rear) return false;
    LinkNode *p = Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p):
        Q.rear=Q.front;
    free(q);
    return true;
}

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

在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层（比如二叉树的遍历）

过程如下：

根节点入队
若队空，处理完毕。否则，执行步骤3

队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队。若其有右孩子，则将右孩子入队，返回步骤2。

4 数组

在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据。所以，我们不研究矩阵及其运算等，而把精力放在如何将矩阵更有效地存储在内存中，并能方便地提取矩阵中的元素。

数组是由n(n>1)个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在 n 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

3.1 一维数组的存储结构

一个数组所有元素在内存中占一段连续的存储空间。

存储结构关系为 $$Loc(a_i)=Loc(a_0)+i*L$$，其中L代表每个元素占有的单元格

3.2 多为数组

以二维数组为例，分为行优先和列优先。

3.2.1 行优先

假设行下标范围为$$[0, h_1]$$，列下标为$$[0, h_2]$$，则存储关系为：

$$Loc(a_{ij})=Loc(a_{00})+[i*(h_2+1)+j]*L$$

3.2.2 列优先

假设行下标范围为$$[0, h1]$$，列下标为$$[0, h2]$$，则存储关系为：

$$Loc(a_{ij})=Loc(a_{00})+[j*(h_1+1)+i]*L$$

5 特殊矩阵的压缩存储

压缩存储，指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间（找出特殊矩阵中值相同的矩元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中）

特殊矩阵指的是具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一

定规律性的矩阵（如对称矩阵、上(下)三角矩阵、对角矩阵等)

5.1 对称矩阵

若对一个n阶矩阵4中的任意一个元素a都有$$a_{ij}=a_{ji}$$，则称其为对称矩阵。

此时将二维矩阵用一维矩阵$$B[n*(n+1)/2)]$$来表示（只保存下三角区或上三角区及对角线元素，节省空间），即$$b_k=a_{ij}$$。

元素下标k和ij之间的关系如下：

5.2 三角矩阵

下三角矩阵图(a)中，上三角元素均为同一常量。可采用与对称矩阵相同的储存思想，将二维矩阵用一维矩阵$$B[n*(n+1)/2 +1]$$来表示

存储结构图如下：

元素下标关系如下：

5.3 三对角矩阵/带状矩阵

如下图所示，$$|i-j|>0$$元素为0

三对角矩阵对角线元素下标对应关系为$$k=2*i+j-3$$
由k求i和j公式如下$$i=[(k+1)/3+1]; j=k-2*i+3$$

6 稀疏矩阵

矩阵中非零元素的个数t，相对矩阵元素的个数。来说非常少，即$$s>>t$$的阵称为稀疏矩阵。

由于稀疏矩阵非零元素很少，因此采用存储非零元素来存储。但是，这里存在一个问题，即非零元素为非规律性存储，因此便采用三元组的方式同时存储坐标信息。

三元组可以采用数组或十字链表法存储。

【数据结构】第三章栈、队列和数组

1 栈

1.1 栈的顺序存储实现（顺序栈）

1.2 顺序栈的基本操作

1.2.1 初始化栈

1.2.2 判栈空/栈满

1.2.3 进栈

1.2.4 出栈

1.2.5 读取栈顶元素

1.3 共享栈

1.4 栈的链式结构实现——链栈

1.5 顺序栈和链栈的对比

1.6 栈在括号匹配中的应用

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

1.8 栈在递归中的应用（P90）

2 队列

2.1 队列的顺序存储结构

2.2 循环队列

2.2.1 方案一

2.2.2 方案二

2.2.3 方案三

2.3 队列的链式存储结构

2.3.1 不带头结点的链式队列

2.3.2 带头结点的链式队列

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

4 数组

3.1 一维数组的存储结构

3.2 多为数组

3.2.1 行优先

3.2.2 列优先

5 特殊矩阵的压缩存储

5.1 对称矩阵

5.2 三角矩阵

5.3 三对角矩阵/带状矩阵

6 稀疏矩阵

热门文章

最新文章

相关课程

相关电子书

【数据结构】第三章 栈、队列和数组

1 栈

1.1 栈的顺序存储实现（顺序栈）

1.2 顺序栈的基本操作

1.2.1 初始化栈

1.2.2 判栈空/栈满

1.2.3 进栈

1.2.4 出栈

1.2.5 读取栈顶元素

1.3 共享栈

1.4 栈的链式结构实现——链栈

1.5 顺序栈和链栈的对比

1.6 栈在括号匹配中的应用

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

1.8 栈在递归中的应用（P90）

2 队列

2.1 队列的顺序存储结构

2.2 循环队列

2.2.1 方案一

2.2.2 方案二

2.2.3 方案三

2.3 队列的链式存储结构

2.3.1 不带头结点的链式队列

2.3.2 带头结点的链式队列

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

4 数组

3.1 一维数组的存储结构

3.2 多为数组

3.2.1 行优先

3.2.2 列优先

5 特殊矩阵的压缩存储

5.1 对称矩阵

5.2 三角矩阵

5.3 三对角矩阵/带状矩阵

6 稀疏矩阵

热门文章

最新文章

相关课程

相关电子书

【数据结构】第三章栈、队列和数组