栈

栈的概念

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

重要术语

  • 空栈：栈里没有任何数据元素
  • 栈顶：允许插入和删除的一段
  • 栈底：不允许插入和删除的一段
  • 特点：先进后出（LIFO）Last In First Out

栈的基本操作

常考题型

合法的出栈顺序

n个元素进栈，出栈元素的不同排列的个数为$\frac{1}{n+1}C_{2n}^{n}$

顺序栈

顺序栈的定义

1
2
3
4
5
#define MAXSIZE 10
typedef struct {
    int data[MAXSIZE];
    int top;
}SqStack;

顺序栈的初始化

注意：看清楚top是指向栈顶元素还是栈顶元素的后面一个位置

1
2
3
4
void InitStack(SqStack &S){
    S.top=-1;//指向栈顶元素
    //栈满条件top==MAXSIZE-1
}

判断栈空

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

入栈操作

1
2
3
4
5
6
bool Push(SqStack &S,int x){
    if(S.top==MAXSIZE-1)return false;
    S.top++;
    S.data[S.top]=x;
    return true;
}

S.top++ S.data[S.top]=x可以简化为S.data[++S.top]=x

出栈操作

1
2
3
4
5
6
bool Pop(SqStack &S,int &x){
    if(S.top==-1)return false;
    x=S.data[S.top];
    S.top--;
    return true;
}

x=S.data[S.top] S.top--等价于x=S.data[S.top--]

读栈顶元素

1
2
3
4
5
bool GetTop(SqStack &S,int &x){
    if(S.top==-1)return false;
    x=S.data[S.top];
    return true;
}

共享栈

两个栈共享一个空间

1
2
3
4
5
6
7
8
9
10
11
#define MAXSIZE 10
typedef struct{
    int data[MAXSIZE];
    int top0;
    int top1;
}ShStack;
void InitStack(ShStack &S){
    S.top0=-1;
    S.top1=MAXSIZE;
}
//栈满条件top0+1==top1

知识回顾与重要考点

链栈

链栈的定义

1
2
3
4
typedef struct StackNode{
    int data;
    struct Linknode *next;
}StackNode,*LinkStack;

知识回顾与重要考点

链栈的初始化

1
2
3
4
bool InitStack(LinkStack &S){
    S=NULL;
    return true
}

进栈

1
2
3
4
5
6
7
8
bool Push(LinkStack &S,int e){
    StackNode *p=(StackNode*)malloc(sizeof(StackNode));
    if(p==NULL)return false;
    p->data=e;
    p->next=S;
    S=p;
    return true;
}

出栈

1
2
3
4
5
6
7
8
bool Pop(LinkStack &S,int &e){
    if(S==NULL)return false;
    StackNode *p=S;
    S=S->next;
    e=p->data;
    free(p);
    return true;
}

查

1
2
3
int GetTop(LinkStack S){
    return S->data;
}