栈的基础知识是软件评测师考试的重要考点，经常出现在上午场的客观选择题当中。栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈又称为先进后出(FILO，或后进先出)的线性表。在栈中进行插入和删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)，不含数据元素的栈称为空栈。下面就该知识点并结合例题进行总结学习。
一、栈的基本运算
（1）初始化栈 InitStack(S)：创建一个空栈S。
（2）判断栈是否为空 StackEmpty(S)：当栈S为空栈时返回“真”，否则返回“假”。
（3）入栈 Push(S，x)：将元素x加入栈顶，并更新栈顶指针。
（4）出栈 Pop(S)：将栈顶元素从栈中删除，并更新栈顶指针。
（5）读栈顶元素 Top(S)：返回栈顶元素的值，但不修改栈顶指针。
二、栈的存储结构
（1）顺序存储：指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在顺序存储方式下，需要预先定义或申请栈的存储空间，也就是说栈空间的容量是有限的。因此在顺序栈中，当一个元素入栈时，需要判断是否栈满(即栈空间中没有空闲单元)，若栈满，则元素入栈会发生上溢现象。栈的操作示意图如下所示：
（2）链式存储：为了克服顺序存储的栈可能存在上溢的不足，可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈项一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。链栈的表示如图所示：
三、栈的应用：表达式求值、括号匹配等。
实例：计算机在处理算术表达式时，可将表达式先转换为后缀形式，然后利用栈进行计算。例如，表达式“46+5*(120-37)”的后缀表达式形式为：
46 5 120 37 - * +
计算后缀表达式时，从左至右扫描表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈顶弹出运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束。例如，上面后缀表达式的计算过程为:
（1）依次将46，5，120， 37压入栈中。
（2）遇到“-”，取出37，120， 计算120-37， 得83，将其压入栈中。
（3）遇到“*”，取出83，5，计算5*83，得415，将其压入栈中。
（4）遇到“+”，取出415，46，计算46+415，得461， 将其压入栈中。
（5）表达式结束，计算过程完成。
下面是近几年对该知识点考察过的真题，以后仍是考试出题的重点，大家要重视起来。
【2017年第21题】对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d，则合法的出栈序列为（ ）。
A、d c b a
B、d a b c
C、d c a b
D、d b c a
解析：本题考查栈的基础知识。
题干要求d第一个出栈，入栈的次序为a、b、c、d，且每个元素进栈、出栈各1次。栈的特点是先进后出的，d第一出栈，那么此时a、b、c都在栈中，所以出栈序列只能是：d、c、b、a。
故正确答案为：A
【2018年第22题】可利用一个栈来检查表达式中的括号是否匹配，其方法是：初始时设置栈为空，然后从左到右扫描表达式，遇到左括号“(”就将其入栈，遇到右括号“)”就执行出栈操作，忽略其他符号。对于算术表达式“a*(b+c))d”，由于（ ），因此可判断出该表达式中的括号不匹配。
A、需要进行出栈操作但栈已空
B、需要进行入栈操作但栈已满
C、表达式处理已结束，但栈中仍留有字符“(”
D、表达式处理已结束，但栈中仍留有字符“)”
解析：本题考查栈的基础知识。
左括号入栈，右括号出栈，，该题中括号为：（）），忽略其他符号，所以共进行了1次入栈操作，2次出栈操作。当执行第2个出栈操作时，第一个左括号已经出栈了，此时栈为空栈，所以可以判断出括号不匹配。
故正确答案为：A
作者唯一官方个人微信公众号（昊洋与你一起成长）：HYJY20180101
写于2021年10月12日
作者：昊洋讲师
版权所有，侵权必究
