37.2° Blog

1.基本概念

一种操作受限的线性表，只能在栈顶插入、删除

特性：后进先出（LIFO）

2.顺序栈实现

2.1 定义

#define MaxSize 50
typedef int ElemType;
typedef struct
{
    // 存放栈中的数据
    ElemType data[MaxSize];
    // 栈顶指针：指向栈顶元素，数组下标，如压入5个数据，top=4
    int top;
}SqStack;

2.2 初始化

// 栈顶指针为 S.top = -1，栈顶元素：S.data[S.top]
void initStack(SqStack& S)
{
    S.top = -1;
}

2.3 进栈

栈不满时，栈顶指针先加1，在送值到栈顶元素

bool push(SqStack& S, ElemType e)
{
    // 栈满，进栈失败
    if (S.top == MaxSize - 1)
        return false;
    // S.data[++S.top] = e;        // 指针先加1，再入栈
    S.top++;                // 指针先加1
    S.data[S.top] = e;      // 新元素入栈
    return true;
}

2.4 出栈

栈非空，先取栈顶元素，再将栈顶指针减1

bool pop(SqStack& S, ElemType& e)
{
    if (S.top == -1)
        return false;
    //e = S.data[S.top--];    // 先出栈，再减一
    e = S.data[S.top];  // 先出栈
    S.top = S.top - 1;  // 再减一
    return true;
}

2.5 读出栈顶元素

bool getTop(SqStack S, ElemType& e)
{
    if (S.top == -1)
        return false;
    e = S.data[S.top];
    return true;
}

2.6 栈长

// 栈长 S.top + 1
int StackLength(SqStack& S)
{
    return S.top + 1;
}

2.7 栈判空

// 栈判空 S.top = -1
bool StackEmpty(SqStack S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}