《3、1、1_栈的基本概念.pdf》由会员分享，可在线阅读，更多相关《3、1、1_栈的基本概念.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2020/1/21王道考研/1第三章 栈和队列王道考研数据结构WWW.CSKAOYAN.COM1本节内容栈(Stack)基本概念王道考研/CSKAOYAN.COM22020/1/21王道考研/2王道考研/CSKAOYAN.COM知识总览知识总览注：数据结构三要素逻辑结构、数据的运算、存储结构（物理结构）存储结构不同，运算的实现方式不同3王道考研/CSKAOYAN.COM穿越：线性表的课件穿越：线性表的课件“逻辑结构”“运算”注：数据结构三要素逻辑结构、数据的运算、存储结构（物理结构）存储结构不同，运算的实现方式不同42020/1/21王道考研/3王道考研/CSKAOYAN.COM栈的定义栈的定
2、义线性表是具有相同数据类型的n（n0）个数据元素的有限 序列，其中n为表长，当n = 0时线性表是一个空表。若用L命名线性表，则其一般表示为L = (a1, a2, , ai, ai+1, , an)栈（Stack）是只允许在一端进行插入或删除操作的线性表a1a2a3a4a55王道考研/CSKAOYAN.COM栈的定义栈的定义栈（Stack）是只允许在一端进行插入或删除操作的线性表62020/1/21王道考研/4王道考研/CSKAOYAN.COM栈的定义栈的定义栈（Stack）是只允许在一端进行插入或删除操作的线性表重要术语：栈顶、栈底、空栈a1a2a3a4a5栈顶：允许插入和删除的一端栈底：
3、不允许插入和删除的一端空栈进栈顺序：a1 a2 a3 a4 a5出栈顺序：a5 a4 a3 a2 a1特点：后进先出Last In First Out （LIFO）栈底元素栈顶元素逻辑结构：与普通线性表相同数据的运算：插入、删除操作有区别7王道考研/CSKAOYAN.COM穿越：线性表的基本操作穿越：线性表的基本操作InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。ListDelete(&L,i,&e)
4、：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。其他常用操作：Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。Empty(L)：判空操作。若L为空表，则返回true，否则返回false。增、删改、查（“改”之前也要“查”）创、销82020/1/21王道考研/5王道考研/CSKAOYAN.COM栈的基本操作栈的基本操作InitStack
5、(&S)：初始化栈。构造一个空栈 S，分配内存空间。DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素其他常用操作：StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。创、销增、删查：栈的使用场景中大多只访问栈顶元素删除栈顶元素不删除栈顶元素9王道考研/CSKAOYAN.COM栈的常考题型栈的常考题型进栈顺序：a b c d e有哪些合法的出栈顺序？n个不同元素进栈，出栈元素不同排列的个数为!#!%&。上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明（不要求掌握）。15 + 1!*+10 9 8 7 66 5 4 3 2 1= 42102020/1/21王道考研/6王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点11