2020年全国计算机二级公共基础知识复习知识点：栈及其基本运算思维导图

栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是先被删除的元素;栈底元素总是先被插入的元素，从而也是后才能被删除的元素。栈是按照"先进后出"或"后进先出"的原则组织数据的。

用一维数组S(1∶m)作为栈的顺序存储空间，其中m为容量。

在栈的顺序存储空间S(1∶m)中，S(bottom)为栈底元素，S(top)为栈顶元素。top=0表示栈空;top=m表示栈满。

栈的基本运算有三种：入栈、退栈与读栈顶元素。

(1)入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1)，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈"上溢"错误。

(2)退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针减一(即top减1)。当栈顶指针为0时，说明栈空，不可进行退栈操作。这种情况称为栈的"下溢"错误。

(3)读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。