【数据结构与算法】—— *栈 *

栈的定义和特点

定义

栈（stack）是限定只在表尾插入和删除操作的线性表

1. 允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）
2. 不含任何数据元素的栈称为空栈

特点

1. 先进后出
2. 后进先出

注意

1. 栈又被称为后进先出（Last In First Out）的线性表，简称LIFO结构
2. 栈的插入操作，称为进栈，也叫压栈，入栈（push）
3. 栈的删除操作，称为出栈，也叫做弹栈（pop）

栈的初始化

定义栈的顺序存储顺序

typedef struct {
    int id;
    char* name;
}ElementType;
typedef struct SeqStack {
    ElementType elements[MAX_SIZE];  //顺序栈中用来存放数据元素的数组
    int top;                         //栈顶（数组中的下标），如果为-1则表明栈为空
    int length;                         //当前栈元素的个数
};

初始化栈

void InitSeqStack(SeqStack* seqstack)
{
    seqstack->top = -1;  //栈指向-1的下标
    seqstack->length = 0;
}

入栈和出栈

入栈

//向栈中压入元素，返回压入的结果(true / false)
int pushStack(SeqStack* seqstack, ElementType element) {
    if (seqstack->top = MAX_SIZE - 1) {
        printf("满栈，压栈失败！");
        return false;
    }
    seqstack->top++; //栈顶指针+1,以便加入新的元素
    //将新插入的元素赋值给栈顶
    seqstack->elements[seqstack->top] = element;
    seqstack->length++;
    return true;
}

---

出栈

//以指针方式返回出栈的元素，返回值为出栈的结果(true / false)
int PopSeqStack(SeqStack* seqstack, ElementType* element)
{
    if (seqstack->top == -1) {
        printf("出栈失败！");
        return false;
    }
    //返回栈顶指向的元素
    *element = seqstack->elements[seqstack->top];
    seqstack->top--;
    seqstack->length--;
    return true;
}

清空栈

void ClearSeqStack(SeqStack* seqstack) {
    seqstack->top = -1;
    seqstack->length = 0;
}