第三章 特殊线性表一栈、队、串
1
§31栈 §3.1.1栈的逻辑结构 )基本概念 栈是一种限定仅在表的一端进行插入与删除的线性表 允许进行插入与删除的这一端称为栈顶,而另一端称为栈底 不含元素的空表称为空栈 插入与删除分别称进栈与出栈。 栈也称作先进后出( First in last out)的线性表,简称FILO表 a1 a a3 a 进栈 4 出栈 栈底 栈 顶 图栈示意图 2
2 §3.1 栈 • (一)基本概念 • 栈是一种限定仅在表的一端进行插入与删除的线性表 • 允许进行插入与删除的这一端称为栈顶，而另一端称为栈底 • 不含元素的空表称为空栈 • 插入与删除分别称进栈与出栈。 • 栈也称作先进后出（First In Last Out）的线性表，简称FILO表 §3.1.1 栈的逻辑结构 a1 a2 a3 a4 … an 栈 底 栈 顶 进栈 出栈 图 -栈示意图
§311栈的逻辑结构 (一)基本概念 ·栈应用的例子 火车扳道站 进入单车道死胡同的汽车 记录中断返回地址(断点)的结构
3 • (一)基本概念 • 栈应用的例子 –火车扳道站 –进入单车道死胡同的汽车 –记录中断返回地址（断点）的结构 §3.1.1 栈的逻辑结构
s311栈的逻辑结构 ()基本概念 ·可能的出栈次序 ·设n=3,按1,2,3的次序进栈,则可能的出栈 次序为 123、132、213、231、321 不可能的次序是: 312 对任意元素k,若它后面有小于它的元素,则 这些小于它的元素必须以“逆序”出现
4 §3.1.1 栈的逻辑结构 • (一)基本概念 • 可能的出栈次序 • 设n=3，按1,2，3的次序进栈，则可能的出栈 次序为 1 2 3、1 3 2、2 1 3、2 3 1、3 2 1 不可能的次序是： 3 1 2 • 对任意元素k，若它后面有小于它的元素，则 这些小于它的元素必须以“逆序”出现
s311栈的逻辑结构 (二)基本操作 ·Init(s):初始化栈s。设定一个空栈,栈的所有其它操作仅在此 操作执行(或隐含执行)之后才能进行。 Empty(s):判定函数。若栈s为空,返回“真”,否则返回 假 Push(s,x):入栈函数。将元素x放到栈顶上,栈溢出时应返回特 殊标志。 Pop(S):出栈函数。栈sS不空时,将栈顶元素摘除,并返回该元 素。否则触发异常。 GetTop(s):读栈顶元素函数。与Pop(s)类似,但不摘取栈顶元素 · Clear(s):清除操作。使栈s重新变为一个空栈。这里,s是个已 存在的栈。 Len(s):求长度函数。返回栈s中元素个数
5 §3.1.1 栈的逻辑结构 • (二) 基本操作 • Init(s)：初始化栈s。设定一个空栈，栈的所有其它操作仅在此 操作执行（或隐含执行）之后才能进行。 • Empty(s)：判定函数。若栈s为空，返回“真” ，否则返回 “假”。 • Push(s,x)：入栈函数。将元素x放到栈顶上，栈溢出时应返回特 殊标志。 • Pop(S)：出栈函数。栈s不空时，将栈顶元素摘除，并返回该元 素。否则触发异常。 • GetTop(s)：读栈顶元素函数。与Pop(s)类似，但不摘取栈顶元素。 • Clear(s)：清除操作。使栈s重新变为一个空栈。这里，s是个已 存在的栈。 • Len(s)：求长度函数。返回栈s中元素个数