|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 >
|
被考次数：10次
被考频率：高频率
总体答错率：30%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
相关知识点：30个
|
|
|
|
|
|
|
栈（Stack）是一种特殊的线性表，是限定仅在表尾进行插入或者删除操作的线性表。进行插入和删除的那一端称为栈顶（top），另一端称为栈底（bottom）。栈的插入操作和删除操作也分别简称进栈和出栈。
|
|
|
|
如果栈中有n个结点｛k0，k1，k2，…, kn-1｝，k0为栈底，kn-1是栈顶，则栈中结点的进栈顺序为k0, k1, k2，…，kn-1，而出栈的顺序为kn-1, kn-2，…, k1,k0，如下图所示。
|
|
|
|
|
|
|
|
栈的主要操作是桟的初始化、插入和删除运算、判断栈是否为空以及读取栈顶结点的值等操作。栈的类型的描述如下：
|
|
|
|
|
|
和顺序表类似，栈的实现方式一般也有两种：顺序存储和链式存储。下面主要介绍顺序栈。由于栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制，使得它们仅能在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。一般地，可以设定一个足够大的一维数组存储栈，数组中下标为0的元素就是栈底，对于栈顶，可以设一个指针top指示它。为了方便，设定top所指的位置是下一个将要插入的结点的存储位置，这样，当top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
顺序存储栈的几个基本操作的具体实现，具体如下所示：
|
|
|
|
|
|
|
|
表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。
|
|
|
|
在计算机中，任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符可以是算术运算体符、关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符。在本节中，仅讨论简单算术表达式的求值问题。在这种表达式中只含加、减、乘、除四则运算，所有的运算对象均为单变量。表达式的结束符为“#”。
|
|
|
|
|
|
|
|
中缀表达式是通常使用的一种表达式，中缀表达式的计算规则如下。
|
|
|
|
（1）括号内的操作先执行，括号外的操作后执行。如有多层括号，则先执行内层括号内的操作，再执行外括号内的操作。
|
|
|
|
|
|
（3）在有多个乘除或加减运算可选择时，按从左到右的顺序执行，即优先级相同的操作符按先后次序进行。
|
|
|
|
|
|
后缀表达式中只有操作数和操作符，它不再含有括号，操作符在两个操作数之后。它的计算规则非常简单，严格按照从左向右的次序依次执行每一个操作。每遇到一个操作符，就将前面的两个操作数执行相应的操作。
|
|
|
|
|
|
队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，first in first out）的原则组织数据的，因此，队列也被称为“先进先出”表。下面用C语言描述队列类型为：
|
|
|
|
|
|
队列分为链队列和循环队列。链队列主要采取顺序存储方式，下面主要介绍链队列的顺序存储。队列的顺序存储在c语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针front和rear，front指示的是队列中最前面，即队首结点在数组中元素的下标，rear指示的是队尾结点在数组中元素的下标的下一个位置，也就是说rear指示的是即将插入的结点在数组中的下标。下图所示的是队列的几种状态：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
链队列还有链式存储结构，与顺序表的链式存储结构类似。循环队列的操作与链队列相似，这里就不再累述了。
|
|
|
