国家级精品章节程数据结构与算法

《国家级精品章节程数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、国家级精品课程—《数据结构与算法》张铭、赵海燕、王腾蛟、宋国杰、高军http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/北京大学信息科学与技术学院“数据结构与算法”教学小组本章主笔：赵海燕版权所有，转载或翻印必究第3章栈与队列主要内容3.1栈(Stack)3.2队列(Queue)3.3栈和队列的比较大纲2.1线性表(linearlist)2.2顺序表—向量(Sequentiallist—vector)2.3链表(Linkedlist)2.4线性表实现方法的比较2.5栈(Stack)2.6队列(

2、Queue)操作受限的线性表栈（Stack）运算只在表的一端进行队列（Queue）运算只在表的两端进行栈后进先出（LastInFirstOut）一种限制访问端口的线性表栈存储和删除元素的顺序与元素到达的顺序相反也称为“下推表”栈的主要元素栈顶（top）元素：栈的唯一可访问元素元素插入栈称为“入栈”或“压栈”（push）删除元素称为“出栈”或“弹出”（pop）栈底：另一端栈的示意图每次取出（并被删除）的总是刚压进的元素，而最先压入的元素则被放在栈的底部当栈中没有元素时称为“空栈”k0k1...kn-1栈顶栈底出栈进栈栈的主要操作压栈（

3、push）出栈（pop）读取栈顶元素（top）判断栈是否为空（isEmpty）栈的抽象数据类型template//栈的元素类型为TclassStack{public://栈的运算集voidclear();//变为空栈boolpush(constTitem);//item入栈，成功则返回真，否则返回假boolpop(T&item);//返回栈顶内容并弹出，成功返回真，否则返回假booltop(T&item);//返回栈顶内容但不弹出，成功返回真，否则返回假boolisEmpty(;//若栈已空返回真boolisFull

4、();//若栈已满返回真};栈的实现方式顺序栈（Array-basedStack）使用向量实现，本质上是顺序表的简化版栈的大小关键是确定哪一端作为栈顶链式栈（LinkedStack）用单链表方式存储，其中指针的方向是从栈顶向下链接顺序栈templateclassarrStack:publicStack{private://栈的顺序存储intmSize;//栈中最多可存放的元素个数inttop;//栈顶位置，应小于mSizeT*st;//存放栈元素的数组public://栈的运算的顺序实现arrStack(int

5、size){//创建一个给定长度的顺序栈实例mSize=size;top=-1;st=newT[mSize];}arrStack(){//创建一个顺序栈的实例top=-1;}~arrStack(){//析构函数delete[]st;}voidclear(){//清空栈内容top=-1;}}顺序栈按压入先后次序，最后压入的元素编号为4，然后依次为3，2，1123top栈底4push(st,‘A’);Apush(st,‘B’);Bpush(st,‘C’);Cpop(st);pop(st);pop(st);顺序栈示意顺序栈示意012345

6、s.top=-1s.top=0A0B1C2D3E4F5s.top=5A012345A0B1C2D345s.top=3顺序栈的溢出上溢（Overflow）当栈中已经有maxsize个元素时，如果再做进栈运算，所产生的现象下溢（Underflow）对空栈进行出栈运算时所产生的现象顺序栈若入栈的顺序为1,2,3,4的话，则出栈的顺序可以有哪些?12341243132413421423143221342143……压栈操作boolarrStack::push(constTitem){if(top==mSize-1){//栈已满cout<

7、<"栈满溢出"<::pop(T&item){//出栈的顺序实现if(top==-1){//栈为空cout<<"栈为空，不能执行出栈操作"<::top(T&item){//返回栈顶内容，但不弹出if

8、(top==-1){//栈空cout<<"栈为空，不能读取栈顶元素"<::clear()