数据结构3资料讲解.ppt

《数据结构3资料讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构33.1.1栈的抽象数据类型定义3.1栈(Stack)栈是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当栈中没有元素时称为空栈。9/2/2021假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出(LIFO)表。例、一叠书或一叠盘子。anan-1a2a1栈顶栈底……栈的抽

2、象数据类型定义为：ADTStack{Data:D＝{ai

3、ai∈DataSet,i=1,2,...,n,n≥0}//称n=0时的栈为空栈。Structure:R＝{

4、ai-1,ai∈D,i=2,...,n}//约定an端为栈顶，a1端为栈底。Operation:Stack();//构造一个空栈~Stack（）；voidPush(DataTypeitem);//进栈DataTypePop();//出栈DataTypeGetTop();//取栈顶元素voidMakeEmpty();//置空栈boo

5、lIsEmpty();//判栈空否boolIsFull();//判栈满否}由于栈的逻辑结构与线性表相同，因此线性表的存储结构对栈也适应。3.1.2栈的实现顺序栈链栈9/2/2021栈的顺序存储结构简称为顺序栈，由于栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一端；而栈顶位置是随着入栈和出栈操作而变化的.1.顺序栈顺序栈的类型定义如下：constintMaxStackSize=50//栈中能容纳最大元素个数classStack{DataTypeStackList[MaxStackSize];int

6、top;public:Stack();//构造函数，初始化topboolIsEmpty()//判断栈的状态是否为空，为空返回true，否则返回false9/2/2021boolIsFull()//判断栈的状态是否满，若满返回true，否则返回falseDataTypeGetTop();//取栈顶元素voidPush(constDataTypex);//入栈DataTypePop();//出栈voidClear();//栈清空};//StackStack(){//构造函数初始化一个空栈{StackList=new

7、DataType[MaxStackSize];top=-1;}//StackboolIsEmpty()//判断栈是否为空{if(top==-1)returntrue;elsereturnfalse;}boolIsFull()//判断栈是否已满{if(top==MaxStackSize-1)returntrue;elsereturnfalse;}DataTypeGetTop()//取栈顶元素{if(IsEmpty()){cout<<”栈空！”<

8、;}voidPush(DataTypex)//向栈顶压入元素{if(IsFull()){cout<<”栈满！”<next=NULL。插入与删除仅在

9、栈顶处进行，链式栈的栈顶在链表头。链栈的定义typedefstructStackNode{DataTypedata;//结点数据StackNode*next;//结点链指针}//StackNodeclassStack{StackNode*top;//栈顶指针Public:Stack(){top=newStackNode;top->next=NULL;}//创建头结点voidPush(DataTypeitem);链栈的定义DataTypePop();DataTypeGetTop();voidClear();boo

10、lIsEmpty(){returntop->next==NULL;}}//入栈操作voidPush(DataTypeitem){//入栈操作p=newStackNode;p->data=item;p->next=top->next;top->next=p;}//Push出栈操作DataTypePop(){//出栈操作if(top->next!=NULL){p=top->next;Dat