首页 > 其他分享 >王道视频-数据结构-笔记3：栈和队列

王道视频-数据结构-笔记3：栈和队列

时间：2023-02-06 13:35:50浏览次数：46  
标签：结点 return 队列 元素 C++ 王道 数据结构 rear


文章目录

  • 0 笔记说明
  • 1 栈
  • 1.1 栈的定义
  • 1.2 栈的基本操作描述
  • 1.3 顺序栈
  • 1.3.1 顺序栈的基本操作
  • 1.3.1.1 初始化
  • 1.3.1.1.1 方式1
  • 1.3.1.1.2 方式2
  • 1.3.1.2 判空
  • 1.3.1.2.1 方式1
  • 1.3.1.2.2 方式2
  • 1.3.1.3 入栈
  • 1.3.1.3.1 方式1
  • 1.3.1.3.2 方式2
  • 1.3.1.4 出栈
  • 1.3.1.4.1 方式1
  • 1.3.1.4.2 方式2
  • 1.3.1.5 读取栈顶元素
  • 1.3.1.5.1 方式1
  • 1.3.1.5.2 方式2
  • 1.3.1.6 判满
  • 1.3.1.6.1 方式1
  • 1.3.1.6.2 方式2
  • 1.3.1.7 销毁/清空栈
  • 1.3.1.7.1 方式1
  • 1.3.1.7.2 方式2
  • 1.4 链栈
  • 1.4.1 链栈（不带头结点）的基本操作
  • 1.4.1.1 初始化
  • 1.4.1.2 判空
  • 1.4.1.3 入栈
  • 1.4.1.4 出栈
  • 1.4.1.5 读取栈顶元素
  • 1.4.1.6 销毁/清空链栈
  • 1.5 共享栈
  • 1.5.1 共享栈的基本操作
  • 1.5.1.1 初始化
  • 1.5.1.2 判满
  • 1.5.1.3 判空
  • 1.5.1.4 入栈
  • 1.5.1.5 出栈
  • 1.5.1.6 读取栈顶元素
  • 1.5.1.7 销毁/清空共享栈
  • 2 队列
  • 2.1 队列的定义
  • 2.2 队列的基本操作描述
  • 2.3 顺序队列
  • 2.3.1 顺序队列的基本操作
  • 2.3.1.1 初始化
  • 2.3.1.2 入队
  • 2.3.1.3 出队
  • 2.3.1.4 获取队头元素
  • 2.3.1.5 判空
  • 2.3.1.6 判满
  • 2.3.1.7 销毁顺序队列
  • 2.3.1.8 判断顺序队列的长度
  • 2.3.2 顺序队列的变形
  • 2.3.2.1 加上size变量
  • 2.3.2.2 加上tag变量
  • 2.3.2.3 rear指向队尾元素
  • 2.4 链队列
  • 2.4.1 链队列的基本操作
  • 2.4.1.1 初始化
  • 2.4.1.1.1 带头结点
  • 2.4.1.1.2 不带头结点
  • 2.4.1.2 入队
  • 2.4.1.2.1 带头结点
  • 2.4.1.2.2 不带头结点
  • 2.4.1.3 出队
  • 2.4.1.3.1 带头结点
  • 2.4.1.3.2 不带头结点
  • 2.4.1.4 获取队头元素
  • 2.4.1.4.1 带头结点
  • 2.4.1.4.2 不带头结点
  • 2.4.1.5 判空
  • 2.4.1.5.1 带头结点
  • 2.4.1.5.2 不带头结点
  • 2.4.1.6 销毁顺序队列
  • 2.4.1.6.1 带头结点
  • 2.4.1.6.2 不带头结点
  • 2.4.1.7 判断链队列的长度
  • 2.4.1.7.1 带头结点
  • 2.4.1.7.2 不带头结点
  • 2.5 双端队列
  • 3 栈的应用
  • 3.1 括号匹配
  • 3.2 表达式求值
  • 3.3 函数调用栈
  • 3.4 递归工作栈
  • 4 队列的应用
  • 4.1 图的广度优先遍历
  • 4.2 操作系统中的资源分配

0 笔记说明

博客内容是对自己笔记的书面整理，根据自身学习需要，我可能会增加必要内容。

1 栈

1.1 栈的定义

栈(Stack)是一种操作受限的线性表，只允许在一端进行插入或删除操作。其逻辑结构与普通的线性表相同，但是对数据的运算如插入、删除操作有区别。栈的特点是LIFO，Last In First Out，即后进先出。根据下图给出空栈、栈底、栈顶的概念：

王道视频-数据结构-笔记3：栈和队列_初始化


允许插入和删除的一端称为栈顶；不允许插入和删除的一端称为栈底。第一个元素为栈底元素，最后一个为栈顶元素。n个不同元素进栈，出栈元素构成的排列个数为：

王道视频-数据结构-笔记3：栈和队列_队列_02


上述公式称为卡特兰(Catalan)数。

1.2 栈的基本操作描述

（1）InitStack(&S)：初始化栈。构造一个空栈s，给其分配内存空间。

（2）DestroyStack(&S)：销毁/清空栈。销毁/清空栈并释放栈s所占用的内存空间。

（3）Push(&S,x)：进栈，若栈s未满，则将x加入使之成为新的栈顶元素。

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

（5）GetTop(S,&x)：读栈顶元素。若栈s非空，则用x返回栈顶元素。栈的使用场景中大多只访问栈顶元素。

（6）StackEmpty(S)：判断一个栈s是否为空。若s为空，则返回true，否则返回false。

1.3 顺序栈

顺序栈即顺序存储的栈。定义顺序栈的C++代码如下：

#define MaxSize 10 //定义栈中最多可容纳的元素个数
typedef struct{
    ElemType data[MaxSize]; //用静态数组存放栈中元素
    int top; //栈顶指针
}SqStack;

顺序栈的缺点是栈的大小不可变。

1.3.1 顺序栈的基本操作

1.3.1.1 初始化
1.3.1.1.1 方式1

初始化栈的C++代码如下：

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

top指向栈顶元素，初始化时设置栈顶指针为-1，然后给栈的各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)。

1.3.1.1.2 方式2

初始化栈的C++代码如下：

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

top指向下一个可以插入元素的位置，初始化时设置栈顶指针为0，然后给栈的各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)。

1.3.1.2 判空
1.3.1.2.1 方式1

判断栈是否为空的C++代码如下：

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

时间复杂度是O(1)。

1.3.1.2.2 方式2

判断栈是否为空的C++代码如下：

bool StackEmpty(SqStack S){
    if(S.top==0)
        return true;
    else
        return false;
}

时间复杂度是O(1)。

1.3.1.3 入栈
1.3.1.3.1 方式1

新元素入栈的C++代码如下：

bool Push(SqStack &S,ElemType x){ //新元素入栈操作
    if(S.top==MaxSize-1) //栈已满
        return false;
    S.data[++S.top]=x; //先让指针加1,然后让新元素入栈
    return true;
}

时间复杂度是O(1)。

1.3.1.3.2 方式2

新元素入栈的C++代码如下：

bool Push(SqStack &S,ElemType x){ //新元素入栈操作
    if(S.top==MaxSize) //栈已满
        return false;
    S.data[S.top++]=x; //先让新元素入栈,然后让指针加1
    return true;
}

时间复杂度是O(1)。

1.3.1.4 出栈
1.3.1.4.1 方式1

C++代码如下：

bool Pop(SqStack &S,ElemType &x){ //栈顶元素出栈，并将值返回给x
    if(S.top==-1) //栈空,报错
        return false;
    x=S.data[S.top--]; //栈顶元素出栈后top指针再减1
    return true;
}

时间复杂度是O(1)。注意：数据还残留在内存中，只是逻辑上被删除了。

1.3.1.4.2 方式2

C++代码如下：

bool Pop(SqStack &S,ElemType &x){ //栈顶元素出栈，并将值返回给x
    if(S.top==0) //栈空,报错
        return false;
    x=S.data[--S.top]; //top指针再减1后栈顶元素出栈
    return true;
}

时间复杂度是O(1)。注意：数据还残留在内存中，只是逻辑上被删除了。

1.3.1.5 读取栈顶元素
1.3.1.5.1 方式1

读取栈顶元素的C++代码如下：

bool GetTop(SqStack S,ElemType &x){ //读取栈顶元素，并将值返回给x
    if(S.top==-1) //栈空,报错
        return false;
    x=S.data[S.top]; //将栈顶元素的值返回给x
    return true;
}

时间复杂度是O(1)。

1.3.1.5.2 方式2

读取栈顶元素的C++代码如下：

bool GetTop(SqStack S,ElemType &x){ //读取栈顶元素，并将值返回给x
    if(S.top==0) //栈空,报错
        return false;
    x=S.data[S.top-1]; //将栈顶元素的值返回给x
    return true;
}

时间复杂度是O(1)。

1.3.1.6 判满
1.3.1.6.1 方式1

判断栈是否已满的C++代码如下：

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

时间复杂度是O(1)。

1.3.1.6.2 方式2

判断栈是否已满的C++代码如下：

bool StackFull(SqStack S){
    if(S.top==MaxSize)
        return true;
    else
        return false;
}

时间复杂度是O(1)。

1.3.1.7 销毁/清空栈
1.3.1.7.1 方式1

销毁/清空栈的C++代码如下：

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

由于是使用静态数组给顺序栈分配内存空间，因此销毁栈时只需要使top指针恢复为-1即可，在主程序运行结束后系统会自动回收顺序栈的内存空间。

1.3.1.7.2 方式2

销毁/清空栈的C++代码如下：

void DestroyStack(SqStack &S){
    S.top=0;
}

由于是使用静态数组给顺序栈分配内存空间，因此销毁栈时只需要使top指针恢复为0即可，在主程序运行结束后系统会自动回收顺序栈的内存空间。

1.4 链栈

链栈即链式存储的栈。定义链栈的C++代码如下：

typedef struct Linknode{
    ElemType data; //数据域
    struct Linknode *next; //指针域
}*LiStack;

将链头作为栈顶，入栈/出栈都只能在栈顶一端进行。链栈也分带头结点和不带头结点的，以下只讨论不带头结点的链栈。

1.4.1 链栈（不带头结点）的基本操作

1.4.1.1 初始化

初始化不带头结点的链栈的C++代码如下：

bool InitStack(LiStack &S){
    S=NULL; //刚开始没有结点
    return true;
}

1.4.1.2 判空

判断不带头结点的链栈是否为空的C++代码如下：

bool StackEmpty(LiStack S){
    return S==NULL;
}

时间复杂度是O(1)。

1.4.1.3 入栈

对于不带头结点的链栈，新元素入栈的C++代码如下：

bool Push(LiStack &S,ElemType x){
    Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
    if(s==NULL) //内存不足，创建失败
        return false;
    s->data=x;
    s->next=S;
    S=s; //将结点s插入链栈
    return true;
}

时间复杂度是O(1)。

1.4.1.4 出栈

对于不带头结点的链栈，栈顶元素出栈的C++代码如下：

bool Pop(LiStack &S,ElemType &x){
    if(S==NULL)
        return false; //栈空则返回NULL
    x=S->data;
    Linknode *p=S;
    S=S->next;
    free(p);
    return true;
}

时间复杂度是O(1)。

1.4.1.5 读取栈顶元素

对于不带头结点的链栈，读取栈顶元素的C++代码如下：

bool GetTop(LiStack S,ElemType &x){ //读取栈顶元素，并将值返回给x
    if(S==NULL) //栈空,报错
        return false;
    x=S->data; //将栈顶元素的值返回给x
    return true;
}

时间复杂度是O(1)。

1.4.1.6 销毁/清空链栈

对于不带头结点的链栈，销毁/清空栈的C++代码如下：

void DestroyStack(LiStack &S){
    Linknode *p,*s=S;
    while(s!=NULL){
        p=s;
        s=s->next;
        free(p);
    }
    S=NULL; //令链栈头指针为NULL
}

下面分析上述代码的时间复杂度，只需要关注最深层循环语句（第4行代码）的执行次数与问题规模n的关系，这里n是链栈的元素总个数，此时该语句执行n次，所以时间复杂度=O(n)。

1.5 共享栈

共享栈指两个栈共享同一片空间，利用的是栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。定义共享栈的C++代码如下：

#define MaxSize 10 //定义栈中最多可容纳的元素个数
typedef struct{
    ElemType data[MaxSize]; //用静态数组存放栈中元素
    int top0; //0号栈的栈顶指针
    int top1; //1号栈的栈顶指针
}ShStack;

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

1.5.1 共享栈的基本操作

1.5.1.1 初始化

初始化共享栈的C++代码如下：

void InitStack(ShStack &S){
    S.top0=-1; //初始化0号栈的栈顶指针
    S.top1=MaxSize; //初始化1号栈的栈顶指针
}

0号栈、1号栈的栈顶分别在分配的静态数组的两端，两个指针top0、top1分别指向各自的栈顶元素，初始化时设置top0为-1、top1为MaxSize，然后给共享栈的各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)。

1.5.1.2 判满

判断栈是否已满的C++代码如下：

bool StackFull(ShStack S){
    if(S.top0+1==S.top1)
        return true;
    else
        return false;
}

时间复杂度是O(1)。

1.5.1.3 判空

判断栈是否为空的C++代码如下：

bool StackEmpty(ShStack S){
    if(S.top0==-1 && S.top1==MaxSize)
        return true;
    else
        return false;
}

时间复杂度是O(1)。

1.5.1.4 入栈

新元素入栈的C++代码如下：

bool Push(ShStack &S,ElemType x,int i){ //新元素入栈操作,需要指定加入哪个栈
    if(S.top0+1==S.top1) //栈已满
        return false;
    if(i==0) //当0号栈进栈时top0先加1再赋值
        S.data[++S.top0]=x;
    else //1号栈进栈时top1先减1再赋值
        S.data[--S.top1]=x;
    return true;
}

时间复杂度是O(1)。

1.5.1.5 出栈

C++代码如下：

bool Pop(ShStack &S,ElemType &x,int i){ //栈顶元素出栈，并将值返回给x,需要指定哪个栈出栈
    if(i==0){
        if(S.top0==-1) //0号栈栈空,报错
            return false;
        x=S.data[S.top0--]; //栈顶元素出栈后top指针再减1
    }
    if(i==1){
        if(S.top1==MaxSize) //1号栈栈空,报错
            return false;
        x=S.data[S.top1++]; //栈顶元素出栈后top指针再加1
    }
    return true;
}

时间复杂度是O(1)。注意：数据还残留在内存中，只是逻辑上被删除了。

1.5.1.6 读取栈顶元素

读取栈顶元素的C++代码如下：

bool GetTop(ShStack S,ElemType &x,int i){ //读取栈顶元素，并将值返回给x，需要指定读取哪个栈
    if(i==0){
        if(S.top0==-1) //0号栈栈空,报错
            return false;
        x=S.data[S.top0]; //读取栈顶元素
    }
    if(i==1){
        if(S.top1==MaxSize) //1号栈栈空,报错
            return false;
        x=S.data[S.top1]; //读取栈顶元素
    }
    return true;
}

时间复杂度是O(1)。

1.5.1.7 销毁/清空共享栈

销毁/清空栈的C++代码如下：

void DestroyStack(ShStack &S){
    S.top0=-1;
    S.top1=MaxSize;
}

由于是使用静态数组给共享栈分配内存空间，因此销毁栈时只需要使top0、top1恢复为-1、MaxSize即可，在主程序运行结束后系统会自动回收共享栈的内存空间。

2 队列

2.1 队列的定义

队列(Queue)是一种操作受限的线性表，只允许在一端进行插入，在另一端进行删除操作。其逻辑结构与普通的线性表相同，但是对数据的运算如插入、删除操作有区别。队列的特点是FIFO，First In First Out，即先进先出。允许插入的一端称为队尾，允许删除的一端称为队头。在队头的第一个元素为队头元素，在队尾的最后一个元素为队尾元素。空队列就是没有元素的队列。

2.2 队列的基本操作描述

（1）lnitQueue(&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。

2.3 顺序队列

顺序队列是用顺序存储实现的队列。定义顺序队列的C++代码如下：

#define MaxSize 10 //队列可容纳元素的最多个数
typedef struct{
    ElemType data[MaxSize]; //使用静态数组存放队列元素
    int front,rear; //队头、队尾指针
}SqQueue;

其中front指向队头元素，rear指向队尾元素的后一个位置，即下一个元素应该插入的位置。

2.3.1 顺序队列的基本操作

2.3.1.1 初始化

初始化顺序队列的C++代码如下：

void InitQueue(SqQueue &Q){
    Q.frnotallow=Q.rear=0; //初始化两个指针均指向0号元素
}

初始化时设置两个指针均指向0号元素，然后给顺序队列的各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)。

2.3.1.2 入队

取模运算：有两个整数a,b，则a%b等于a除以b后得到的余数。取模运算将无限的整数域映射到有限的整数集合{0,1,2,…,b-1)上。

对于顺序队列，只能从队尾插入元素。新元素入队的C++代码如下：

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front) //队满条件
        return false;
    Q.data[Q.rear]=x; //新元素插入队尾
    Q.rear=(Q.rear+1)%MaxSize; //队尾指针+1再取模
    return true;
}

上述代码中​​Q.rear=(Q.rear+1)%MaxSize​​​使用了模运算，从而将线状存储空间即{0,1,2,…,MaxSize-1}在逻辑上变成“环状”，即变为循环队列。队列满的条件是队尾指针的下一位置是队头，即​​(Q.rear+1)%MaxSize==Q.front​​。这样的代价是需要牺牲一个存储单元。代码的时间复杂度是O(1)。

2.3.1.3 出队

对于顺序队列，只能让队头元素出队。队头元素出队的C++代码如下：

bool DeQueue(SqQueue &Q,ElemType &x){ //删除队头元素，并用x返回
    if(Q.rear==Q.front) //队空
        return false;
    x=Q.data[Q.front];
    Q.frnotallow=(Q.front+1)%MaxSize;
    return true;
}

上述代码中​​Q.frnotallow=(Q.front+1)%MaxSize​​​也使用了模运算，从而将线状存储空间即{0,1,2,…,MaxSize-1}在逻辑上变成“环状”，即变为循环队列。队列空的条件是队尾指针等于队头指针，即​​Q.rear==Q.front​​。代码的时间复杂度是O(1)。

2.3.1.4 获取队头元素

对于顺序队列，只能获取队头元素的值。C++代码如下：

bool GetHead(SqQueue Q,ElemType &x){ //获取队头元素的值，并用x返回
    if(Q.rear==Q.front) //队空
        return false;
    x=Q.data[Q.front];
    return true;
}

与【2.3.1.3 出队】一节的代码相比，本节代码少了语句​​Q.frnotallow=(Q.front+1)%MaxSize​​。代码的时间复杂度是O(1)。

2.3.1.5 判空

判断顺序队列是否为空的C++代码如下：

bool QueueEmpty(SqQueue Q){
    return Q.rear==Q.front;
}

时间复杂度是O(1)。

2.3.1.6 判满

判断顺序队列是否已满的C++代码如下：

bool QueueFull(SqQueue Q){
    return Q.frnotallow==(Q.rear+1)%MaxSize;
}

时间复杂度是O(1)。

2.3.1.7 销毁顺序队列

销毁顺序队列的C++代码如下：

void DestroyQueue(SqQueue &Q){
    Q.frnotallow=Q.rear=0; //将两个指针均指向0号元素即可
}

时间复杂度是O(1)。

2.3.1.8 判断顺序队列的长度

判断顺序队列的长度的C++代码如下：

int LengthQueue(SqQueue Q){
    return (Q.rear+MaxSize-Q.front)%MaxSize;
}

时间复杂度是O(1)。

2.3.2 顺序队列的变形

上面实现的顺序队列的队列满的条件是队尾指针的下一位置是队头，即​​(Q.rear+1)%MaxSize==Q.front​​。这样的代价是需要牺牲一个存储单元。也可以换个方法，使得不需要浪费一个存储单元。

2.3.2.1 加上size变量

修改定义顺序队列的C++代码如下：

#define MaxSize 10 //队列可容纳元素的最多个数
typedef struct{
    ElemType data[MaxSize]; //使用静态数组存放队列元素
    int front,rear; //队头、队尾指针
    int size; //队列当前长度
}SqQueue;

其中front仍然指向队头元素，rear仍然指向队尾元素的后一个位置，即下一个元素应该插入的位置。

顺序队列的基本操作会有一些变化：① 初始化时​​rear=frnotallow=0​​​，​​size=0​​​；② 插入元素成功时​​size++​​​，删除成功时​​size--​​​；③ 队空条件：​​size==0​​​；④ 队满条件​​size==MaxSize​​。

2.3.2.2 加上tag变量

修改定义顺序队列的C++代码如下：

#define MaxSize 10 //队列可容纳元素的最多个数
typedef struct{
    ElemType data[MaxSize]; //使用静态数组存放队列元素
    int front,rear; //队头、队尾指针
    int tag; //删除成功时令tag=0;插入成功时令tag=1
}SqQueue;

其中front仍然指向队头元素，rear仍然指向队尾元素的后一个位置，即下一个元素应该插入的位置。只有成功进行删除操作，才可能导致队空；只有成功进行插入操作，才可能导致队满。

顺序队列的基本操作会有一些变化：① 初始化时​​rear=frnotallow=0​​​，​​tag=0​​​；② 插入元素成功时​​tag=1​​​，删除成功时​​tag=0​​​；③ 队空条件：​​rear=front && tag==0​​​；④ 队满条件​​rear=front && tag==1​​。

2.3.2.3 rear指向队尾元素

front仍然指向队头元素，rear指向队尾元素。顺序队列的基本操作会有一些变化：① 初始化时​​rear=MaxSize-1，frnotallow=0​​​；② 入队时​​Q.rear=(Q.rear+1)%MaxSize，Q.data[Q.rear]=x​​​；③ 队空条件：​​（Q.rear+1)%MaxSize==Q.front​​。

2.4 链队列

链队列是用链式存储实现的队列。定义链队列的C++代码如下：

typedef struct LinkNode{ //链队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

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

2.4.1 链队列的基本操作

2.4.1.1 初始化
2.4.1.1.1 带头结点

C++代码如下：

void InitQueue(LinkQueue &Q){ //初始化带头结点的链队列
    Q.frnotallow=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); //开始时令两个指针均指向头结点
    Q.front->next=NULL;
}

时间复杂度是O(1)。

2.4.1.1.2 不带头结点

C++代码如下：

void InitQueue(LinkQueue &Q){ //初始化不带头结点的链队列
    Q.frnotallow=Q.rear=NULL; //刚开始令两个指针均指向NULL
}

时间复杂度是O(1)。

2.4.1.2 入队
2.4.1.2.1 带头结点

C++代码如下：

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; //新结点插到rear之后
    Q.rear=s; //修改rear指针，指向新结点
}

时间复杂度是O(1)。

2.4.1.2.2 不带头结点

C++代码如下：

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.frnotallow==NULL){ //在空队列中插入第一个元素需要特殊处理
        Q.frnotallow=s; //修改队头指针
        Q.rear=s; //修改队尾指针
    }
    else{
        Q.rear->next=s; //新结点插到rear之后
        Q.rear=s; //修改rear指针，指向新结点
    }
}

时间复杂度是O(1)。

2.4.1.3 出队
2.4.1.3.1 带头结点

C++代码如下：

bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.frnotallow==Q.rear)
        return false; //空队列
    LinkNode *p=Q.front->next;
    x=p->data; //用x返回队头元素的值
    Q.front->next=p->next; //修改头结点的next指针
    if(Q.rear==p) //若是最后一个结点出队
        Q.rear=Q.front; //修改rear指针
    free(p); //释放结点的空间
    return true;
}

时间复杂度是O(1)。

2.4.1.3.2 不带头结点

C++代码如下：

bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.frnotallow==NULL)
        return false; //空队列
    LinkNode *p=Q.front;
    x=p->data; //用x返回队头元素的值
    Q.frnotallow=p->next; //修改front指针
    if(Q.rear==p) //若是最后一个结点出队
        Q.rear=Q.frnotallow=NULL; //修改rear指针
    free(p); //释放结点的空间
    return true;
}

时间复杂度是O(1)。

2.4.1.4 获取队头元素
2.4.1.4.1 带头结点

C++代码如下：

bool GetHead(LinkQueue Q,ElemType &x){
    if(Q.frnotallow==Q.rear)
        return false; //空队列
    LinkNode *p=Q.front->next;
    x=p->data; //用x返回队头元素的值
    return true;
}

时间复杂度是O(1)。

2.4.1.4.2 不带头结点

C++代码如下：

bool GetHead(LinkQueue Q,int &x){
    if(Q.frnotallow==NULL)
        return false; //空队列
    LinkNode *p=Q.front;
    x=p->data; //用x返回队头元素的值
    return true;
}

时间复杂度是O(1)。

2.4.1.5 判空
2.4.1.5.1 带头结点

C++代码如下：

bool IsEmpty(LinkQueue Q){
    return Q.frnotallow==Q.rear;
}

时间复杂度是O(1)。

2.4.1.5.2 不带头结点

C++代码如下：

bool IsEmpty(LinkQueue Q){
    return Q.frnotallow==NULL;
}

时间复杂度是O(1)。

2.4.1.6 销毁顺序队列
2.4.1.6.1 带头结点

通过不断使队头元素出队，直至链队列中只剩下头结点，C++代码如下：

void DestroyQueue(LinkQueue &Q){
    ElemType temp;
    while(DeQueue(Q,temp));
}

时间复杂度是O(1)。

2.4.1.6.2 不带头结点

通过不断使队头元素出队，直至链队列中再无任何结点，C++代码如下：

void DestroyQueue(LinkQueue &Q){
    ElemType temp;
    while(DeQueue(Q,temp));
}

时间复杂度是O(1)。

2.4.1.7 判断链队列的长度
2.4.1.7.1 带头结点

C++代码如下：

int LengthQueue(LinkQueue Q){
    int length=0;
    LinkNode *p=Q.front->next;
    while(p!=NULL){
        length++;
        p=p->next;
    }
    return length;
}

时间复杂度是O(n)，n为链队列除头结点以外的结点个数。

2.4.1.7.2 不带头结点

C++代码如下：

int LengthQueue(LinkQueue Q){
    int length=0;
    LinkNode *p=Q.front;
    while(p!=NULL){
        length++;
        p=p->next; //修改头结点的next指针
    }
    return length;
}

时间复杂度是O(n)，n为链队列的结点个数。

2.5 双端队列

前面讨论过，栈是只允许从一端插入和删除的线性表。队列是只允许从一端插入、另一端删除的线性表。双端队列分为三种：

（1）普通的双端队列是只允许从两端插入、两端删除的线性表。若只使用双端队列其中一端的插入、删除操作，则效果等同于栈。

（2）输入受限的双端队列是只允许从一端插入、两端删除的线性表。

（3）输出受限的双端队列是只允许从两端插入、一端删除的线性表。

这里只是简单提一下双端队列，不详细列举其基本操作的代码了。

3 栈的应用

3.1 括号匹配

有三种括号：()、[]、{}。如下是一对括号字符串：

王道视频-数据结构-笔记3：栈和队列_队列_03


按方向分的话分为两种：左括号和右括号。观察上图可知：扫描括号字符串时，每出现一个右括号，就需要消耗一个左括号，并且扫描过程中最后出现的左括号最先被匹配，这正是LIFO，因此可以使用栈实现算法。算法逻辑：扫描括号字符串时，遇到左括号就入栈；遇到右括号，就弹出栈顶元素检查是否匹配：（1）若当前扫描到的右括号与栈顶左括号不匹配，则匹配失败。（2）若扫描到右括号且栈空，则匹配失败。（3）扫描完所有括号后，栈非空，则匹配失败。下面是算法流程图：

王道视频-数据结构-笔记3：栈和队列_Stack_04


下面是括号匹配全部代码：

#include<stdio.h>
#include<string.h> //包含函数strlen的头文件，该函数用于判断字符串的长度
#include<stdlib.h> //包含函数malloc、free的头文件
typedef struct LinkNode{ //定义链栈的结点
    char data;
    struct LinkNode *next;
}LinkNode,*LiStack; //链栈
void InitStack(LiStack &S){ //初始化链栈
    S=NULL;
}
bool StackEmpty(LiStack S){ //判断栈是否为空
    return S==NULL;
}
bool Push(LiStack &S,char x){ //新元素入栈
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    if(s==NULL)
        return false; //内存不足创建失败
    s->data=x;
    s->next=S;
    S=s; //将结点s插入链栈，令其为栈顶元素
    return true;
}
bool Pop(LiStack &S, char &x){ //栈顶元素出栈
    if(S==NULL)
        return false; //栈空
    LinkNode *s=S;
    S=s->next;
    x=s->data;
    free(s);
    return true;
}
bool bracketCheck(char str[]){
    int length=strlen(str);
    LiStack 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;
        }
    }
    return StackEmpty(S); //扫描完全部的括号字符串后，若栈为空则匹配成功，否则失败
}
int main(){
    char s[]="([()([])()]{()})";
    if(bracketCheck(s))
        printf("%s","匹配成功");
    else
        printf("%s","匹配失败");
    return 0;
}

3.2 表达式求值

算术表达式由三个部分组成：操作数、运算符、界限符。界限符是必不可少的，也就是括号。括号或者说界限符反映了计算的先后顺序。但是有一个波兰数学家想这样做：可以不用界限符也能无歧义地表达运算顺序。于是发明了：① 逆波兰表达式，即后缀表达式；② 波兰表达式，即前缀表达式。

类型

规则

例1

例2

中缀表达式

运算符在两个操作数中间

a+b

a+b-c

后缀表达式

运算符在两个操作数后面

ab+

ab+c-

前缀表达式

运算符在两个操作数前面

+ab

-+abc

关于中缀、后缀、前缀表达式，我单独写了一篇博文，看这里。

3.3 函数调用栈

函数调用的特点是最后被调用的函数最先执行结束，正是栈的特性——LIFO。调用函数时需要用一个栈存储这些东西：① 调用返回地址；② 实参；③ 局部变量。

3.4 递归工作栈

“递归”算法把原始问题转换为属性相同，但规模较小的问题。如：

（1）计算正整数的阶乘n！，公式如下：

王道视频-数据结构-笔记3：栈和队列_初始化_05


示例代码如下：

#include<stdio.h>
int func(int n){ //计算n的阶乘
    if(n<0)
        return -1; //n不能小于0
    if(n==0||n==1)
        return 1;
    return n*func(n-1);
}
int main(){
    int x;
    scanf("%d",&x);
    printf("%d的阶乘是：%d\n",x,func(x));
    return 0;
}

输入：

6

输出：

6的阶乘是：720

（2）求斐波那契数列，公式如下：

王道视频-数据结构-笔记3：栈和队列_Queue_06


示例代码如下：

#include<stdio.h>
int func(int n){ //计算n的斐波那契数列值
    if(n<0)
        return -1; //n不能小于0
    if(n==0||n==1)
        return n;
    return func(n-1)+func(n-2);
}
int main(){
    int x;
    scanf("%d",&x);
    printf("斐波那契数列是：");
    for(int i=0;i<=x;i++)
        printf("%d ",func(i));
    printf("\n");
    return 0;
}

输入：

10

输出：

斐波那契数列是：0 1 1 2 3 5 8 13 21 34 55

递归包括：① 递归表达式，即递归体；② 边界条件，即递归出口。递归调用时，函数调用栈可称为递归工作栈：每进入一层递归，就将递归调用所需信息压入栈顶；每退出一层递归，就从栈顶弹出相应信息。递归的缺点是效率低，太多层递归可能会导致栈溢出，而且包含很多重复计算。

4 队列的应用

4.1 图的广度优先遍历

在第六章图中会详细学习，请看这里。

4.2 操作系统中的资源分配

多个进程争抢着使用有限的系统资源时，先来先服务（FCFS，First Come First Service）是一种常用策略，可使用队列实现。如：CPU资源的分配、打印机的分配、打印数据缓冲区队列。

END

标签：结点,return,队列,元素,C++,王道,数据结构,rear
From： https://blog.51cto.com/u_14975310/6038977

相关文章

  • 王道视频-数据结构-笔记2：线性表
    文章目录0笔记说明1线性表1.1线性表的定义1.2线性表的基本操作2顺序存储的线性表：顺序表2.1静态分配的顺序表2.2动态分配的顺序表2.3顺序表的特点2.4顺序表的基本操......
  • 【Java 数据结构及算法实战】系列 016：HJ2 计算某字符出现次数
    描述写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字母，然后输出输入字符串中该字母的出现次数。不区分大小写，字符串长度小于500。输入描述：第一行输入一个由字......
  • 【Java数据结构及算法实战】系列007：Java队列01——Queue概述
    队列与栈类似，也是一种运算受限的线性表。队列则被限定在表尾进行插入、在表头进行删除，这种数据结构，实现了FIFO（FirstInFirstOut，先进先出）或者是LILO（LastInLastOut，后进后......
  • php双向队列实例讲解
    双向队列是指一种具有队列和栈的性质的数据结构。双向队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双向队列就像是一个队列，但是你可以在任何一端添......
  • 数据结构与算法Python语言实现-第一章答案
    1.1编写一个Python函数is_multiple(n,m)，用来接收两个整数值n和m，如果n是m的倍数，即存在整数i使得n=mi，那么函数返回True，否则返回Falsedefis_multiple......
  • 数据结构-小球走迷宫问题（递归算法）
    迷宫样式packagecom.recursion;publicclassMaze{publicstaticvoidmain(String[]args){int[][]map=newint[8][7];for(inti=0......
  • [数据结构] 二分查找 (四种写法)
    二分查找二分查找二分查找（BinarySearch）也叫作折半查找，前提是查找的顺序结构是有序的，我们一般在数组上进行二分查找。二分查找就好像猜数字大小游戏一样。假设要数字目......
  • RBMQ案例二：工作队列模式
      工作队列模式工作队列（又名：任务队列）背后的主要思想是避免立即执行资源密集型任务而不得不等待它完成。相反，我们安排任务稍后完成。我们将任务封装为消息并将其发......
  • C/C++数据结构课程设计任务书[2023-02-05]
    C/C++数据结构课程设计任务书[2023-02-05]数据结构课程设计任务书13周一、目的课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结......
  • [数据结构] 哈希表 (开放寻址法+拉链法)
    哈希表哈希表的基本概念哈希表Hashtable是一种提供快速查找和插入元素的数据结构，也称散列表。哈希表是基于数组的扩展，一般利用数组的下标作为哈希表的键值。哈希表存......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99