本文共 2242 字，大约阅读时间需要 7 分钟。

栈

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵守后进先出LIFO(Last In First out)的原则

• 压栈：栈的插入操作叫做压栈，也可称为进栈或入栈，在栈顶入数据。
• 出栈：栈的删除操作叫出栈，出数据也在栈顶。

栈的实现一般可以使用数组或链表实现，但两者相对而言数组的结构更优一些，因为数组在尾上插入数据的时候是直接用下标插入，而链表则需要找到它的尾指针，然后再进行插入（双向链表除外，这里的链表通常都是单链表）。

栈和一样都可分为静态顺序表和动态顺序表。

静态栈

typedef int STDataType;#define N 10typedef struct Stack{
    STDataType a[N]; int top; // 栈顶}Stack;

静态的栈，由于长度是固定的，在栈满需要增容时，可能会存在空间浪费，因此在实际中并不实用，所以我们经常使用动态的数组

动态栈

typedef int STDataType;typedef struct Stack{
    STDataType* _a; int _top; // 栈顶 int _capacity; // 容量}Stack;

动态栈的接口实现

1. void StackInit(Stack* pst);

描述：对栈进行初始化，为数组a申请4个大小的空间，置top为0，capacity为4.

实现：

void StackInit(Stack* pst)                                          {
           assert(pst);            pst->a = (STDataType*)malloc(sizeof(STDataType)*4);        pst->top = 0;        pst->capacity = 4;    }

2. void StackDestory(Stack* pst);

描述：对申请的空间进行销毁，并将a指针置为NULL，top和capacity置为0。

实现：

void StackDestory(Stack* pst)    {
           assert(pst);                                                  free(pst->a);                             pst->a = NULL;                                             pst->top = pst->capacity = 0;                 }

3. void StackPush(Stack* pst,STDataType x);

描述：在栈顶插入x

实现：

void StackPush(Stack* pst,STDataType x){
       assert(pst);    //说明栈已经满了    if(pst->capacity == pst->top){
           STDataType* tmp =(STDataType*) realloc(pst,pst->capacity*2*sizeof(STDataType));        if(tmp == NULL)        {
               StackDestory(pst);            exit(-1);        }        pst->capacity *= 2;        pst->a = tmp;    }    pst->a[pst->top] = x;                                               pst->top++;}

4. void StackPop(Stack* pst);

描述：弹出栈顶的值

实现：

void StackPop(Stack* pst){
       assert(pst);    assert(!StackEmpty(pst));    --pst->top;}

5. int StackSize(Stack* pst);

描述：返回当前栈的大小值

实现：

int StackSize(Stack* pst){
       assert(pst);    return pst->top;}

6. STDataType StackTop(Stack* pst);

描述：返回当前栈顶的值

实现：

STDataType StackTop(Stack* pst){
       assert(pst);    assert(!StackEmpty(pst));    return pst->a[pst->top - 1];}

7.int StackEmpty(Stack* pst);

描述：判断当前栈是否为空，若为空则返回1，非空则返回0

实现：

int StackEmpty(Stack* pst){
       assert(pst);    return pst->top ==  0 ? 1 : 0;}