数据结构-线性表-栈

栈的定义

栈是只允许在一端进行插入和删除操作的线性表
英文：stack
生活中：叠起的碟子、烤肉串
栈也是一种线性表
逻辑结构：和普通的线性表相同
数据的运算：插入、删除操作有区别

栈的几个重要术语
栈顶（允许插入和删除的一端）、
栈底（不允许插入和删除的一端）、
空栈

栈的特点：后进先出
Last In First Out
或称LIFO

栈的基本操作
InitStack(&s) 初始化栈
DestroyStack(&L) 销毁栈
Push(&S,x) 进栈
Pop(&S,&x) 出栈
GetTop(S,&x) 读栈顶元素
StackEmpty(S) 栈的判空

常考题型
进栈顺序：a->b->c->d->e
合法的出栈顺序：
e->d->c->b->a
b->e->c->d->a
n个不同元素进栈，合法的出栈顺序有1/(n+1)*nC(2n)种

顺序栈的缺点：
栈的大小不可以改变
解决方案：用链式存储的方法来实现栈、共享栈

链栈：
用链式存储结构实现的栈
基本操作：创（初始化）、增（进栈）、删（出栈）、
查（获取栈顶元素）、判空、判满
本质上也是一个单链表

栈的顺序存储实现

#include <stdio.h>

//栈的定义
#define MaxSize 10  //定义栈中元素的最大个数
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize]; //利用静态数组存放栈中的元素
    int top;    //栈顶指针
} SqStack;  //顺序栈

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

//判断栈空
bool EmptyStack(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 &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;
}

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

//另一种写法：初始化时栈顶指针的值为0

int main(void){
    //保证编译通过
    return 0;
}

栈的链式存储实现

#include <stdio.h>

typedef int ElemType;

//链栈的定义
typedef struct Linknode {
    ElemType data;  //数据域
    struct Linknode *next;  //指针域
} *LinkStack;   //栈类型定义