《数据结构》课程教学资源：第三章 栈和队列

3拿能和队列 本章主要介绍以下内容: 栈的概念、存储结构及其基本操作 队列的概念、存储结构及其基本操作 栈与队列的应用举例 请单市鼠标左键换页 退比

第3章 栈和队列 本章主要介绍以下内容： ⚫ 栈的概念、存储结构及其基本操作 ⚫ 队列的概念、存储结构及其基本操作 ⚫ 栈与队列的应用举例 退出

3.,L线 3.2从列 请单市鼠标左键换页

3.1 栈 3.2 队列

3.1栈 31.1栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入 和删除数据元素的操作只能在线性表的一端进行。如 下所示 插入和删除端 进行插入和删除的一端是浮动端,通常被称为栈 顶,并用一个“栈顶指针”指示;而另一端是固定端, 通常被称为栈底。我们经常将栈用下图3-1的形式描述: 请单市鼠标左键换页

3.1 栈 3.1.1 栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入 和删除数据元素的操作只能在线性表的一端进行。如 下所示： 进行插入和删除的一端是浮动端，通常被称为栈 顶，并用一个“栈顶指针”指示；而另一端是固定端， 通常被称为栈底。我们经常将栈用下图3-1的形式描述： a1 , a2 , a3 , ..., an 插入和删除端

栈顶top a 图3-1 请单市鼠标左键换页

an ... a2 a1 栈顶 top 图 3-1

结论:后进先出( Last In first out),简称为 LIFO线性表。 举例1:家里吃饭的碗,通常在洗干净后一个一个 地落在一起存放,在使用时,若一个一个地拿,一定 最先拿走最上面的那只碗,而最后拿出最下面的那只 碗 举例2:在建筑工地上,使用的砖块从底往上一层 层地码放,在使用时,将从最上面一层一层地拿取 下面我们先给出栈结构的基本操作 (1)初始化栈 InitStack(S) (2)入栈Push(S,item) (3)出栈Pop(S,item) (4)获取栈顶元素内容 GetTop(S,tem) (5)判断栈是否为空 StackEmpty(S) 请单市鼠标左键换页

结论：后进先出（Last In First Out），简称为 LIFO线性表。 举例1：家里吃饭的碗，通常在洗干净后一个一个 地落在一起存放，在使用时，若一个一个地拿，一定 最先拿走最上面的那只碗，而最后拿出最下面的那只 碗。 举例2：在建筑工地上，使用的砖块从底往上一层 一层地码放，在使用时，将从最上面一层一层地拿取。 下面我们先给出栈结构的基本操作： （1）初始化栈 InitStack(S) （2）入栈 Push(S,item) （3）出栈 Pop(S,item) （4）获取栈顶元素内容 GetTop(S,item) （5）判断栈是否为空StackEmpty(S)

3.1.2栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次 存放栈中的每个数据元素,并用起始端作为栈底。 类型定义如下所示: #define maX stack 1o 的最大数据元素数目 typedef struct stack( Stack Entry item MAX STACKI 放栈中数据元素的存储单元 int top ∥栈顶指针 STACK: 请单市鼠标左键换页

3.1.2 栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次 存放栈中的每个数据元素，并用起始端作为栈底。 类型定义如下所示： #define MAX_STACK 10 //栈的最大数据元素数目 typedef struct stack{ StackEntry item[MAX_STACK]; //存放栈中数据元素的存储单元 int top; //栈顶指针 }STACK;

基本操作算法 1.初始化栈S void InItStack(STACK * S) {s->top=-1;} 2.入栈 void Push(stacKS, Stack Entry item) if(S>top= MAX STACK-1)exit(“ Stack is full”); else s->item[++S->top]=item 请单市鼠标左键换页

基本操作算法： 1. 初始化栈S void InItStack(STACK *S) { s->top=-1; } 2. 入栈 void Push(STACK *S,StackEntry item) { if (S->top==MAX_STACK-1) exit(“Stack is full”); else S->item[++S->top]=item; }

MAX STACK-1 0 tp=-1 图3-2 请单市鼠标左键换页

图 3-2 MAX_STACK-1 ... 1 0 top= -1

3.出栈 void Pop(stACK*S, Stack Entry *item) if( StackEmpt!y(*S)exit(“ Stack is empty”); else *item=S->item[s->top--I; 4.获取栈顶元素内容 void GetTop(stack s, stack Entry *item) if(StackEmpty())exit(Stack is empty); else *item=S item Stop]; 请单市鼠标左键换页

3. 出栈 void Pop(STACK *S,StackEntry *item) { if (StackEmpty(*S)) exit(“Stack is empty”); else *item=S->item[S->top--]; } 4. 获取栈顶元素内容 void GetTop(STACK S,StackEntry *item) { if (StackEmpty(S)) exit(“Stack is empty”); else *item=S.item[S.top]; }

5.判断栈S是否为空 int StackEmpty(STACK S) if(.top==-1)return TRUE else falses 结论:由于栈的插入和删除操作具有它的特殊性, 所以用顺序存储结构表示的栈并不存在插入删除数据 元素时需要移动的问题,但栈容量难以扩充的弱点仍 就没有摆脱。 请单市鼠标左键换页

5. 判断栈S是否为空 int StackEmpty(STACK S) { if (S.top==-1) return TRUE; else FALSE; } 结论：由于栈的插入和删除操作具有它的特殊性， 所以用顺序存储结构表示的栈并不存在插入删除数据 元素时需要移动的问题，但栈容量难以扩充的弱点仍 就没有摆脱