栈的基本概念

1. 栈（Stack）是只允许在一端进行插入或删除操作的线性表
2. 栈顶：允许进行插入和删除的一端 （最上面的为栈顶元素）。
3. 栈底：不允许进行插入和删除的一端 （最下面的为栈底元素）。
4. 空栈：不含任何元素的空表。
5. 特点：后进先出（后进栈的元素先出栈）、LIFO（Last In First Out）。
6. 缺点：栈的大小不可变，解决方法：共享栈。

---

栈的基本操作

---

卡特兰数

---

顺序栈的实现

使用数组来实现。其中下标为0的一端作为栈底，将数组尾部作为栈顶，以进行插入和删除
使用一个变量top进行栈顶标识，top之外元素将不属于栈的定义范围

初始化使top=-1时，  空栈的判断条件为：top==-1  【常用】
初始化使top=0时，  空栈的判断条件为：top==0，相应的增删也会有所不同

具体不同看下面实现代码
1
2
3
4

1. 顺序栈的结构体：SqStack

sequence–>顺序的意思–>sq

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

void testStack(){    
    SqStack S;       //声明一个顺序栈(分配空间)
}
1
2
3
4
5
6
7
8
9

2. 顺序栈的初始化 ：InitStack(SqStack &S)

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

3. 入栈和判满 ：Push(SqStack &S, ElemType x)

只有入栈的时候，才会考虑是否满了
先+1后赋值

bool Push(SqStack &S, ElemType x){    
    if(S.top == MaxSize - 1)     // 判断栈是否已满       
        return false;    
    S.data[++S.top] = x;    
    return true;
}
1
2
3
4
5
6

4. 出栈和判空：Pop(SqStack &x, ElemType &x)

只有出栈的时候，才会考虑是否为空
先赋值后-1

bool Pop(SqStack &x, ElemType &x){    
    if(S.top == -1)        // 判断栈是否为空    
        return false;    
    x = S.data[S.top--];    
    return true;
}
1
2
3
4
5
6

5. 读取栈顶元素 ：GetTop(SqStack S, ElemType &x)

和pop( )唯一的不同是：没有-1

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

---

6.【混淆点】另一种实现方法：当初始化top=0时

---

共享栈 （两个栈共享同一片空间）：ShStack

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

// 初始化栈
void InitStack(ShStack &S){    
    S.top0 = -1;      //在外边
    S.top1 = MaxSize;   //在外边
}

//判断是否满
top0 + 1 == top1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

栈的链式存储实现【即链栈】

1. 链栈的结构体【自己定义的】

typedef struct StackNode{        
    ElemType data;        //数据域    
    Linknode *next;       //指针域
}StackNode,*StackLinkList;

void testStack(){   
    StackLinkList L;            //声明一个链栈
}

1
2
3
4
5
6
7
8
9

2. 链栈的初始化 ：InitStack(StackLinkList &L)

bool InitStack(StackLinkList &L){    
    L = (StackNode *)malloc(sizeof(StackNode));   
    if(L == NULL)             
        return false;   
    L->next = NULL;    
    return true;
}
1
2
3
4
5
6
7

3. 判断栈是否为空：isEmpty(StackLinkList &L)

bool isEmpty(StackLinkList &L){    
    if(L->next == NULL)      
        return true;   
    else           
        return false;
}
1
2
3
4
5
6

4. 入栈【就是头插法】：pushStack(StackLinkList &L,ElemType x)

bool pushStack(StackLinkList &L,ElemType x){  
    StackNode *s = (StackNode *)malloc(sizeof(StackNode));  
    if(s == NULL)         
        return false;   
    s->data = x;     
    // 头插法      
    s->next = L->next;  
    L->next = s;     
    return true;
}
1
2
3
4
5
6
7
8
9
10

5. 出栈：popStack(StackLinkList &L, int &x)

bool popStack(StackLinkList &L, int &x){     
    // 栈空不能出栈  
    if(L->next == NULL)     
        return false;    
    StackNode *s = L->next;  
    x = s->data;       
    L->next = s->next;
    free(s);       
    return true;
}
1
2
3
4
5
6
7
8
9
10