2019王道《数据结构》(C语言版)——栈和队列

清疚 2024-04-18 23:51 9阅读 0赞

## 2019王道《数据结构》——栈和队列 ##

## 重点 ##

栈（出入栈的过程、出栈序列的合法性）和队列的操作及其特征是重中之重。均是线性表的应用和推广

## 一、栈的基本操作 ##

提示：如果看不懂，可以结合下面的代码来看

InitStack(&S): 初始化一个栈

StackEmpty(S): 判断一个栈是否为空，若栈S为空返回True，否则返回false

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

Pop(&S,&x): 弹出栈，返回x

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

ClearStack(&S): 销毁栈， 并释放S占用的存储空间

符号“&”是C++所特有的，表示引用（别名），在c语言中可以用*代替

## 二、栈的顺序存储结构 ##

#### 1）顺序栈的实现 ####

栈的顺序存储

//栈的顺序存储结构
    #define MaxSize 50 //定义栈的存储量
    typedef int ElemType;     //定义栈里面存储的元素的数据类型
    typedef struct{     //定义栈
        ElemType data[MaxSize];   //定义一个data数组用来存“栈里面的各个元素结点的数据”
        int top;      //栈顶指针
    }SqStack;

**说明：S代表栈**

进栈指针：S.top（初始时设置S.top=-1;栈顶元素:S.data\[S.top\]）

进栈操作：栈不满时，栈顶指针先加1（**解释：这就是为什么初始时栈顶指针S.top=-1,因为我们第一次向栈里面加元素的时候，把S.top++，这个时候S.top就等于0了，正好我们的数组位置是从0开始的**），再送值到栈顶元素。

出栈操作： 栈非空时，先取栈顶元素值，再将栈顶指针减1

栈空条件：S.top = -1; 栈满条件：S.top==MaxSize-1; 栈长：S.top+1（**数组位置是从0开始的**）;

由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢。

#### 2） 顺序栈的基本运算 ####

#include <cstdlib>
    #include <cstdio>
     
    using namespace std;
     
    //栈的顺序存储结构
    #define MaxSize 50 //定义栈的存储容量
    typedef int ElemType;       //定义栈中存储的元素的数据类型
    typedef struct{      //定义栈
        ElemType data[MaxSize];   //存放一个data数组用来存储栈中元素
        int top;      //栈顶指针
    }SqStack;
     
    void InitStack(SqStack &S) {    
        S.top = -1;
    }
     
    bool StackEmpty(SqStack S) { 
        return S.top == -1;  //如果S.top == -1，就返回true,否则返回false
    }
     
    bool Push(SqStack &S, ElemType x) { 
        if (S.top == MaxSize - 1) //如果栈已经满了，就返回false
            return false;
        S.data[++S.top] = x;  //先把S.top指针加1，然后再将x加入使之成为新栈顶
        return true;
    }
     //弹出栈顶的第一个元素
    bool Pop(SqStack &S, ElemType &x) { 
        if (!(StackEmpty(S))) {  //如果栈不空
            x = S.data[S.top--]; //先把栈顶元素弹出去，然后再把S.top指针减1
            return true;
        }
        return false; //如果栈为空，则直接返回false
    }
     //得到栈顶第一个元素的值，但是并不将栈顶元素弹出去
    bool Gertop(SqStack S, ElemType &x) { 
        if (S.top == -1) //如果S.top==-1，说明栈已经空了
            return false;
        x = S.data[S.top]; //得到栈顶元素
        return true;
    }
     
    bool ClearStack(SqStack &S) {  //清空栈
        if (S.top == -1) //如果S.top==-1，说明栈已经空了
            return false;
        
        S.top = -1;   //直接将S.top栈顶指针的值赋值为-1，意思就是“清空栈”
        return true;
    }
     
    void prinStack(SqStack S) {   //打印栈里面的元素值
        
        ElemType x; 
        
        while (!StackEmpty(S)) { //如果栈不为空，则执行while循环
            Pop(S, x);   //弹出栈顶元素
            printf("%d ", x);  //这里的x已经Pop(S, x)里面赋值了
        }
    }
     
    int main() { 
     
        int i = 10;
        SqStack s;  //定义一个栈S
        InitStack(s); //初始化栈
        while (i--) {   
            ElemType e;
            scanf("%d", &e);
            Push(s, e); //往栈里面存数据
        }
     
        prinStack(s); //打印栈里面的数据
     
        return 0;
    }

#### 3）共享栈 ####

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，**两个栈顶向共享空间的中间延伸**。

## 三、栈的链式存储结构 ##

不存在栈满上溢的情况，通常用单链表实现，**规定所有的操作都是在单链表的表头进行的**

//栈的链式存储结构,头插法
    typedef struct Linknode{ 
        ElemType data;
        struct Linknode *next;   //指针域,这个指针指向该节点的下一个节点
    }*LinkStack;    //栈里面的节点类型定义

#### 试题精选 ####

1）基本操作是指该结构最核心、最基本的运算，其他较复杂的操作可以通过基本操作来实现。

2）栈和队列都是限制存取点的线性结构

3）对于n个不同元素出栈，出栈序列的个数为： （提示：下面有该公式的举例讲解，不要直观地以为是全排列，其实不是！！！）

![img][]

此公式为**卡特兰数，** 排列组合公式

![formula][]

![formula][formula 1]

**讲解**：我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出：

f(1) = 1 //即 1

f(2) = 2 //即 12、21

f(3) = 5 //即 123、132、213、321、231

123： 1入栈，再出栈，然后2入栈，再出栈，然后3入栈，再出栈

132： 1入栈，再出栈，然后2，3顺序入栈，3出栈，2出栈

…

对于f(3)里面为什么没有312，原因很简单，如果是312的出栈顺序的话，那就是说3第一个出来，但是因为1和2是顺序进去的，所以出来应该是2，1

4）设单链表的表头指针为h，节点结构由data和next两个域组成，其中data域为字符型，试设计算法判断该链表前n个字符是否中心对称

bool dc( LinkedList L, int n) {   
     
        if (n <= 1)        //n的值不合法，n必须大于会等于2才考虑对称性
            return false;
     
        LNode *p = L->next; //把链表的头指针赋给p
        char arr[MaxSize];       //字符数组，用于存储栈里面的元素数据
        int top = -1;           //初始时，让top指针指向-1位置
        while (p != NULL && top < (n / 2 - 1)) {   //如果p不为空，且top指针没有超过该单链表的一半长度
            arr[++top] = p->data;//先把top指针的位置加1，然后把p指针指向的节点数据加到arr数组里面去
            p = p->next; //把p指针的下一个节点赋给p，就相当于把p指针往后面移动
        }
    if (p == NULL)    //链表总长度<=n/2,不满足条件（因为上面的n是dc( LinkedList L, int n)的形参，是我们自己随意指定的，有可能我们指定的n值太大了，然后才出现这种情况）
            return false;
     
        if (n & 1)           //n为奇数，比如3=11，则11&01=true，再比如5=101,则101&001=true
            p = p->next;    //因为经过上面的while循环操作以后，p已经指向了(n+1)/2位置的节点，因为这里的n是奇数，所以我们判断对称的话需要忽略中间节点，所以我们让 p = p->next;指向下一个节点，从而直接跳过中间位置的节点
        while (p != NULL && top > -1) { 
            if (p->data != arr[top--]) //这个时候p已经指向到(n+1)/2+1位置的节点了，然后把该位置节点的数据与arr栈顶的数据做对比，看是否相等
                return false;
            p = p->next;
        }
     
        if (top > -1)     //栈未被清空，说明字符总数不到n个，比如我们的字符总数为7，n为10，那上面的程序就是判断字符序列的前5个与后5个是否对应相等。但是显然我们的字符总数才7个，所以应该是前半部分是5个，后半部分是2个，所以才会出现这里的top>-1的情况
            return false;
        else
            return true;
        
    }
    
        if (top > -1)     //栈未被清空，说明字符总数不到n个，比如我们的字符总数为7，n为10，那上面的程序就是判断字符序列的前5个与后5个是否对应相等。但是显然我们的字符总数才7个，所以应该是前半部分是5个，后半部分是2个，所以才会出现这里的top>-1的情况
            return false;
        else
            return true;
        
    }

[img]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvOTg0MzMzLzIwMTcwMy85ODQzMzMtMjAxNzAzMTQyMDIzNTM2MDQtNjA2MzU2NDMxLnBuZw?x-oss-process=image/format,png
[formula]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zczEuYmFpZHUuY29tLzZPTlhzamlwMFFJWjh0eWhucS9pdC91PTE0ODg4ODU2MjgsMjA5OTc1MTE3NyZmbT01OA?x-oss-process=image/format,png
[formula 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zczEuYmFpZHUuY29tLzZPTlhzamlwMFFJWjh0eWhucS9pdC91PTI3MTgzMDE2MTgsNTIxMjQ0JmZtPTU4?x-oss-process=image/format,png