堆栈(Stack)：具有一定约束操作的线性表。

• 只在一端（栈顶 Top）做插入、删除操作
• 插入数据：Push
• 删除数据：Pop
• 后入先出：LIFO

1. 堆栈的顺序存储实现

• 堆栈的顺序存储实现一般由一个一维数组和一个记录栈顶元素位置的变量组成。

struct SqStack{
    ElementType data[MAXSIZE];
    int top;
}
typedef struct SqStack* Stack;

主要操作

1. 入栈
void Push(Stack ptrS,ElementType item)
{
    if(ptrS->top == MAXSIZE - 1){
        printf("堆栈满");
        return;
    }else{
        ptrS->data[++ptrS->top] = item;
    }
}
2. 出栈
ElementType  Pop(Stack ptrS)
{
    if(ptrS.top == -1){
        printf("栈空");
        return ERROR;
    }else{
        return ptrS->data[PtrS->top--];
    }
}

案例

要求用一个数组实现两个堆栈，要求最大限度的利用数组空间，只要有空闲位置就能入栈。

struct DStack{
    ElementType data[MAXSIZE];
    int top1;
    int top2;
}ds;
ds.top1 = -1;
ds.top2 = MAXSIZE;
//入栈
void Push(struct DStack *ptrS,ElementType item, int tag)
{
    if(ptrS->top2 - ptrS->top1 == 1){
        printf("堆栈满");
        return;
    }
    if(tag == 1)
        ptrS->data[++ptrS->top1] = item;
    else
        ptrS->data[--ptrS->top2] = item;
}
//出栈
ElementType Pop(struct DStack*ptrS,int tag)
{
    if(tag == 1){
        if(ptrS->top1 == -1)
        {
            printf("堆栈1空");
            return NULL;
        }
        return ptrS->data[ptrS->top1--];
    }else{
        if(ptrS->top1 == MAXSIZE)
        {
            printf("堆栈2空");
            return NULL;
        }
        return ptrS->data[ptrS->top2++];
    }
}

2. 堆栈的链式存储实现

• 堆栈的链式存储实际上是个单链表，叫做链栈。插入、删除在栈顶进行。栈顶在头结点。