3.1 栈

3.1.1 栈的基本概念

栈是只允许在一端进行插入或删除的数据表

栈.png

• 栈顶：允许插入和删除的一端
• 栈底：不允许插入和删除的一端

特点：后进先出(LIFO)
n个不同的元素进栈，出栈元素不同排列个数为

上述公式称为卡特兰数

3.1.2 栈的基本操作

InitStack(&s)初始化栈，构建一个空栈，分配存储空间
DestoryStack(&s)销毁栈，销毁并释放s所占用内存空间
Push(&s,x)进栈，若栈未满，将x加入栈中，使其称为栈顶
Pop(&s,x)出栈，若栈非空，弹出栈顶元素，用x返回
GetTop(s,&x)读取栈顶元素，若栈非空，用x返回栈顶元素
StackEmpty(s)判断是否为空栈

进栈和出栈可能同时进行

3.2 顺序栈

3.2.1 顺序栈的定义

顺序栈：使用顺序存储方式实现的栈，利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时使用一个指针指示当前栈顶元素值
定义代码如下：

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int top; //栈顶指针
}SqStack;

3.2.2 顺序栈的初始化

在初始化时，只需要将栈顶指针设置为-1，表示栈内不存在元素，也可以直接通过top判断是否为空栈

//初始化栈
void InitStack(SqStack &s){
    s.top = -1;
}

// 判断栈是否为空
bool StackEmpty(SqStack &s){
    if(s.top==-1) return true;
    else return false;
}

3.2.3 进栈操作

bool Push(SqStack &s,ElemTyppe x){
    if(s.top==MaxSize-1) return false;
    s.top = s.top+1;
    s.data[s.top]=x;
    return true;
}

3.2.4 出栈操作

bool Pop(SqStack &s,ElemTyppe x){
    if(s.top==-1) return false;
    x = s.data[s.top];
    s.top = s.top-1;
    return true
}

3.2.5 读取栈顶元素

bool GetTop(SqStack s,ElemTyppe &x){
    if(s.top==-1) return false;
    x = s.data[s.top];
    return true;
}

3.3 链栈

使用链式存储的栈称为链栈，相当于一个只从头结点进行插入删除操作的单链表，但链栈没有头结点，Lhead指向栈顶元素
创建链栈的代码如下

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}*ListStrack;

3.4 队列(Queue)

3.4.1 队列的定义

队列是一种操作受限的线性表
队列只允许在一段删除，在另一端插入

队列.png

特点：先进先出(FIFO)

3.4.2 队列的基本操作

InitQueue(&Q)初始化队列
DestortQueue(&Q)销毁队列
EnQueue(&Q,x)入队，若队列不是满队列，将x加入栈中，称为队尾
DeQueue(&Q,&x)出队，若队列非空，弹出队头元素并用x返回
GetHead(Q,&x)读取队头元素，若非空，队头元素赋值给x
QueueEmpty(Q)队列判空

3.5 队列的顺序存储

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front, rear; //队头队尾指针
}SqQueue;

3.5.1 队列的初始化

// 初始化
void InitQueue(SqQueue &Q){Q.rear = Q.front;}

// 判空
void QueueEmpty(SqQueue Q){
    if (Q.rear == Q.front)return true;
    else return false;
}

3.5.2 入队

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1) % MaxSize == Q.front) return false; //队满
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear+1)% MaxSize;
    return true;
}

在顺序存储中需要对队尾指针进行取余处理，目的是可以调用队头空出的位置，通过这种方式，将原本的线性存储空间变成了一个可重复使用的环，因此也称循环队列

3.5.3 出队

bool DeQueue(SqQueue &Q, ElemType &x){
     if (Q.rear == Q.front) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front +1)%Maxsize;
    return true;
}

3.6 双端队列

双端队列是只允许两端插入两端删除的线性表
特殊可分为输入受限，输出受限等等

双端队列.png

3.7 栈的应用

括号匹配问题

bool BrackeCheak(char str[], int length){
    SqStack S;
    InitStack S;
    for(int i=0; i<length; i++){
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') ) Push(S, str[i]
        else {
            if(StackEmpty(S)) return false;
            char topElem;
            Pop(S.topElem);
            if (str[i] == '(' && topElem!=')') return false;
            if (str[i] == '[' && topElem!=']') return false;
            if (str[i] == '{' && topElem!='}') return false;
        }
    }
    return StackEmpty(S);
}