「数据结构」栈和队列

  • 开发
  • 22

栈

栈的基本概念

  1. 定义
    1. 栈是只允许在一端进行插入或删除操作的线性表
    2. 栈顶：线性表允许进行插入删除的那一端
    3. 栈底：固定的，不允许进行插入和删除的另一端
    4. 空栈：不含任何元素
    5. 特点：后进先出（LIFO）
  2. 基本操作
    1. InitStack(&S)：初始化一个空栈S
    2. StackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回false
    3. Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶
    4. Pop(&S,%=&x)：出栈，若栈S非空，则用x返回栈顶元素
    5. GetTop(S,&x)：读栈顶元素，若栈S非空，则用x返回栈顶元素
    6. DestroyStack(&S)：销毁栈，并释放栈S占用的存储空间
  3. 卡特兰数：n个不同元素进栈，出栈元素的不同排列的个数为 1 n + 1 C 2 n n \frac{1}{n+1}C^n_{2n} n+11​C2nn​

栈的顺序存储结构

  1. 顺序栈的定义
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
   
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

void testStack(){
   
    SqStack S;       //声明一个顺序栈(分配空间)
                     //连续的存储空间大小为 MaxSize*sizeof(ElemType)
}
  1. 基本操作
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
   
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

//初始化栈
void InitStack(SqStack &S){
   
    S.top = -1;                   //初始化栈顶指针
}

//判栈空
bool StackEmpty(SqStack S){
   
    if(S.top == -1)      //栈空
        return true;
    else                 //栈不空
        return false;
}

//新元素进栈
bool Push(SqStack &S, ElemType x){
   
    if(S.top == MaxSize - 1)        //栈满
        return false;

    S.top = S.top + 1;    //指针先加1
    S.data[S.top] = x;    //新元素入栈

    /*
    S.data[++S.top] = x;
    */
    
    return true;
}

//出栈
bool Pop(SqStack &x, ElemType &x){
   
    if(S.top == -1)          //栈空
        return false;
    
    x = S.data[S.top];       //先出栈
    S.top = S.top - 1;       //栈顶指针减1
    return true;

    /*
    x = S.data[S.top--];
    */

    //只是逻辑上的删除，数据依然残留在内存里
}

//读栈顶元素
bool GetTop(SqStack S, ElemType &x){
   
    if(S.top == -1)
        return false;
    
    x = S.data[S.top];      //x记录栈顶元素
    return true; 
}


void testStack(){
   
    SqStack S;       //声明一个顺序栈(分配空间)
    InitStack(S);
    //...
}
  1. 栈满条件：top==MaxSize
  2. 顺序栈的缺点：栈的大小不可变
  3. 共享栈
    1. 定义：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

栈的链式存储结构

与链表类似，入栈和出栈的操作都在链表的表头进行

队列

队列的概念

  1. 定义：队列是只允许在一端进行插入（入队），在另一端删除（出队）的线性表
  2. 队头：允许删除的一端
  3. 队尾：允许插入的一端
  4. 空队列：不含任何元素的空表
  5. 队列的特点：先进先出（FIFO）
  6. 队列的基本操作
    1. InitQueue(&Q): 初始化队列，构造一个空队列Q
    2. DestroyQueue(&Q): 销毁队列，并释放队列Q所占用的内存空间
    3. EnQueue(&Q, x): 入队，若队列Q未满，将x加入，使之成为新的队尾
    4. DeQueue(&Q, &x): 出队，若队列Q非空，删除队头元素，并用x返回
    5. GetHead(Q,&x): 读队头元素，若队列Q非空，则将队头元素赋值给x
    6. QueueEmpty(Q): 判队列空，若队列Q为空，则返回true，否则返回false

队列的顺序存储结构

  1. 队列的顺序实现
# define MaxSize 10;     //定义队列中元素的最大个数
typedef struct{
   
    ElemType data[MaxSize];   //用静态数组存放队列元素
    int front, rear;          //队头指针和队尾指针
}SqQueue;
  1. 初始化操作
//初始化队列
void InitQueue(SqQueue &Q){
   
    //初始化时，队头、队尾指针指向0
    Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue 0){
   
    if(Q.rear == Q.front)    //队空条件
        return true;
    else 
        return false;
}
  1. 入队操作
bool EnQueue(SqQueue &Q, ElemType x){
   
    if((Q.rear+1)%MaxSize == Q.front)    //队满
        return false;    //队满报错
    Q.data[Q.rear] = x;    //将x插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;    //队尾指针加1取模
    return true;
}
  1. 出队操作
//出队，删除一个队头元素，用x返回
bool DeQueue(SqQueue &Q, ElemType &x){
   
    if(Q.rear == Q.front)              //队空报错
        return false;  
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize; //队头指针后移动
    return true;
}
  1. 获得队头元素
bool GetHead(SqQueue &Q, ElemType &x){
   
    if(Q.rear == Q.front)              //队空报错
        return false;  
    x = Q.data[Q.front];
    return true;
}
  1. 判断队列已满/已空
    1. 方案一：牺牲一个存储单元（实现代码同1）
      1. 初始化时：rear=front=0;
      2. 队空条件：Q.rear==Q.front;
      3. 队满条件：(Q.rear+1)%MaxSize == Q.front
      4. 队列元素个数：(rear+MaxSize-front)%MaxSize;
    2. 方案二
      1. 实现
      #define MaxSize 10;     //定义队列中元素的最大个数
typedef struct{
       
    ElemType data[MaxSize];   //用静态数组存放队列元素
    int front, rear;          //队头指针和队尾指针
    int size;
}SqQueue;
      1. 初始化时
      rear=front=0;
size=0;
      1. 插入成功：size++;
      2. 删除成功：size--;
      3. 队满条件：size==Maxsize;
      4. 队空条件：size==0;
    3. 方案三
      1. 实现
      #define MaxSize 10;     //定义队列中元素的最大个数
typedef struct{
       
    ElemType data[MaxSize];   //用静态数组存放队列元素
    int front, rear;          //队头指针和队尾指针
    int tag;    //最近进行的是删除/插入
}SqQueue;
      1. 初始化时
      rear=front=0;
tag=0;
      1. 插入成功：tag=1;
      2. 删除成功：tag=0;
      3. 队满条件：rear==front&&tag==1;
      4. 队空条件：rear==front&&tag==0;

队列的链式存储结构

  1. 定义队列
typedef struct LinkNode{
         //链式队列结点
    ElemType data;
    struct LinkNode *next;
}

typedef struct{
                  //链式队列
    LinkNode *front, *rear;   //队列的队头和队尾指针
}LinkQueue;

  1. 初始化

    1. 带头结点
    void InitQueue(LinkQueue &Q){
     
    //初始化时，front、rear都指向头结点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front -> next = NULL;
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
     
    if(Q.front == Q.rear)     //也可用 Q.front -> next == NULL
        return true;
    else
        return false;
}
    1. 不带头结点
    void InitQueue(LinkQueue &Q){
     
    //初始化时，front、rear都指向NULL
    Q.front = NULL;
    Q.rear = NULL;
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
     
    if(Q.front == NULL)
        return true;
    else
        return false;
}

  2. 入队

    1. 带头结点
    //新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
     
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;     //s作为最后一个结点，指针域指向NULL
    Q.rear->next = s;   //新结点插入到当前的rear之后
    Q.rear = s;         //表尾指针指向新的表尾
}
    1. 不带头结点
    //新元素入队
void EnQueue(LinkQueue &Q, ElemType x){
     
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;
    if(Q.front==NULL){
         //在空队列中插入第一个元素
	    Q.front=s;    //修改队头队尾指针
	    Q.rear=s;
    }else{
     
	    Q.rear->next=s;    //新结点插入到rear结点之后
	    Q.rear=s;    //修改rear指针
    }
}

  3. 出队

    1. 带头结点
    //队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
     
    if(Q.front == Q.rear)
        return false;                    //空队

    LinkNode *p = Q.front->next;    //p指针指向即将删除的结点
    x = p->data;
    Q.front->next = p->next;             //修改头结点的next指针
    if(Q.rear == p)                      //此次是最后一个结点出队
        Q.rear = Q.front;                //修改rear指针
    free(p);                             //释放结点空间

    return true;
}
    1. 不带头结点
    //队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
     
    if(Q.front == Q.rear)
        return false;                    //空队

    LinkNode *p = Q.front;    //p指针指向即将删除的结点
    x = p->data;
    Q.front = p->next;             //修改头结点的next指针
    if(Q.rear == p){
         //此次是最后一个结点出队
	    Q.rear==NULL:
	    Q.front==NULL;
    }                      
    free(p);     //释放结点空间
    return true;
}

双端队列

  1. 定义：只允许从两端插入、两端删除的线性表
    1. 输入受限的双端队列：允许一端插入，两端删除的线性表
    2. 输出受限的双端队列：允许两端插入，一端删除的线性表

栈和队列的应用

栈在括号匹配中的应用

#define MaxSize 10   

typedef struct{
   
    char data[MaxSize];
    int top;
} SqStack;

//初始化栈
InitStack(SqStack &S)

//判断栈是否为空
bool StackEmpty(SqStack &S)

//新元素入栈
bool Push(SqStack &S, char x)

//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x)

bool bracketCheck(char str[], int length){
   
    SqStack S;      //声明
    InitStack(S);   //初始化栈

    for(int i=0; i<length; i++){
   
        if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
   
            Push(S, str[i]);       //扫描到左括号，入栈
        }else{
   
            if(StackEmpty(S))      //扫描到右括号，且当前栈空
                return false;      //匹配失败
            
            char topElem;          //存储栈顶元素
            Pop(S, topElem);       //栈顶元素出栈

            if(str[i] == ')' && topElem != '(' )
                return false;

            if(str[i] == ']' && topElem != '[' )
                return false;

            if(str[i] == '}' && topElem != '{' )
                return false;       
        }
    }

    StackEmpty(S); //栈空说明匹配成功
}

栈在表达式值中的应用

中缀表达式
(需要界限符)

  1. 规则：运算符在两个操作数中间
  2. 例
    1. a + b
    2. a + b - c
    3. a + b - c*d

后缀表达式 (逆波兰表达式)

  1. 规则：运算符在两个操作数后面
  2. 例
    1. a b +
    2. ab+ c - / a bc- +
    3. ab+ cd* -
  3. 中缀表达式转后缀表达式
    1. 确定中缀表达式中各个运算符的运算顺序
    2. 选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
    3. 如果还有运算符没被处理，继续步骤2

“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)

  1. 用栈实现中缀表达式转后缀表达式
    1. 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况
      1. 遇到操作数: 直接加入后缀表达式
      2. 遇到界限符: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘(’ 为止。注意: ‘(’ 不加入后缀表达式
      3. 遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈
    2. 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式
  2. 后缀表达式的计算：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数
  3. 用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）
    1. 从左往后扫描下一个元素，直到处理完所有元素
    2. 若扫描到操作数，则压入栈，并回到步骤1;否则执行步骤3
    3. 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤1

先出栈的是“右操作数”

前缀表达式 (波兰表达式)

  1. 规则：运算符在两个操作数前面
  2. 例
      • a b
    2. +ab c
      • +ab *cd
  3. 中缀表达式转前缀表达式
    1. 确定中缀表达式中各个运算符的运算顺序
    2. 选择下一个运算符，按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数
    3. 如果还有运算符没被处理，就继续执行步骤2

“右优先”原则: 只要右边的运算符能先计算，就优先算右边的;

  1. 用栈实现前缀表达式的计算
    1. 从右往左扫描下一个元素，直到处理完所有元素
    2. 若扫描到操作数则压入栈，并回到步骤1，否则执行步骤3
    3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤1；

先出栈的是“左操作数”

4.中缀表达式的计算(用栈实现)：两个算法的结合： 中缀转后缀 + 后缀表达式的求值
1. 初始化两个栈，操作数栈和运算符栈
2. 若扫描到操作数，压入操作数栈
3. 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈 (期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈项元素并执行相应运算，运算结果再压回操作数栈)

栈在递归中的应用

  1. 函数调用的特点：最后被调用的函数最先执行结束(LIFO)
  2. 函数调用时，需要用一个栈存储
    1. 调用返回地址
    2. 实参
    3. 局部变量
  3. 递归调用时，函数调用栈称为 “递归工作栈”
    1. 每进入一层递归，就将递归调用所需信息压入栈顶
    2. 每退出一层递归，就从栈顶弹出相应信息
    3. 缺点： 太多层递归可能回导致栈溢出

数组和特殊矩阵

数组的定义

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

数组的存储结构

  1. 一维数组
    1. 各数组元素大小相同，物理上连续存放
    2. 数组下标：默认从0开始
    3. 数组元素 a[i] 的存放地址 = L O C + i ∗ s i z e o f ( E l e m T y p e ) LOC + i * sizeof(ElemType) LOC+i∗sizeof(ElemType)
      1. LOC为数组起始地址
  2. 二维数组
    1. 行优先/列优先存储优点：实现随机存储
    2. M行N列的二维数组 b[M][N] 中，b[i][j]的存储地址：
      1. 行优先存储: L O C + ( i × N + j ) × s i z e o f ( E l e m T y p e ) LOC + (i×N + j) × sizeof(ElemType) LOC+(i×N+j)×sizeof(ElemType)
      2. 列优先存储： L O C + ( j × M + i ) × s i z e o f ( E l e m T y p e ) LOC + (j×M + i) × sizeof(ElemType) LOC+(j×M+i)×sizeof(ElemType)
  3. 普通矩阵的存储：使用二维数组存储

描述矩阵元素时，行、列号通常从1开始
描述数组时，通常下标从 0 开始

特殊矩阵的压缩存储

矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

  1. 对称矩阵
    1. 若n 阶方阵中任意一个元素 a i , j a_{i,j} ai,j​都有 a i , j = a j , i a_{i,j}=a_{j,i} ai,j​=aj,i​则该矩阵为对称矩阵
    2. 策略：只存储主对角线+下三角区；按行优先原则将各元素存入一维数组中
    3. 数组大小： n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1)​
    4. 元素下标对应关系：k为 a i , j a_{i,j} ai,j​在一维数组中的下标

k = { i ( i − 1 ) 2 + j − 1 , i ≥ j ( 下三角区和主对角线元素 ) j ( j − 1 ) 2 + i − 1 , i < j ( 上三角区元素 a i , j = a j , i )   k= \left\{ \begin{array}{l} \frac{i(i-1)}{2}+j-1, \quad i \ge j \quad (下三角区和主对角线元素) \\ \frac{j(j-1)}{2}+i-1, \quad i<j \quad (上三角区元素a_{i,j}=a_{j,i}) \ \end{array} \right. k={ 2i(i−1)​+j−1,i≥j(下三角区和主对角线元素)2j(j−1)​+i−1,i<j(上三角区元素ai,j​=aj,i​) ​

  1. 三角矩阵
    1. 以主对角线划分，三角矩阵有上（下）三角两种。上（下）三角矩阵的下（上）三角（不含主对角线）中的元素均为常数。在大多数情况下，三角矩阵常数为零
    2. 策略：按行优先原则将元素存入一维数组中（同对称矩阵）。并在最后一个位置存储常量
    3. 元素下标对应关系：k为 a i , j a_{i,j} ai,j​在一维数组中的下标

k = { i ( i − 1 ) 2 + j − 1 , i ≥ j ( 下三角区和主对角线元素 ) n ( n + 1 ) 2 , i < j ( 上三角区元素 a i , j = a j , i )   k= \left\{ \begin{array}{l} \frac{i(i-1)}{2}+j-1, \quad i \ge j \quad (下三角区和主对角线元素) \\ \frac{n(n+1)}{2}, \quad i<j \quad (上三角区元素a_{i,j}=a_{j,i}) \ \end{array} \right. k={ 2i(i−1)​+j−1,i≥j(下三角区和主对角线元素)2n(n+1)​,i<j(上三角区元素ai,j​=aj,i​) ​
3. 三对角矩阵（带状矩阵）
1. 当 ∣ i − j ∣ > 1 |i-j|>1 ∣i−j∣>1时，有 a i , j = 0 ( 1 ≤ i , j ≤ n ) a_{i,j}=0 (1 \leq i,j \leq n) ai,j​=0(1≤i,j≤n)
2. 策略：按行优先(或列优先) 原则，只存储带状部分
3. 元素下标对应关系：k为 a i , j a_{i,j} ai,j​在一维数组中的下标 k=2i+j-3

稀疏矩阵

  1. 非零元系远远少于矩阵元素的个数
  2. 策略
    1. 顺序存储——三元组<行,列,值>
      1. 会失去随机存取的特性
    2. 十字链表法
阅读全部

相关推荐

  3. 数据结构---栈和队列

    2024-02-17 00:10:02       40 阅读

  5. 数据结构:栈和队列

    2024-02-17 00:10:02       38 阅读

  6. 「数据结构」栈和队列

    2024-02-17 00:10:02       23 阅读

  7. 【数据结构】栈和队列

    2024-02-17 00:10:02       23 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-02-17 00:10:02       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-02-17 00:10:02       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-02-17 00:10:02       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-02-17 00:10:02       20 阅读

热门阅读

  2. 网络安全的新防线：主动进攻，预防为先

    2024-02-17 00:10:02       29 阅读

  7. C# 避免UI线程阻塞

    2024-02-17 00:10:02       30 阅读

  10. Vue源码系列讲解——模板编译篇【五】(优化阶段)

    2024-02-17 00:10:02       30 阅读

  12. 2024 前端面试题 附录3

    2024-02-17 00:10:02       36 阅读

  16. 贪心，暴力枚举

    2024-02-17 00:10:02       36 阅读

  18. Git 存储大文件

    2024-02-17 00:10:02       36 阅读

  21. spring boot 使用AOP实现是否已登录检测

    2024-02-17 00:10:02       30 阅读

  24. C语言程序设计：编程计算求e近似值： 用while语句求直到最后一项值小于10-5为止。e=0+1+1/1+1/1/2+1/1/2/3...

    2024-02-17 00:10:02       28 阅读