4.4.1 什么是栈

栈允许在同一端执行插入和删除操作，允许执行插入和删除操作的一端称为栈顶（top），另一端称为栈底（bottom）。栈底是固定的，而栈顶是浮动的；如果栈中元素的个数为零，则被称为空栈。插入操作一般称为入栈（Push），删除操作一般称为出栈（Pop）。

1．入栈

入栈将数据保存到栈顶。在执行入栈操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。入栈操作的算法如下。

（1）如果TOP≥n，则输出溢出信息，进行出错处理。在进栈前首先检查栈是否已满，如果满，则溢出；如果不满，则执行步骤（2）。

（2）设置TOP=TOP+1，使栈指针加1，指向进栈地址。

（3）设置S(TOP)=X，结束操作，X为新进栈的元素。

2．出栈

出栈将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。出栈操作的算法如下：

（1）如果TOP≤0，则输出下溢信息，并进行出错处理。在出栈前首先检查是否已为空栈，如果为空，则下溢信息；如果不为空，则执行步骤（2）。

（2）设置X=S(TOP)，把出栈后的元素赋给X。

（3）设置TOP=TOP−1，结束操作，将栈指针减1，指向栈顶。

在Python语言中，常见的栈操作如下所示。

· stack()：建立一个空的栈对象。

· push()：把一个元素添加到栈的顶层。

· pop()：删除栈的顶层元素，并返回这个元素。

· peek()：返回顶层的元素，并不删除它。

· isEmpty()：判断栈是否为空。

· size()：返回栈中元素的个数。