栈的深入理解

一.基本概念

栈是仅限制在表尾进行插入和删除操作的特殊线性表，

限制操作的表尾端称为“栈顶”, 另一 端称为“栈底”

特点：

栈是“后进先出”的线性表（LIFO）或 “先进后出”的线性表（FILO）

?

二.栈的抽象数据类型

基本操作和含义

常见操作

?

?

三.顺序栈

存储结构

与顺序表一样，顺序栈也是使用数组来实现。

?

基本操作

入栈

要求：

插入元素x使其成为顺序栈中新的栈顶元素

步骤：

关键代码 ?

算法 ?

出栈

要求

将栈顶元素从栈中移去，并返回被移去的栈顶元素值

步骤

关键代码 ?

算法 ?

四.链栈

存储结构

重要结论

基本操作

求链栈的长度

操作 length ()的实现

计算出链栈中所包含的数据元素的个数并返回其值

动画

解法

链栈的入栈操作

push (x )的实现

将数据域值为x的新结点插入到链栈的栈顶，使其成为新的栈顶元素。

动画

步骤：

算法实现 ?

链栈的出栈操作

将首结点（或栈顶结点）从链栈中移去，并返回该结点的数据域的值。

动画

?

?

算法： 出栈操作 ?