文章目录

🚀一、栈的原理精讲
🚀二、栈的算法实现
- ⛳栈的顺序存储结构
- - 🎉（一）顺序栈
  - - 1.栈的结构体定义
    - 2.栈的初始化
    - 3.判断空栈
    - 4.判断栈满
    - 5.元素入栈
    - 6.元素出栈
    - 7.获取栈顶元素
  - 🎉（二）共享栈
  - - 1.共享栈的结构体定义
    - 2.共享栈进栈
    - 3.共享栈出栈
- ⛳栈的链式存储结构
- - 🎉链栈
  - - 1.链栈的结构体定义
    - 2.链栈的初始化
    - 3.链栈的入栈
    - 4.链栈的出栈
    - 5.取栈顶元素、遍历链栈

🚀一、栈的原理精讲

拿一个故事引入一下：

我拼搏了几年后，终于有点小钱能买一辆车了，但是，我家住在巷子里，在一个胡同的尽头，而且整个胡同非常窄，只能容纳一辆车通过，而且是死胡同，我每天都要为停车发愁。当我回家早，把车停在胡同里面，早上上班一起来，我勒个去，我的车在胡同最里面，这到胡同口，一辆辆的车哇，我还要一辆一辆打电话，让胡同口那辆车出去，然后挨着一辆一辆出去，才能开到我的车。每天上班我都迟到，所以之后我干脆下班后再加班，晚点回来，等天黑了，别的车都停进去了再回家，再回去把车停在胡同口，这样早上就可以第一个去上班了。

在这里插入图片描述

胡同里的小汽车是排成一条直线，是线性排列，而且只能从一端进出，后进的汽车先出去，后进先出（Last In First Out，简称LIFO），这就是"栈"。栈也是一种线性表，只不过它是操作受限的线性表，只能在一端操作

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储。

栈的核心要素：

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Base）：固定的，不允许进行插入和删除的另一端。

🚀二、栈的算法实现

⛳栈的顺序存储结构

🎉（一）顺序栈

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素。其中，base 指向栈底，top 指向栈顶。

（本篇采用的方法，top指向的是下一个要插入的位置，即栈顶元素的下一个位置，而不是栈顶元素，在有些地方可以看见，top指向的就是栈顶的元素）

注意：栈只能在一端操作，后进先出，这是栈的关键特征，也就是说不允许在中间查找、取值、插入、删除等操作，我们掌握好顺序栈的初始化、入栈，出栈，取栈顶元素等操作即可。

在这里插入图片描述

1.栈的结构体定义

#define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定

typedef int ElemType;

typedef struct _SqStack{
    ElemType *base; //栈底指针
    ElemType *top; //栈顶指针
}SqStack;

解释：

栈底指针同时也就是我们分配空间的基地址
也可改为ElemType base[MAXSIZE]，但为了理解上方便，最好用指针分配空间
栈顶指针同样也不用设置为指针，因为是数组，定义为普通整形表示下标位置也可

2.栈的初始化

bool InitStack(SqStack &S) { //构造一个空栈 S
    S.base = new int[MaxSize];//为顺序栈分配一个最大容量为 Maxsize 的空间

    if (!S.base) return false; //空间分配失败

    S.top=S.base; //top 初始为 base，空栈

    return true;
}

//采用top指向栈顶元素的方法
bool StackEmpty(SqStack S){
    S->top = -1;    //初始化栈顶指针
}

在这里插入图片描述

解释：

当采用top指向栈顶元素的方法时，并且以ElemType base[MAXSIZE]方式分配空间，初始化操作直接将top = -1即可

3.判断空栈

bool IsEmpty(SqStack &S){ //判断栈是否为空
    if (S.top == S.base){
    	return true;
    } else {
    	return false;
    }
}

//采用top指向栈顶元素的方法
bool StackEmpty(SqStack S){
    if(S.top == -1){    
        return true;    //栈空
    }else{  
        return false;   //不空
    }
}

解释：

采用top指向栈顶元素的方法时，当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。

4.判断栈满

//本篇方法
S.top-S.base == MaxSize；
    
//采用top指向栈顶元素的方法
S->top == MAXSIZE-1

在这里插入图片描述

解释：

指针的减法表示中间相隔多少个元素，基础知识不多讲

5.元素入栈

bool PushStack(SqStack &S, int e) { // 插入元素 e 为新的栈顶元素
    if (S.top-S.base == MaxSize) //栈满
    	return false;
    
    *(S.top++) = e; //元素 e 压入栈顶，然后栈顶指针加 1，等价于*S.top=e;S.top++;
    return true;
}

//采用top指向栈顶元素的方法
/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, ElemType e){
    //满栈
    if(S->top == MAXSIZE-1){
        return ERROR;
    }
    S->top++;   //栈顶指针增加一
    S->data[S->top] = e;    //将新插入元素赋值给栈顶空间
    return OK;
}

在这里插入图片描述

6.元素出栈

bool PopStack(SqStack &S, ElemType &e) //删除 S 的栈顶元素，暂存在变量 e中
{
    if (S.base == S.top){ //栈空
    	return false;
    }
    
    e = *(--S.top); //栈顶指针减 1，将栈顶元素赋给 e
    
    return true;
}

//采用top指向栈顶元素的方法
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqStack *S, ElemType *e){
    if(S->top == -1){  //栈空
        return ERROR;
    }
    *e = S->data[S->top];   //将要删除的栈顶元素赋值给e
    S->top--;   //栈顶指针减一
    return OK;
}

在这里插入图片描述

解释：

出栈操作: 和入栈相反，出栈前要判断是否栈空，如果栈是空的，则出栈失败，否则将栈顶元素暂存给一个变量，栈顶指针向下移动一个空间（top–）。

7.获取栈顶元素

ElemType GetTop(SqStack &S) { //返回 S 的栈顶元素，栈顶指针不变	
    if (S.top != S.base){ //栈非空
    	return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
    } else {
    	return -1;
    }
}

//采用top指向栈顶元素的方法
/*读栈顶元素*/
Status GetTop(SqStack S, ElemType *e){
    if(S->top == -1){   //栈空
        return ERROR;
    }
    *e = S->data[S->top];   //记录栈顶元素
    return OK;
}

🎉（二）共享栈

利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：（共享栈我们就以第二种方式再来讲解一下）

两个栈的栈顶指针都指向下一个可插入位置，S1.top=S1.base时1号栈为空，S2.top == S2.base == MaxSize时2号栈为空；仅当两个栈顶指针相同（S1.top = S2.top）时，此时能最后插入一个元素。当1号栈进栈时S1.top先赋值再加一，2号栈进栈时S2.top先赋值再减一出栈时则刚好相反。

在这里插入图片描述

两个栈的栈顶指针都指向栈顶元素，S1.top=-1时1号栈为空，S2.top=MaxSize时2号栈为空；仅当两个栈顶指针相邻（S1.top+1=S2.top）时，判断为栈满。当1号栈进栈时S1.top先加1再赋值，2号栈进栈时S2.top先减一再赋值出栈时则刚好相反。

在这里插入图片描述

1.共享栈的结构体定义

/*两栈共享空间结构*/
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
/*两栈共享空间结构*/
typedef struct{
	ElemType data[MAXSIZE];
	int top0;	//栈0栈顶指针
	int top1;	//栈1栈顶指针
}SqDoubleStack;

解释：

像之前一样，ElemType data[MAXSIZE];可用指针表示
栈0栈顶指针和栈1栈顶指针同样也能用指针表示
栈1的栈底指针就不需要了，其实就是MAXSIZE - 1

2.共享栈进栈

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){
    if(S->top0+1 == S->top1){   //栈满
        return ERROR;
    }
    if(stackNumber == 0){   //栈0有元素进栈
        S->data[++S->top0] = e; //若栈0则先top0+1后给数组元素赋值
    }else if(satckNumber == 1){ //栈1有元素进栈
        S->data[--S->top1] = e; //若栈1则先top1-1后给数组元素赋值
    }
    return OK;
}

解释：

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈0还是栈1的栈号参数stackNumber。

3.共享栈出栈

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){
    if(stackNumber == 0){
        if(S->top0 == -1){
            return ERROR;   //说明栈0已经是空栈，溢出
        }
        *e = S->data[S->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针减1
    }else if(stackNumber == 1){
        if(S->top1 == MAXSIZE){
            return ERROR;   //说明栈1是空栈，溢出
        }
        *e = S->data[S->top1++];    //将栈1的栈顶元素出栈，随后栈顶指针加1
    }
    return OK;
}

⛳栈的链式存储结构

🎉链栈

栈的链式存储结构就是链栈，栈底就是链表的最后一个结点，而栈顶是链表的第一个结点，一个链栈可以由栈顶指针top唯一确定。链栈的元素入栈就类似于链表的头插法

链式存储结构可以更好的避免栈上溢，因为顺序栈在定义结构体时需要定义最大值。
便于多个栈共享存储空间和提高其效率
通常采用单链表实现，并规定所有操作都是在单链表的表头进行的
这里规定链栈没有头节点，Lhead指向栈顶元素，
对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

在这里插入图片描述

1.链栈的结构体定义

//1.定义数据类型
typedef int ElemType;
//2.定义链栈结构体
typedef struct LinkStackNode
{
    ElemType data;//存数据
    struct LinkStackNode *next;//存下个节点的地址
} LinkStack;

解释：

也可以为链栈增加要素，例如增添一个count表示元素数量，但这样就不能跟结点共享一个结构体，需要单独定义：

/*栈的链式存储结构*/
/*构造节点*/
typedef struct LinkStackNode{
    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{
    LinkStackPrt top;
    int count;
}LinkStack;

//这样定义就不需要什么初始化操作了，最多初始化count = 0

2.链栈的初始化

//3.初始化链栈
int initLinkStack(LinkStack *L)
{
    L = (LinkStack *) malloc(sizeof(LinkStack));//申请内存
    if(!L->data) return 0;//申请失败
    L->data = 0;//初始化链栈头结点数据域
    L->next = NULL;//初始化链栈头结点指针域
    return 1;
}

3.链栈的入栈

//4.入栈
int push(LinkStack *L, ElemType e)
{
    LinkStack *n;//新节点
    n = (LinkStack *) malloc(sizeof(LinkStack));
    if(!n->data) return 0;
    
    n->data = e;//存入数据
    n->next = L->next;//链栈栈顶元素链入新节点，新节点变成栈顶
    L->next = n;//新节点链入链栈头结点末尾
    return 1;
}

4.链栈的出栈

//5.出栈
int pop(LinkStack *L, ElemType *e)
{
    if(!L->next) return 0;//栈空，返回0
    
    LinkStack *d = L->next;//出栈指针指向栈顶
    *e = d->data;//赋值
    L->next = d->next;//头结点跳过出栈节点，链入出栈节点的下一节点
    free(d);//释放内存
    return 1;
}

5.取栈顶元素、遍历链栈

//取栈顶
int getTop(LinkStack *L, ElemType *e)
{
    if(!L->next) return 0;
    *e = L->next->data;
    return 1;
}

//遍历链栈
void printStack(LinkStack *L)
{
    LinkStack *p = L;//遍历指针
    while (p)
    {
        p = p->next;
        printf("%d ", p->data);
    }
    printf("\n");
}