什么是栈

对于n个数据元素构成的一个线性序列，如果只允许在其指定的一端插入或删除一个数据元素，这种逻辑结构称为栈（stack）或者栈堆。

允许插入的一端称为栈顶，另一端固定端称为栈底。没有元素的堆栈称为空栈。

栈是一种"后进先出（Last Input First Out）"的数据结构。

栈通常用于数据逆序处理的各种场合，如:

• 对数据进行收尾元素的互换操作
• 函数的嵌套调用和返回地址的存放
• 编译过程中的语法分析等

运算和实现

栈的基本运算主要有入栈，出栈和判断:

• 入栈（压栈）：在栈顶添加新的元素的操作，新的元素成为新的栈顶元素。入栈需要足够的空间，否则栈会产生溢出，称为上溢。

• 出栈（退栈，弹栈）：将栈顶的元素从栈中退出并传递给用户程序的操作，原栈顶元素的后继元素成为新的栈顶。出栈时必须保证栈内数据不能为空，否则发生下溢。

• 判断操作用来检查栈内数据是否为空，返还结果是一逻辑值。如果栈顶和栈底重合，说明栈堆为空。

栈的操作

递归实例

/*  递归演示 */
#include<stdio.h>
void up_and_down(int);
int main()
{
    up_and_down(1);
    return 0; 
}

void up_and_down(int n)
{
    printf("Level %d : n location %p\n", n, &n );
    if ( n < 4 )
        up_and_down( n+1 );
    printf("LEVEL %d : n location %p\n", n, &n);
}

系统的输出为：

Level 1:  n location  0x0012ff48
Level 2:  n location  0x0012ff3c
Level 3:  n location  0x0012ff30
Level 4:  n location  0x0012ff24
LEVEL 4:  n location  0x0012ff24
LEVEL 3:  n location  0x0012ff30
LEVEL 2:  n location  0x0012ff3c
LEVEL 1:  n location  0x0012ff48

我理解的递归

需要注意：

• 每级递归的变量n都属于本级递归私有。
• Level 1 和LEVEL 1 的地址相同，以此类推。