西华师范大学：《算法与程序设计》课程教学资源_第三章 栈和队列

第3章栈和队列 本章主要介绍以下内容: 栈的概念、存储结构及其基本操作 队列的概念、存储结构及其基本操作 栈与队列的应用举例 西师大学数学与信启学院 限出

ぜ3【 ᴸ়䭏݇ ᴀゴЏ㽕ҟ㒡ҹϟݙᆍ˖ l ᷜⱘὖᗉǃᄬټ㒧ᵘঞ݊෎ᴀ᪡԰ l 䯳߫ⱘὖᗉǃᄬټ㒧ᵘঞ݊෎ᴀ᪡԰ l ᷜϢ䯳߫ⱘᑨ⫼В՟ ߎ䗔

3.1栈 3.2队列 西师大学数学与信启学院

3.1 ᷜ 3.2 䯳߫

3.栈 3.1.1栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入 和删除数据元素的操作只能在线性表的一端进行。如 下所示: a1,a2,a3y…,a 插入和删除端 进行插入和删除的一端是浮动端,通常被称为栈 顶,并用一个“栈顶指针”指示;而另一端是固定端, 通常被称为栈底。我们经常将栈用下图31的形式描 述 西师大学数学与信启学院

3.1 ᷜ 3.1.1 ᷜⱘᅮН ᷜᰃϔ⾡⡍⅞ⱘ㒓ᗻ㸼DŽ݊⡍⅞ᗻ೼Ѣ䰤ᅮᦦܹ ੠ߴ䰸᭄᥂ܗ㋴ⱘ᪡԰া㛑೼㒓ᗻ㸼ⱘϔッ䖯㸠DŽབ ϟ᠔⼎˖ 䖯㸠ᦦܹ੠ߴ䰸ⱘϔッᰃ⍂ࡼッˈ䗮ᐌ㹿⿄Ўᷜ 乊ˈᑊ⫼ϔϾ³ᷜ乊ᣛ䩜´ᣛ⼎˗㗠঺ϔッᰃ೎ᅮッˈ 䗮ᐌ㹿⿄ЎᷜᑩDŽ៥Ӏ㒣ᐌᇚᷜ⫼ϟ೒3-1ⱘᔶᓣᦣ 䗄˖ a1 , a2 , a3 , ..., an ᦦܹ੠ߴ䰸ッ

栈顶top a2 图3-1 西师大学数学与信启学院

an ... a2 a1 ᷜ乊 top ೒ 3-1

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

㒧䆎˖ৢ䖯ߎܜ˄Last In First Out˅ˈㅔ⿄Ў LIFO㒓ᗻ㸼DŽ В՟1˖ᆊ䞠ৗ佁ⱘ⹫ˈ䗮ᐌ೼⋫ᑆޔৢϔϾϔϾ ഄ㨑೼ϔ䍋ᄬᬒˈ೼Փ⫼ᯊˈ㢹ϔϾϔϾഄᣓˈϔᅮ ᳔ܜᣓ䍄᳔Ϟ䴶ⱘ䙷া⹫ˈ㗠᳔ৢᣓߎ᳔ϟ䴶ⱘ䙷া ⹫DŽ В՟2˖೼ᓎㄥᎹഄϞˈՓ⫼ⱘⷪഫҢᑩᕔϞϔሖ ϔሖഄⷕᬒˈ೼Փ⫼ᯊˈᇚҢ᳔Ϟ䴶ϔሖϔሖഄᣓ পDŽ ϟ䴶៥Ӏܜ㒭ߎᷜ㒧ᵘⱘ෎ᴀ᪡԰˖ ˄1˅߱ྟ࣪ ᷜInitStack(S) ˄2˅ܹᷜ Push(S,item) ˄3˅ߎ ᷜPop(S,item) ˄4˅㦋পᷜ乊ܗ㋴ݙᆍ GetTop(S,item) ˄5˅߸ᮁᷜᰃ৺Ўぎ StackEmpty(S)

3.1.2栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次 存放栈中的每个数据元素,并用起始端作为栈底 类型定义如下所示: #define maX stack 10 栈的最大数据元素数目 typedef struct stack( Stack Entry item MAX STACK]; /放栈中数据元素的存储单元 int top: ∥栈顶指针 JSTACK; 西师大学数学与信启学院

3.1.2 ᷜⱘ乎ᑣᄬټ ᷜⱘ乎ᑣᄬټ㒧ᵘᰃ⫼ϔ㒘䖲㓁ⱘᄬټऩܗձ⃵ ᄬᬒᷜЁⱘ↣Ͼ᭄᥂ܗ㋴ˈᑊ⫼䍋ྟッ԰ЎᷜᑩDŽ ㉏ൟᅮНབϟ᠔⼎˖ #define MAX_STACK 10 //ᷜⱘ᳔໻᭄᥂ܗ㋴᭄Ⳃ typedef struct stack{ StackEntry item[MAX_STACK]; //ᄬᬒᷜЁ᭄᥂ܗ㋴ⱘᄬټऩܗ int top; //ᷜ乊ᣛ䩜 }STACK;

基本操作算法: 1.初始化栈S void Inltstack(STACK *S i s->top=-1; 3 入栈 void Push(stackS, StackEntry item if(S>top= MAX STACK-)exit(“ Stack is ful”); else s->item[++S->topl=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-I 图32 西师大学数学与信启学院

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

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. topl 西师大学数学与信启学院

ᷜߎ .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(sTACKs) if(s top=-1)return TRUE else falses 结论:由于栈的插入和删除操作具有它的特殊 性,所以用顺序存储结构表示的栈并不存在插入删除 数据元素时需要移动的问题,但栈容量难以扩充的弱 点仍就没有摆脱。 西师大学数学与信启学院

5. ߸ᮁᷜSᰃ৺Ўぎ int StackEmpty(STACK S) { if (S.top==-1) return TRUE; else FALSE; } 㒧䆎˖⬅Ѣᷜⱘᦦܹ੠ߴ䰸᪡԰݋᳝ᅗⱘ⡍⅞ ᗻˈ᠔ҹ⫼乎ᑣᄬټ㒧ᵘ㸼⼎ⱘᷜᑊϡᄬ೼ᦦܹߴ䰸 ᭄᥂ܗ㋴ᯊ䳔㽕⿏ࡼⱘ䯂乬ˈԚᷜᆍ䞣䲒ҹᠽܙⱘᔅ ⚍ҡህ≵᳝ᨚ㜅DŽ