(14)--第三章第三节链栈的基本操作.pdf

01【链栈的存储结构】

目录02【取栈顶元素】

CONTENTS03【入栈】

04【出栈】

01链栈的存储结构

链栈的存储结构

•链栈结点结构与单链表相同。

datanext

•链栈用单链表实现

S…/\

栈顶设在哪里好？

链栈的存储结构

栈顶指针S

anan-1a1∧

注意:链栈中指针的方向

//栈的链式存储表示

typedefLinkListLinkStack;

链栈的存储结构

链栈的基本形态

带头结点

•非空栈S…/\

•空栈S/\

不带头结点（以下操作针对此种情况）

•非空栈S…/\

•空栈S/\

02取栈顶元素

取栈顶元素

1.问题分析

•操作名称：GetTop(S，e)

•初始条件：栈S已存在且非空

•操作结果：用e返回S的栈顶元素

Sanan-1a1∧

算法思想：

1)首先判断栈是否为空，若栈为空，则返回ERROR；

2)若栈不空则取S指向的栈顶元素，返回OK。

取栈顶元素

2.算法描述

//若栈不空，则用e返回S的栈顶元素，返回OK，否则返回ERROR

StatusGetTop(LinkStackS，ElemTypee)

{//判断栈是否为空

if(S==NULL)returnERROR;

//栈不空，取栈顶元素

e=S-data;//栈顶元素为S指示的元素

returnOK;

}

03入栈

S

入栈eanan-1a1∧

1.问题分析p

•操作名称：Push(S，e)

•初始条件：栈S已存在

•操作结果：插入元素e为新的栈顶元素

算法思想：

1)首先申请结点空间，建立新结点；

2)然后将新结点插入到链栈中作为新的栈顶元素；

3)最后移动栈顶指针到新的栈顶。

入栈

2.算法描述

//插入元素e为新的栈顶元素

StatusPush(LinkStackS,ElemTypee)

{//建立结点

p=(LinkStack)malloc(sizeof(LNode));

p-data=e;

//插入栈顶（链表头）

p-next=S;

S=p;

returnOK;

}