栈、队列和数组 | DS

栈

概念

栈的数学性质：出栈排列数目（$n$ 个不同元素以某种顺序依次进栈，并可在任意时刻出栈）满足函数 $Catalan()$：$N=\frac{1}{n+1}C^n_{2n}$

栈的基本操作：初始化、判空、进栈 push、出栈 pop、读栈顶、销毁

顺序存储结构

顺序栈、共享栈（两个顺序栈共享存储空间）

采用共享栈的好处：节省存储空间，降低发生上溢的可能

链式存储结构

链栈

代码实现

顺序栈

/* 顺序栈 */
#define MaxSize 50
typedef struct {
    ElemType data[maxSize];
    int top;
} SqStack;

/**
 * 初始化
 */
void initStack(SqStack &st) {
   st.top = -1;
}

/**
 * 判栈空
 * @return 栈空与否
 */
bool isEmpty(SqStack st) {
    return st.top == -1;
}

/**
 * 判栈满
 * @return 栈满与否
 */
bool isFull(SqStack st) {
    return st.top == MaxSize - 1;
}

/**
 * 进栈
 * @param  st 栈
 * @param  e  进栈元素的值
 * @return    操作结果
 */
bool push(SqStack &st, ElemType e) {
    if (isFull(st)) return false;
    st.data[++st.top] = e;
    return true;
}

/**
 * 出栈
 * @param  st 栈
 * @param  e  记录出栈元素的值
 * @return    操作结果
 */
bool pop(SqStack &st, ElemType &e) {
    if (isEmpty(st)) return false;
    e = st.data[top--];
    return true;
}

/**
 * 读栈顶
 * @param  st 栈
 * @param  e  记录栈顶值
 * @return    操作结果
 */
bool getTop(SqStack st, ElemType &e) {
    if (isEmpty(st)) return false;
    e = st.data[st.top];
    return true;
}

链栈

带头结点

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

/**
 * 判栈空
 * @return 栈空与否
 */
bool isEmpty(LiStack lst) {
    return lst->next == NULL;
}

/**
 * 进栈(头进)
 * @param  e  进栈元素的值
 */
void push(LiStack &lst, ElemType e) {
    // 新结点
    LinkNode *p = (LinkNode*)malloc(sizeof(LinkNode));
    p->data = e;
    p->next = NULL;  // 可省,但是好习惯

    // 头插
    p->next = lst->next;
    lst->next = p;
}

/**
 * 出栈(头出)
 * @param  e  记录出栈元素的值
 */
bool pop(LiStack &lst, ElemType &e) {
    // 判空
    if (isEmpty(lst)) return fasle;

    LinkNode *p = lst->next;
    e = p->data;  // 记录出栈元素值
    lst->next = p->next;
    free(p);

    return true;
}

应用

• 括号匹配、表达式求值、调用函数（递归调用、子程序调用）、进制转换、迷宫求解

• 递归

  优点：代码简单，容易理解

  尾递归和单向递归可以用循环/迭代消除，不一定非要使用栈

  递归效率不高的原因是递归调用过程中包含很多重复的计算

  关于尾调用、尾递归、递归

• 表达式表示方法

  前缀（波兰式）、中缀、后缀（逆波兰式）

  例：中缀式 (a+b+c×d)/e，转化为前缀式为 /++ab×cde，转化为后缀式为 ab+cd×+e/

  一个中缀式可能有多种前/后缀式，因为前/后缀式是由中缀式按某一种运算次序而生成的

• 中缀化后缀（算法思路）

  遇数字直接输出，遇运算符入栈

  运算符入栈时先将前面优先级 ≥ 自己的一一出栈

  右括号与最近的左括号匹配，将它们之间的符号出栈（右括号不入栈）

• 后缀式运算

  从左到右入栈，数字直接入，遇到运算符时将栈内 2 个操作数出栈（运算符几目就出栈几个），进行运算后将值入栈，重复操作

• 原中缀表达式对应的表达式树的后序遍历序列即为后缀表达式

• 前缀式运算

  从左到右，将连续出现的两个操作数和在它们之前紧靠的运算符构成一个最小表达式

• 中缀式运算

  准备俩栈，操作数直接入栈 1，运算符入栈 2

  运算符入栈之前若发现栈顶的运算符优先级 ≥ 自己，则先将其出栈，并从栈 1 弹出相应数目的操作数与之运算，得到的值入栈 1

  入完栈后就开始出栈运算，再将运算结果入栈，直到栈 2 为空

队列

概念

略

顺序存储结构

顺序队列、循环队列（逻辑环状的顺序队列）

链式存储结构

链队

双端队列

输入序列 1 2 3 4，不能得到的输出序列：

1）输入受限：4 2 1 3、4 2 3 1

2）输出受限：4 1 3 2、4 2 3 1

代码实现

循环队列

#define MaxSize 50
typedef stuct {
    int data[maxSize];
    int front;  // 指向队头元素
    int rear;  // 指向队尾元素的下一个位置
} SqQueue;

/**
 * 初始化
 * @param qu 被操作的队列
 */
void initQueue(SqQueue &qu) {
    qu.front = qu.rear = 0;
}

/**
 * 判队空
 * @return 队空与否
 */
bool isEmpty(SqQueue qu){
    return qu.front == qu.rear;
}

/**
 * 判队满
 * 以牺牲一个存储单元的方式来区分队空和队满
 * @return 队满与否
 */
bool isFull(SqQueue qu){
    return ((qu.rear + 1) % maxSize) == qu.front;

    // 其他处理方式
    // 1.增设成员变量size,表示当前元素个数
    // 2.增设成员变量tag
    //   若因删除导致Q.rear == Q.front,tag设为0,表示队空;
    //   若因插入导致则设为1,表示队满
}

/**
 * 入队(尾入)
 * @param  qu 队列
 * @param  e  入队元素的值
 * @return    操作结果
 */
bool offer(SqQueue &qu, ElemType e) {
    // 先判满
    if (isFull(qu)) return false;

    qu.data[qu.rear] = e;
    qu.rear = (qu.rear + 1) % maxSize;
    return true;
}

/**
 * 出队(头出)
 * @param  qu 队列
 * @param  e  记录出队元素值
 * @return    操作结果
 */
bool poll(SqQueue &qu, ElemType &e) {
    // 先判空
    if (isEmpty(qu)) return false;

    e = qu.data[qu.front];
    qu.front = (qu.front + 1) % maxSize;
    return true;
}

/**
 * 获取队列长度
 * @return 队列长度
 */
int getQLen(SqQueue qu) {
    return (qu.rear - qu.front + MaxSize) % MaxSize;
}

链队

带头结点

/**
 * 链队结点
 */
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;
/**
 * 链队
 */
typedef struct {
    LinkNode *front;  // 指向头结点
    LinkNode *rear;  // 指向队尾结点
} *LiQueue;

/**
 * 初始化
 */
void initQueue(LiQueue &lqu){
    lqu->front = lqu->rear = (LinkNode*)malloc(sizeof(LinkNode));  // 建立头结点
    lqu->front->next = NULL;
}

/**
 * 判队空
 */
bool isEmpty(LiQueue lqu) {
    return lqu->front == lqu->rear;
}

/**
 * 入队(尾入)
 */
void enQueue(LiQueue &lqu, ElemType e){
    // 创建新结点
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = e;
    s->next = NULL;
      
    // 入队操作  
    lqu->rear->next = s;
    lqu->rear = s;
}

/**
 * 出队(首出)
 */
bool deQueue(LiQueue &lqu, ElemType &e) {
    // 出队先判空
    if (isEmpty(lqu))  return false;

    // 出队操作
    LinkNode *p = lqu->front->next;
    e = p->data;
    lqu->front->next = p->next;

    // 若出队后队空了,则需要修改队尾指针
    if (lqu->rear == p) {
        lqu->rear = lqu->front;
    }

    free(p);

    return true;
}

链栈的头指针（链表名）即为栈顶指针，只有这一个指针

而链队，从定义上看，由两部分组成：含两个指针的结构体 + 链表，也可以看成含头尾指针的链表，且其头尾指针存在一个结构体中

这种差异在初始化中尤为明显

应用

1）解决主机与外部设备之间速度不匹配的问题

2）解决由多用户引起的资源竞争问题

3）层次遍历、广度优先搜索、缓冲区、页面替换……

数组

• 数组定义

  由 $n$ ($n ≥ 1$) 个相同类型的数据元素构成的有限序列

• 数组与线性表

  数组是线性表的推广

  一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，依次类推

  之前讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的
  数组和广义表可以看成是线性表在下述含义的扩展：表中的数据元素本身也是一个数据结构

• 计算机语言中的数组

  属于数据类型

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

  逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储

• 多维数组（矩阵也是）有两种映射方法：按行优先和按列优先

  

矩阵

相同元素或零元素在矩阵中的分布存在一定规律的矩阵称为特殊矩阵，反之称为稀疏矩阵

压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间

特殊矩阵

特殊矩阵的压缩存储

1）对称矩阵：$n$ 阶方阵存放在一维数组 B[n(n+1)/2] 中，一般存下三角

2）三角矩阵：存放在一维数组 B[n(n+1)/2+1] 中（最后存储常量项 c 一次）

3）对角矩阵、带状矩阵：一维数组

矩阵行列下标从 1 开始，数组要看题目

稀疏矩阵

表示方法

• 三元组表示法

  一个三元组（行标，列标，值）唯一确定一个非零元

• 伪地址表示法

  每行只有两个存储单元：值与伪地址

  伪地址即元素在矩阵中按照行优先或列优先存储的相对位置（相对第一个元素）

  对于稀疏矩阵 $A_{m×n}$，其元素 $A_{ij}$ 的伪地址为 $n(i−1)+j$，可反推真实地址

顺序存储结构

三元组顺序表：失去了随机存取特性

/**
 * 三元组顺序表建立
 * @param A 存储稀疏矩阵的二维数组
 * @param m A行数
 * @param n A列数
 * @param B 三元组
 */
void createTrimat(float A[][maxSize], int m, int n, float B[][3]) {
    int k = 1;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (A[i][j] != 0) {
                B[k][0] = A[i][j];  // 值
                B[k][1] = i;  // 行标
                B[k][2] = j;  // 列标
                ++k;
            }
    B[0][0] = k - 1;  // 第0行用来存储非零元素个数、行数和列数
    B[0][1] = m;
    B[0][2] = n;
}

/**
 * 通过三元组顺序表打印稀疏矩阵
 * @param B 三元组
 */
void print(float B[][3]) {
    int k = 1;
    for (int i = 0; i < B[0][1]; ++i) {
        for (int j = 0; j < B[0][2]; ++j) {
            if (i == (int)B[k][1] && j == (int)B[k][2]) {
                printf("%d ", B[k][0]);
                ++k;
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}

链式存储结构

十字链表法（三元组）

/* 十字链表普通结点 */
tpyedef struct OLNode {
    int row, col;  // 行列下标
    struct OLNode *right, *down;  // 该非零元所在行表和列表的后继链域
    float val;
} OLNode;

/* 十字链表头结点 */
tpyedef struct {
    OLNode *rhead, *chead;
    int m, n, k;  // 行数、列数、非零元个数
} CrossList;

/**
 * 十字链表建立
 * @param A 存储稀疏矩阵的二维数组
 * @param m A行数
 * @param n A列数
 * @param k 非零元个数
 * @param M 十字链表
 */
bool createCrossListMat(float A[][maxSize], int m, int n, int k, CrossList &M) {
    // 初始化十字链表头结点
    if (M.rhead != NULL) free(M.rhead);
    if (M.chead != NULL) free(M.chead);
    M.m = m;
    M.n = n;
    M.k = k;
    
    // 初始化每个行表、列表的头结点
    if (!(M.rhead = (OLNode*)malloc(sizeof(OLNode)*m))) return false;  // m个行表头结点
    for (int i = 0; i < m; i++) {
        M.rhead[i].right = NULL;
        M.rhead[i].down = NULL;
    }
    if(!(M.chead = (OLNode*)malloc(sizeof(OLNode)*n))) return false;  // n个列表头结点
    for (int i = 0; i < n; i++) {
        M.chead[i].right = NULL;
        M.chead[i].down = NULL;
    }
    
    // 先统一设置好指向每个列表尾结点的指针
    OLNode *temp_c[maxSize];
    for (int j = 0; j < n; j++)
        temp_c[j] = &(M.chead[j]);

    // 往十字链表里装结点
    for (int i = 0; i < m; i++) {
        OLNode *r = &(M.rhead[i]);  // 跟踪当前行表的尾结点
        for (int j = 0; j < n; j++) {
            if (A[i][j] != 0) {
                OLNode *p = (OLNode*)malloc(sizeof(OLNode));
                p->cow = i;
                p->rol = j;
                p->val = A[i][j];
                p->down = NULL;
                p->right = NULL;
                r->right = p;
                r = p;
                // 更新当前列表尾结点指针
                temp_c[j]->down = p;
                temp_c[j] = p;
            }
        }
    }

    return true;
}

刷题总结

• 某时刻同处于栈中的元素，不管如何进出栈，它们出栈的相对顺序仍保持先进后出

• 链队用循环链表不是不行，只是自找麻烦（出入队后还要维持循环）

• 由于在队首做出队操作，为了便于删除队头元素，故总是选择链头作为队首

  具有首尾指针的单链表，链首能快速增删元素，而队尾只有插入元素方便

• 双端队列可能的输出序列

  1. 输出受限（一端仅能输入）

     入完再出：输出序列 —从内到外→ 输入序列

     随意出：若输出序列第一位是输入序列最后一个，就等于入完再出；若不是，慢慢分析

  2. 输入受限（一端仅能输出）

     入完再出：输入序列 —从外到内→ 输出序列

     随意出：从第一位开始分析

• 循环队列出队，队首指针是 +1

• 循环队列非空时首尾指针指向的不同情况对出入队操作、初始状态以及判空/满的影响

  设定第一个进入队列的元素存储在 0 下标处

  1. front 指向队首元素

     出队先取元素，再移 front

     初始 front 为 0

  2. front 指向刚出队元素（队首元素前一个位置）

     出队先移 front，再取元素

     初始 front 指向 maxsize-1

  3. rear 指向队尾元素

     进队先移 rear，后存元素

     初始 rear 为 maxsize-1

  4. rear 指向队尾元素后一个位置

     进队先存元素，后移 rear

     初始 rear 为 0

  队空队满条件（不考虑第一个入队元素位置、所有存储单元都用来存储）

  1. front、rear 指向队首、队尾元素

     队空：(rear+1) % maxsize == front

     队满：(rear+1) % maxsize == front

  2. front 指向队首元素、rear 指向队尾元素后一个位置

     队空：rear == front

     队满：rear == front

  3. front 指向刚出队元素、rear 指向队尾元素

     队空：rear == front

     队满：rear == front

  4. front 指向刚出队元素、rear 指向队尾元素后一个位置

     队空：(front+1) % maxsize == rear

     队满：(front+1) % maxsize == rear

  上述四种情况中队空队满的判断都是一致的，要想区分有以下三种常见手法：

  1）牺牲一个存储单元

  2）增设成员变量 size，表示当前队列元素个数

  3）增设成员变量 tag。若因删除导致判断条件达成，tag 设为 0，表示队空；若因插入导致则设为 1，表示队满

• 循环队列长度要加 maxSize 再模，要不要加 1 需要看首尾指针的设定

• 链队出队时队尾指针也可能会修改

• 矩阵/多维数组存到一维数组后的下标

  三要点：矩阵类型、行优先 or 列优先、该元素在矩阵中的位置

  一细节：一维数组起始序号