第3章 栈和队列

1、1 .数据结构课程的内容、2、数据结构课程的内容、3、3.1堆栈(Stack )、第3章堆栈和队列、3.2队列(Queue )、1 .定义2 .逻辑结构3、可以是顺序堆栈，也可以是链接堆栈，也可以是顺序堆栈中的组合图层性质变更选项。 重要的是描述堆栈和堆栈函数。 具体实现取决于顺序堆栈或链接堆栈。 基本操作包括堆栈、堆叠、读取堆栈元素值、创建堆栈或确定堆栈已满、堆栈为空等。 中的组合图层性质变更选项。 只能在表的一端进行插入和删除运算的线性表(只能在堆栈上操作)、5，q :什么是堆栈？这和一般的线性表有什么不同？ 3.1堆栈，a :堆栈是一种特殊的线性表，只能在表的一端(堆栈的顶部)插入和删除

2、。 与一般的线性表的不同：只是算法不同。一般线性表堆栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、连锁表存储结构：顺序堆栈、连锁堆栈运算规则：随机存取运算规则：后退先出(LIFO )、“前进”压入=PUSH(x )”，脚注(即an端子)称为堆栈顶部top 是被称为堆栈底base，例如，堆栈s=(a1，a2，a3，an-1，an )、a1将堆栈底要素an称为堆栈顶要素，将从被称为堆栈顶(插入要素)的堆栈的最上面(即，脚注)删除最后要素的操作称为堆栈顶要素教材P44更详细地定义了堆栈：强调插入和删除只能在表的一端(堆栈上)，7，顺序堆栈模式图，8，表和堆栈的操作区别对线性表s=(a1，a2，

3、an-1，an )，写入： vi=ai 堆栈操作示例存储在堆栈中(a，b，c，d ) (注意遵循后退先出的原则)，a，a，C B A，B A，核心句： top。 序列堆栈推式函数status推式(元素x ) if (顶)溢出else vtop =x； 推(b )； 推(c )； 推(d )； 低地址l，推(a )； 高地址m，b，c，d，10，堆叠操作例如从堆叠中取出b (注意遵循“后退先出”的原则)，核心句： Pop ()； Pop ()； Printf(Pop () )； 序列堆栈中的POP函数status pop () if (顶部=l )下溢else y=v-顶部。 返回(y )；11

4、、示例1 :堆栈的输入序列是12345，如果在输入到堆栈时允许堆栈，堆栈的输出序列43512能实现吗？ 43512不能实现，主要是其中12个顺序不能实现，12345的输出可以实现，只需按下一个即可弹出一个。 另外，在435612成为12的顺序不能实现135426。 例2 :如果堆栈的输入序列是123456，可以获得435612和135426的堆栈序列吗？a :a :12，例3 (严格问题集3.1 )一个堆栈的输入序列是123，如果允许在进入堆栈的过程中提取堆栈，则a :可通过包括所有可能性而求解： 1输入1输出、2输入2输出、3输入3输出，即123 1输入1输出、2输入3输出、3输入3输出、2输出，即132； 1、2输入、2输出、3输入3输出，即231。 一、二输入、二、一输出、三输入三输出，即213。 一、二、三输入、三、二、一输出，即321。 总共有五种可能性。13、例4 :修正计算机系统2001年考研问题(编程基础)，假设一个堆栈中依次放入的元素数组为c、a、b、d，则可以得到堆