吉林大学：《数据结构》课程电子教案（PPT课件）第四章 栈和队列

第四章 栈找和队列

第四章 栈 和 队 列

4.1悦 4.1.1 栈的定义和操作 。栈的定义：栈是插入和删除只能在其一端进 行的线性表。 出栈 进栈 [例]有一线性表 (a1,a2,,a5) 栈顶 as 进栈和出栈情况。 a4 a3 a2 栈底 aj

4.1 栈 4.1.1 栈的定义和操作 ● 栈的定义：栈是插入和删除只能在其一端进 行的线性表。 a5 a3 a2 a1 a4 出栈 进栈 栈顶 栈底 [例] 有一线性表 (a1, a2, …, a5) 进栈和出栈情况

。栈的特性： ①有序性。 ②后进先出性

● 栈的特性： 有序性。 后进先出性。 ① ②

●栈的ADT描述。 ADT Stack is Data 包含栈顶位置信息的数据项 Operations Constructor Initial Values:无 Press: 堆栈初始化

● 栈的 ADT 描述。 ADT Stack is Data 包含栈顶位置信息的数据项 Operations Constructor Initial Values:无 Press: 堆栈初始化

StackEmpty Input: 无 Preconditions: 无 Press: 检查堆栈是否为空 Output: 若为空返回t,否则返回f Postconditions:无 Pop Input: 无 Preconditions: 堆栈非空 Press: 删除栈顶元素 Output: 返回被删除的栈顶元素 Postconditions 原栈顶元素被从栈中删除

StackEmpty Input: 无 Preconditions: 无 Press: 检查堆栈是否为空 Output: 若为空返回t，否则返回f Postconditions: 无 Pop Input: 无 Preconditions: 堆栈非空 Press: 删除栈顶元素 Output: 返回被删除的栈顶元素 Postconditions 原栈顶元素被从栈中删除

Push Input: 准备压入堆栈的元素 Preconditions: 无 Press: 将元素压入栈顶 Output: 无 Postconditions:新压入元素成为栈顶元素 Peek Input: 无 Preconditions: 堆栈非空 Press: 访问栈顶元素 Output: 栈顶元素的数据值 Postconditions:堆栈不变

Push Input: 准备压入堆栈的元素 Preconditions: 无 Press: 将元素压入栈顶 Output: 无 Postconditions: 新压入元素成为栈顶元素 Peek Input: 无 Preconditions: 堆栈非空 Press: 访问栈顶元素 Output: 栈顶元素的数据值 Postconditions: 堆栈不变

end ADT Stack

end ADT Stack

4.1.2 栈的顺序表示和实现 栈内变化情况 321 3 1 top 0 A top -1 3 3 2 32 top 今 top ,1 B 1 0 A 0 A 0 top- -1

4.1.2 栈的顺序表示和实现 top 1 2 3 0 -1 top 1 2 3 0 A C B top 1 2 3 0 A B top 1 2 3 0 A top 1 2 3 0 -1 栈 内 变 化 情 况

1顺序栈的类定义 include include const int MaxStackSize =50; Template Class Stack private T stacklist [MaxStackSize]; int top;

1 顺序栈的类定义 # include # include const int MaxStackSize = 50; Template Class Stack private T stacklist[MaxStackSize]; int top;

public: Stack (void); void Push(const T&item); T Pop(void); void ClearStack(void); T Peek(void)const; int StackEmpty(void)const; int StackFull(void)const; }；

public: Stack(void); void Push(const T& item); T Pop(void); void ClearStack(void); T Peek(void) const; int StackEmpty(void) const; int StackFull(void) const; };