数据结构-第二章：栈和队列

发表于 2023-06-30 更新于 2023-07-09 分类于数据结构

栈和队列。

栈

栈的基本概念

栈的定义

栈是只允许在一端进行插入或删除操作的线性表。

重要术语：栈顶、栈底、空栈

特点：后进先出（LIFO）

栈的基本操作

创、销
- InitStack(&S)：初始化栈。构造空栈S，分配内存空间。
- DestroyStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间。
增、删
- Push(&S,x)：进栈，若栈S未满，将x加入使之称为新栈顶。
- Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并将x返回。
查
- GetTop(S,&x)：读栈顶元素。若栈S非空，则用x返回栈顶元素。
其它操作
- StackEmpty(S):判断栈S是否为空。若空返回true，否则返回false。

常考题型

进栈顺序：a→b→c→d→e
有哪些合法的出栈顺序？

栈的顺序存储实现

顺序栈的定义

#define MaxSize 10              //定义栈中元素最大个数
typeof struct{                   
    ElemType data[MaxSize];     //静态数组存放栈中元素
    int top;                    //栈顶指针
}SqStack;

void testStack(){
    SqStack S;                  //声明一个顺序栈（分配空间）
    //...后续操作...
}

初始化操作

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

//判断栈空
bool StackEmpty(SqStack S){
    if(S.top==-1)
        return true;
    else
        return false;           //初始化栈顶指针
}

void testStack(){
    SqStack S;                  //声明一个顺序栈（分配空间）
    InitStack(S);
    //...后续操作...
}

进栈与出栈

进栈：将数据存入栈顶
出栈：将栈顶元素删除并存入一个变量中

//入栈
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 &S,ElemType &x){
    if(S.top==-1)               //栈空，报错
        return false;
    //x=S.data[S.top]           //栈顶元素先出栈
    //S.top=S.top-1             //指针再减1
    x=S.data[S.top--];          //等价于上两行写法
    return true;
}

出栈操作并没有在内存中删除元素，只是逻辑上移出了栈。

读取栈顶元素

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

另一种实现方式

令top指针初始化时指向0的位置，即top指针表示下一次插入元素的位置。

则初始化操作改为：

1
2
3

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

进栈操作改为：

bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize)          //栈满，报错
        return false;
    S.data[S.top++]=x;
    return true;
}

出栈操作改为：

bool Pop(SqStack &S,ElemType &x){
    if(S.top==0)                //栈空，报错
        return false;
    x=S.data[--S.top];
    return true;
}

共享栈

顺序栈的大小不可改变，要解决这个问题可以使用链式存储的方式实现。也可以在初始分配时开辟一片比较大的空间，但这样很容易造成浪费，因此提出了共享栈的概念。

共享栈是两个栈共享同一片空间。

定义共享栈为：

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

初始化操作为：

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

栈满的条件为：top0+1==top1

栈的链式存储实现

链式存储的栈称为链栈。
其本质上也是一个链表，只是只能操作头结点。
可以分为带头结点和不带头结点两种。（推荐不带头结点）

//定义
typedef struct Linknode{
    ElemType data;
    struct Linknode *next;
}*LiStack;

其余操作自己复现。

队列

队列的基本概念

队列的定义

只允许在一端进行插入（入队），在另一端删除的线性表（出队）。

重要术语：队头、队尾、空队列

特点：先进先出，后进后出（FIFO）。

队列的基本操作

队列的顺序实现

初始化与定义

队列包含队头指针和队尾指针，队头指针指向队头元素，队尾指针指向下一个应该插入的位置。

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];     //静态数组存放队列元素
    int front,rear;             //队头指针和队尾指针
}SqQueue;

//初始化
void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;           //队头队尾指针均指向0
}

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
    return Q.rear==Q.front;
}

void testQueue(){
    SqQueue Q;                  //声明队列
    //...后续操作
}

入队

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;  //①
    return true;
}

①通过取余操作令队列将存储空间在逻辑上变为环状（循环队列）。

同时，由于队头指针等于队尾指针已经是队列为空的充分条件，因此为了实现判断队列为满的操作，我们需要牺牲一个存储空间，从而将其充分条件变为队尾指针的下一位为队头指针，如②。

出队

删除队头元素，并用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;
}

查找

返回队头元素

bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear==Q.front){    //队空则报错
        return false;
    }
    x=Q.data[Q.front];
    return true;
}

获取队列元素个数

1
2
3

int GetSize(SqQueue Q){
    return (Q.rear+MaxSize-Q.front)&MaxSize;
}

空间利用：方案一

加入size记录元素数量。

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];     //静态数组存放队列元素
    int front,rear;             //队头指针和队尾指针
    int size;                    //当前队列元素个数
}SqQueue;

空间利用：方案二

加入tag标签，每次删除成功时令tag=0，插入成功时令tag=1。结合tag判断是空是满。

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];     //静态数组存放队列元素
    int front,rear;             //队头指针和队尾指针
    int tag;                    //最近进行的是插入还是删除。
}SqQueue;

其它方案

也可以令队尾指针指向最后一个元素。区别在于:

插入时先后移再插入元素
初始化时令队尾指针指向数组最后一个元素
判空:(Q.rear+1)%MaxSize==Q.front
判满：两种方式，同理

队列的链式实现

链式队列其实就是链表的阉割版，许多操作与链表大同小异。

链式队列定义

#define MaxSize 10
typedef struct LinkNode{
    ElemType data;  
    struct LinkNode *next;
}LinkNode;

typedef strcut{
    LinkNode *front,*rear;
}LinkQueue;

初始化

带头结点

//初始化
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
} 

//判空
bool IsEmpty(LinkQueue Q){
    return Q.front==Q.rear;
    //return Q.front->next==NULL;
}

不带头结点

//初始化
void InitQueue(LinkQueue &Q){
    Q.front=NULL;
    Q.rear=NULL;
} 

//判空
bool IsEmpty(LinkQueue Q){
    return Q.front==NULL;
    //return Q.rear==NULL;
}

注：队头指针始终指向头结点

void testLinkQueue(){
    LinkQueue Q;
    InitQueue(Q);
    //...后续操作
}

入队

先申请一个新结点，并将元素放入新结点中
令新结点next指针设为NULL
令当前rear指向节点的next指向新结点
更新表尾指针

不带头结点的类似。

用代码实现为：

//带头结点
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;                   //修改表尾指针
}

//不带头结点
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指针
然后释放该结点

不带头结点的类似。

代码实现为：

//带头结点
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;       //修改头结点的next指针
    if(Q.rear==p)               
        Q.rear=Q.front;         //如果是最后一个结点出队，修改rear指针
    free(p);
    return true;
}

//不带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==NULL)
        return false;           //空队
    LinkNode *p=Q.front；
    x=p->data;
    Q.front=p->next;
    if(Q.rear==p){              //如果是最后一个结点出队
        Q.front=NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;
}

双端队列

双端队列是允许从两端插入、两端删除的线性表。

双端队列的单独一端其实就是栈，所以栈能实现的功能双端队列均可实现。

双端队列还可以分为：

输入受限的双端队列：只允许一端插入、两端删除的线性表
输出受限的双端队列：只允许一端删除、两端插入的线性表

常考题型

对输出序列合法性的判断。不做阐述，见题即可。

栈与队列的应用

栈的应用——括号匹配

问题介绍

判断表达式的括号是否正确。

问题分析

可以发现，最后出现的左括号最先被匹配（LIFO）。因此可用栈来实现该特性。

扫描到左括号就压栈，扫描到右括号就出栈。如果出现以下情况，就说明表达式有误：

扫描到右括号后发现与栈顶不匹配
扫描到右括号时栈空
扫描完成后栈不为空

流程图为：

代码

假设使用顺序栈。

#define MaxSize 10              //定义栈中元素最大个数
typeof struct{                   
    ElemType data[MaxSize];     //静态数组存放栈中元素
    int top;                    //栈顶指针
}SqStack;

bool bracketCheck(char str[], int length){
    SqStack S;
    InitStack(S);
    for(int i=0;i<length;i++){
        if(str[i]=='('||str[i]=='['||str[i]=='{'){
            S.push(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);
}