1. 栈的定义和概念

栈是限定仅在表尾进行插入或删除操作的线性表。

表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈又称为后进先出的线性表（ LIFO结构，Last In, First Out）。

插入元素的操作叫做入栈，删除栈顶元素的操作叫做出栈。

2. 用鲜活的比喻来理解栈

大家设想一下，你手头有一只方方正正的箱子，这个箱子是能放书进去的，而且底面积更好和你要放的书是一样大小的，你放书进去也只能打平放，不能竖着放。（为了避免杠精要来和我纠缠，我必须把规则说得清晰一些）。

然后，你开始放书进入，可以想象，你每次放进去的书只会在最顶端；有时候，你也会从箱子里面拿书出来，你也只能拿最顶上的那一本，因为书和箱子的底面积一样，你没办法直接把手伸到下面拿下面的那些数。

1. 箱子就是栈

2. 放书进箱子：这是入栈，新放入的书在箱子的最顶部

3. 取书：这是出栈，永远都是拿到了最顶端的书

4. 箱子空了，里面没有书了，这就是空栈

5. 箱子满了，那就是溢栈了，类似于数组定义得不够大，越界了

我们之所以要打这个比喻，是因为我们写程序的时候有时候就是会遇到这类问题。我们琢磨好了这种情况，知道如何处理，后面就会解一批同类的题目了。

3. 基于数组来简单实现栈

栈的实现有很多方法，以后大家还会学到 STL 模板，人家封装好模板我们只管用，功能很强大，很好用，但是要记和背很多函数，我们暂时先不学 STL。考试的理论知识题一般是不会考 STL 模板的，只会考大家基于数组来实现栈的算法，所以大家非常有必要学一下如何基于数组和 top 指针来实现栈。

上图就是栈的的示意图，灰色的表示数据，输出被存入数组。一般从下标 1 开始使用，因为 0 会有特殊用途。当栈为空的时候，top == 0 ，数组的 0 下标存放一个特殊的数往往可以简化代码（存入什么数要看题目的情况了，以后在实战训练里面再进一步讲解）。

所以，栈的数据是存放在从 1 到 top 这段范围，一般采用左闭右闭原则。

1. 入栈

既然是来一个新的数据，那就是放在栈顶，所以，首先 top 指针增加 1 ，然后把新来的数据赋值到数组。这两个顺序不能搞乱

void push(int t)
{
    if(top==n-1)
        printf("错误，栈已满");
    else
    {
        top+=1;
        Stack[top] = t;
    }
}

或者简化为

void push(int t)
{
    if(top==n-1)
        printf("错误，栈已满");
    else
        Stack[++top] = t;
}

2. 出栈

一般来说，出栈之前会先获取栈顶数据，可能会保存到另外的一个变量里面，然后再来出栈。

出栈只需要把 top 指针减一即可。之前的数据还留在数组里面，但是因为 top 变量已经不指向它了，就相当于被删掉了。

int pop()
{
    if(top==0)
    {
        printf("错误，栈已空");
        return -1; // -1 为错误代码。当栈内数据不可能等于 -1 时可以使用
    }
    else
    {
        int ret=Stack[top];
        top-=1;
        return ret；
    }
}

或者简化为

int pop()
{
    if(top==0)
    {
        printf("错误，栈已空");
        return -1; // -1 为错误代码。当栈内数据不可能等于 -1 时可以使用
    }
    else
        return Stack[top--]；
}

4. 栈内只有 1 个数据

top == 1 的时候表示栈内只有 1 个数据。

5. 空栈

top == 0 的时候表示栈已经空。空栈的情况下不能继续做出栈操作（都没东西了，还怎么出？），程序里面一般要写一些针对空栈的逻辑。

6. 清空栈内所有数据

只需要让 top 指针指向下标 0 即可。

top = 0;

4. 术语

栈顶指针： tail 或者 top （使用 top 会比使用 tail 更多）

弹出： pop

压栈: push