数据结构——栈

1、栈的定义

​ 栈就是只能在一端插入和删除数据的链表，这个端就叫做栈顶（top），最后一个添加的数据第一个被删除。因此，这也叫后进先出（LAST IN FIRST OUT）链表或是先进后出链表（FIRST IN LAST OUT）。

栈储存的图像表示：

（图片来自百度：

https://baike.baidu.com/pic/%E6%A0%88/12808149/0/06493638860a850cb8998fc0?fr=lemma&ct=single#aid=0&pic=06493638860a850cb8998fc0

）

2、栈的基本操作

对于栈有两种操作：

• 进栈指令（PUSH）：在栈中现有元素顶部添加一个元素，新加入的元素变为最顶端的元素。
• 出栈指令（POP）：取出栈顶元素，删除栈中的这个元素。

3、栈的基础经典算法

1．进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；

②置TOP=TOP+1（栈指针加1，指向进栈地址）；

③S(TOP)=X，结束（X为新进栈的元素）；

2．退栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；

②X=S(TOP)，（退栈后的元素赋给X）：

③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

顺序栈的储存实现

#include <iostream>
#define MAXSIZE 100        //定义最大空间
#define ElemType int        //定义数据类型
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;

typedef struct SNode *Stack;
struct SNode{
    ElemType Data[MAXSIZE];        //定义栈的空间
    int top;    //指示栈顶的位置 
};           

顺序栈的入栈实现

void Push(Stack Ptrs, ElemType item){
    if(Ptrs->top == MAXSIZE-1)        //栈满
        cout << "Data overflow";
    else{
        Ptrs->Data[++(Ptrs->top)] = item;        //先使top上移一位，再赋值
        
        //也可以写成
        //Ptrs->top++;
        //Ptrs->Data[Ptrs->top] = item;
    }
}           

顺序栈的出栈实现

ElemType Pop(Stack Ptrs){
    if(Ptrs->top == -1){        //栈空
        cout << "No data";
        return ERROR;
    }
    else{
        return (Ptrs->Data[Ptrs->top--]);        //先抛出top的值，再使top-1
    }
}           

4、共享栈——一个数组存放两个栈

​ 这是一种合理使用空间的方法，使数组空间不被浪费太多

共享栈的定义：

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

其图示为：

（图片来自网络，侵删）

共享栈的储存实现

#include <iostream>
#define MAXSIZE 100        //定义最大空间
#define ElemType int        //定义数据类型
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;
typedef struct DoubleStack DS
struct DoubleStack{
    ElemType Data[MAXSIZE];
    int top1;        //定义第一个栈的头位置
    int top2;        //定义第二个栈的头位置
};

DS->top1 = -1;
DS->top2 = MAXSIZE;            

共享栈的入栈实现

void Push(DS Ptrs, ElemType item, int flag){
    //flag用于区分栈1和栈2
    if(Ptrs->top1 - Ptrs->top2 == 1)        //栈满
        cout << "Data overflow"; 
    if(flag == 1)        //向栈1输入
        Ptrs->Data[++(Ptrs->top1)] = item;
    else if(flag == 2)        //向栈2输入
        Ptrs->Data[--(Ptrs->top2)] = item;
}
           

共享栈的出栈实现

ElemType Pop(DS Ptrs, int flag){
    if(flag == 1){        //判断为栈1
        if(Ptrs->top1 == -1){        //栈空
            cout << "No data";
            return nullptr;
        }
        else
            return Ptrs->Data[(Ptrs->top1)--];
    }
    else if(flag == 2){        //判断为栈2
        if(Ptrs->top2 == MAXSIZE){        //栈空
            cout << "No data";
            return nullptr;
        }
        else
            return Ptrs->Data[(Ptrs->top1)++];
    }
}           

5、链式栈

链式栈不需要预先分配容量，也无需增加容量，但是需要链表的首位作为top（栈的顶端元素）

链式栈的储存实现

#include <iostream>
#define MAXSIZE 100        //定义最大空间
#define ElemType int        //定义数据类型
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;

typedef struct LinkStack *LS;
struct LinkStack{
    ElemType Data;        
    LinkStack *Next;
};           

创建一个空的链式栈

LS CreateStack(){
    LS s;
    s = new(LinkStack);        //申请空间
    s->Next = nullptr;
    return s;
}           

链式栈的入栈实现

void Push(ElemType X, LS s){
    LS ssr = s;
    ssr = new(LinkStack);
    ssr->Data = X;        //插入值X
    ssr->Next = s->Next;        //插入
    s->Next = ssr; 
}           

链式栈的出栈实现

ElemType Pop(LS s){
    LS FirstCell;
    ElemType Top;
    if(s->Next == nullptr)        //判断是否为空栈
        cout << "No data";
    else{
        FirstCell = s->Next;
        s->Next = FirstCell->Next;
        Top = FirstCell->Data;;
        delete FirstCell;        //释放空间，防止内存泄漏
        return Top;
    }
}           

6、栈的简单应用

中缀表达式

基本策略：

​ 将中缀表达式转化成后缀表达式，然后求值

将中缀表达式转化成后缀表达式的方法：