数据结构3栈和队列

数据结构3栈和队列第三章第三章第三章第三章第三章第三章第三章第三章栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列 3.1 3.1 栈栈 3.2 3.2 栈与递归栈与递归 3.3 3.3 队列队列 3.4 3.4 优先队列优先队列 3.5 3.5 双端队列双端队列栈的定义及基本运算：栈的定义及基本运算：栈栈(Stack)(Stack)...

第三章第三章第三章第三章第三章第三章第三章第三章栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列栈和队列 3.1 3.1 栈栈 3.2 3.2 栈与递归栈与递归 3.3 3.3 队列队列 3.4 3.4 优先队列优先队列 3.5 3.5 双端队列双端队列栈的定义及基本运算：栈的定义及基本运算：栈栈(Stack)(Stack)是是限制限制在表的一端进行插入和在表的一端进行插入和删除运算的删除运算的线性表线性表。通常称插入、删除。通常称插入、删除的这一端为栈顶的这一端为栈顶 (Top)(Top)，，另一端为栈底另一端为栈底 (Bottom)(Bottom)。。当表中没有元素时称为空栈。当表中没有元素时称为空栈。假设栈假设栈S=(aS=(a11，，aa22，，aa33，，……aann))，则，则aa11称为栈称为栈底底元素，元素，aann为为栈栈顶元素。栈中元素按顶元素。栈中元素按aa11，， aa22，，aa33，，……aann的次序进栈，退栈的第一个的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，改是按后进先出的原则进行的。因此，栈称为栈称为后进先出表（后进先出表（LIFOLIFO））。。栈栈stackstackstackstackstackstackstackstack �� 后进先出后进先出(LIFO):(LIFO):(LIFO):(LIFO):(LIFO):(LIFO):(LIFO):(LIFO):后进后进(Last In),(Last In),(Last In),(Last In),(Last In),(Last In),(Last In),(Last In),先出先出(First Out).(First Out).(First Out).(First Out).(First Out).(First Out).(First Out).(First Out). �� 栈：限定仅在一端进行插入和删除操作的线性栈：限定仅在一端进行插入和删除操作的线性表表((((((((栈是一种运算受限的线性表栈是一种运算受限的线性表)))))))) �� 术语术语 �� 入栈入栈(push)(push)(push)(push)(push)(push)(push)(push)：：元素插入栈元素插入栈 �� 出栈出栈(pop)(pop)(pop)(pop)(pop)(pop)(pop)(pop)：：删除元素删除元素 �� 栈顶栈顶(top)(top)(top)(top)(top)(top)(top)(top)：：栈的可访问元素栈的可访问元素 �� 栈的实现：顺序栈栈的实现：顺序栈(array-based)(array-based)(array-based)(array-based)(array-based)(array-based)(array-based)(array-based) �� 链式栈链式栈(linked stack)(linked stack)(linked stack)(linked stack)(linked stack)(linked stack)(linked stack)(linked stack) 7 6 5 4 3 2 1 pushpushpushpushpoppoppoppop toptoptoptop toptoptoptop 例、一叠书或一叠盘子。例、一叠书或一叠盘子。 a a11 a a22 a a n-1n-1 a a nn …… 栈顶栈底 StackStackStackStackStackStackStackStack ADTADTADTADTADTADTADTADT // Stack // Stack // Stack // Stack // Stack // Stack // Stack // Stack abtractabtractabtractabtractabtractabtractabtractabtract class class class class class class class class template class Stack {template class Stack {template class Stack {template class Stack {template class Stack {template class Stack {template class Stack {template class Stack { public:public:public:public:public:public:public:public: // Reinitialize the stack// Reinitialize the stack// Reinitialize the stack// Reinitialize the stack// Reinitialize the stack// Reinitialize the stack// Reinitialize the stack// Reinitialize the stack virtual void clear() = 0; virtual void clear() = 0; virtual void clear() = 0; virtual void clear() = 0; virtual void clear() = 0; virtual void clear() = 0; virtual void clear() = 0; virtual void clear() = 0; // // // // // // // // 把元素压入栈顶把元素压入栈顶........ virtual void push(const T&) = 0; virtual void push(const T&) = 0; virtual void push(const T&) = 0; virtual void push(const T&) = 0; virtual void push(const T&) = 0; virtual void push(const T&) = 0; virtual void push(const T&) = 0; virtual void push(const T&) = 0; // // // // // // // // 把元素从栈顶取出把元素从栈顶取出........ virtual T pop() = 0; virtual T pop() = 0; virtual T pop() = 0; virtual T pop() = 0; virtual T pop() = 0; virtual T pop() = 0; virtual T pop() = 0; virtual T pop() = 0; // // // // // // // // 返回栈顶元素的值。返回栈顶元素的值。 virtual T virtual T virtual T virtual T virtual T virtual T virtual T virtual T GetTopGetTopGetTopGetTopGetTopGetTopGetTopGetTop() const = 0;() const = 0;() const = 0;() const = 0;() const = 0;() const = 0;() const = 0;() const = 0; ////////////////把栈置空把栈置空 virtual void virtual void virtual void virtual void virtual void virtual void virtual void virtual void MakeEmptyMakeEmptyMakeEmptyMakeEmptyMakeEmptyMakeEmptyMakeEmptyMakeEmpty() = 0;() = 0;() = 0;() = 0;() = 0;() = 0;() = 0;() = 0; virtual virtual virtual virtual virtual virtual virtual virtual intintintintintintintint isEmptyisEmptyisEmptyisEmptyisEmptyisEmptyisEmptyisEmpty（）（） virtual virtual virtual virtual virtual virtual virtual virtual intintintintintintintint isFullisFullisFullisFullisFullisFullisFullisFull（）（）=0=0=0=0=0=0=0=0 };};};};};};};}; 顺序栈顺序栈由于栈是运算受限的线性表，因此由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量的，故需用一个整型变量 toptop 顺序栈顺序栈 �� 顺序栈的实现即顺序表实现的简化。顺序栈的实现即顺序表实现的简化。顺序栈的实现即顺序表实现的简化。顺序栈的实现即顺序表实现的简化。顺序栈的实现即顺序表实现的简化。顺序栈的实现即顺序表实现的简化。顺序栈的实现即顺序表实现的简化。顺序栈的实现即顺序表实现的简化。 �� 关键关键关键关键关键关键关键关键：：：：：：：：确定用数组的哪一端作为栈顶？确定用数组的哪一端作为栈顶？确定用数组的哪一端作为栈顶？确定用数组的哪一端作为栈顶？确定用数组的哪一端作为栈顶？确定用数组的哪一端作为栈顶？确定用数组的哪一端作为栈顶？确定用数组的哪一端作为栈顶？ �� 1.1.1.1.1.1.1.1.当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第00000000个位置作为栈顶时：个位置作为栈顶时：个位置作为栈顶时：个位置作为栈顶时：个位置作为栈顶时：个位置作为栈顶时：个位置作为栈顶时：个位置作为栈顶时：所有操作需在第所有操作需在第所有操作需在第所有操作需在第所有操作需在第所有操作需在第所有操作需在第所有操作需在第00000000个位置进行，则个位置进行，则个位置进行，则个位置进行，则个位置进行，则个位置进行，则个位置进行，则个位置进行，则pushpushpushpushpushpushpushpush操作和操作和操作和操作和操作和操作和操作和操作和 poppoppoppoppoppoppoppop操作都需把当前栈中的所有元素移动一个位操作都需把当前栈中的所有元素移动一个位操作都需把当前栈中的所有元素移动一个位操作都需把当前栈中的所有元素移动一个位操作都需把当前栈中的所有元素移动一个位操作都需把当前栈中的所有元素移动一个位操作都需把当前栈中的所有元素移动一个位操作都需把当前栈中的所有元素移动一个位置，则时间代价为：置，则时间代价为：置，则时间代价为：置，则时间代价为：置，则时间代价为：置，则时间代价为：置，则时间代价为：置，则时间代价为： O(nO(nO(nO(nO(nO(nO(nO(n))))))))。。。。。。。。 2.2.2.2.2.2.2.2.当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第当用数组的第iiiiiiii位置作为栈顶时：位置作为栈顶时：位置作为栈顶时：位置作为栈顶时：位置作为栈顶时：位置作为栈顶时：位置作为栈顶时：位置作为栈顶时：所有操作只是在线性表尾进行，则所有操作只是在线性表尾进行，则所有操作只是在线性表尾进行，则所有操作只是在线性表尾进行，则所有操作只是在线性表尾进行，则所有操作只是在线性表尾进行，则所有操作只是在线性表尾进行，则所有操作只是在线性表尾进行，则pushpushpushpushpushpushpushpush操作和操作和操作和操作和操作和操作和操作和操作和 poppoppoppoppoppoppoppop操作的时间代价仅为操作的时间代价仅为操作的时间代价仅为操作的时间代价仅为操作的时间代价仅为操作的时间代价仅为操作的时间代价仅为操作的时间代价仅为O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1) 上溢：上溢：上溢：上溢：当栈满时再做进栈运算必定产生空间溢出当栈满时再做进栈运算必定产生空间溢出当栈满时再做进栈运算必定产生空间溢出当栈满时再做进栈运算必定产生空间溢出下溢：下溢：下溢：下溢：当栈空时再做退栈运算也将产生溢出当栈空时再做退栈运算也将产生溢出当栈空时再做退栈运算也将产生溢出当栈空时再做退栈运算也将产生溢出说明：说明：说明：说明：上溢是一种出错状态，应该设法避免之；下溢则可能是上溢是一种出错状态，应该设法避免之；下溢则可能是上溢是一种出错状态，应该设法避免之；下溢则可能是上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，正常现象，因为栈在程序中使用时，其初态或终态都是空栈，正常现象，因为栈在程序中使用时，其初态或终态都是空栈，正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。所以下溢常常用来作为程序控制转移的条件。所以下溢常常用来作为程序控制转移的条件。所以下溢常常用来作为程序控制转移的条件。 templatetemplatetemplatetemplate < < < > > > classclassclassclass AStackAStackAStackAStack: : : : publicpublicpublicpublic StackStackStackStack<<<>>> {{{{ privateprivateprivateprivate:::: intintintint MaxSizeMaxSizeMaxSizeMaxSize; ; ; ; // // // // 栈中最大元素个数 intintintint toptoptoptop; ; ; ; // // // // 栈中实际元素个数 TTTT ****elementselementselementselements; ; ; ; // // // // 存储栈元素的数组 publicpublicpublicpublic:::: AStackAStackAStackAStack((((intintintint szszszsz = = = =DefaultListSizeDefaultListSizeDefaultListSizeDefaultListSize) // ) // ) // ) // ConstructorConstructorConstructorConstructor { { { { sizesizesizesize = = = = szszszsz; ; ; ; toptoptoptop = 0; = 0; = 0; = 0; elementselementselementselements = = = = newnewnewnew TTTT[[[[szszszsz]; }]; }]; }]; } ~ ~ ~ ~AStackAStackAStackAStack() { () { () { () { deletedeletedeletedelete [] [] [] [] elementselementselementselements; } // ; } // ; } // ; } // DestructorDestructorDestructorDestructor voidvoidvoidvoid clearclearclearclear() { () { () { () { toptoptoptop = 0; } = 0; } = 0; } = 0; } 顺序栈顺序栈注意：这里toptoptoptop在第IIII个位置一些重要的条件一些重要的条件 �� 栈满：栈满：top==maxSize-1top==maxSize-1；； �� 栈空：栈空：top==-1top==-1 链式栈链式栈 �栈的链式存储结构称为链栈，它是运算受栈的链式存储结构称为链栈，它是运算受栈的链式存储结构称为链栈，它是运算受栈的链式存储结构称为链栈，它是运算受限的单链表，先插入和删除操作仅限制在限的单链表，先插入和删除操作仅限制在限的单链表，先插入和删除操作仅限制在限的单链表，先插入和删除操作仅限制在表头位置上进行表头位置上进行表头位置上进行表头位置上进行....由于只能在链表头部进行由于只能在链表头部进行由于只能在链表头部进行由于只能在链表头部进行操作，故链表没有必要像单链表操作，故链表没有必要像单链表操作，故链表没有必要像单链表操作，故链表没有必要像单链表那样附加那样附加那样附加那样附加头结点头结点头结点头结点。栈顶指针就是链表的头指针。栈顶指针就是链表的头指针。栈顶指针就是链表的头指针。栈顶指针就是链表的头指针 �栈的所有操作只是在头结点进行，所以其栈的所有操作只是在头结点进行，所以其栈的所有操作只是在头结点进行，所以其栈的所有操作只是在头结点进行，所以其时间代价为时间代价为时间代价为时间代价为OOOO(1).(1).(1).(1). �定义：书pppp106106106106 顺序栈与链式栈的比较顺序栈与链式栈的比较 �� 时间上：时间上：时间上：时间上：时间上：时间上：时间上：时间上：顺序栈为顺序栈为顺序栈为顺序栈为顺序栈为顺序栈为顺序栈为顺序栈为O(1),O(1),O(1),O(1),O(1),O(1),O(1),O(1),链式栈为链式栈为链式栈为链式栈为链式栈为链式栈为链式栈为链式栈为O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1) �� 空间上：空间上：空间上：空间上：空间上：空间上：空间上：空间上：顺序栈顺序栈顺序栈顺序栈顺序栈顺序栈顺序栈顺序栈要一个固定的长度，当栈不够要一个固定的长度，当栈不够要一个固定的长度，当栈不够要一个固定的长度，当栈不够要一个固定的长度，当栈不够要一个固定的长度，当栈不够要一个固定的长度，当栈不够要一个固定的长度，当栈不够满时，空间浪费；满时，空间浪费；满时，空间浪费；满时，空间浪费；满时，空间浪费；满时，空间浪费；满时，空间浪费；满时，空间浪费；链式栈链式栈链式栈链式栈链式栈链式栈链式栈链式栈长度可变，但对于每长度可变，但对于每长度可变，但对于每长度可变，但对于每长度可变，但对于每长度可变，但对于每长度可变，但对于每长度可变，但对于每个元素需要一个链接域，产生结构性开销。个元素需要一个链接域，产生结构性开销。个元素需要一个链接域，产生结构性开销。个元素需要一个链接域，产生结构性开销。个元素需要一个链接域，产生结构性开销。个元素需要一个链接域，产生结构性开销。个元素需要一个链接域，产生结构性开销。个元素需要一个链接域，产生结构性开销。 �� 何时使用顺序栈？何时使用顺序栈？何时使用顺序栈？何时使用顺序栈？何时使用顺序栈？何时使用顺序栈？何时使用顺序栈？何时使用顺序栈？ �� 当要实现多个栈时，可用一个数组存储两个当要实现多个栈时，可用一个数组存储两个当要实现多个栈时，可用一个数组存储两个当要实现多个栈时，可用一个数组存储两个当要实现多个栈时，可用一个数组存储两个当要实现多个栈时，可用一个数组存储两个当要实现多个栈时，可用一个数组存储两个当要实现多个栈时，可用一个数组存储两个栈，且最好是一个栈增长时另一个栈缩短。栈，且最好是一个栈增长时另一个栈缩短。栈，且最好是一个栈增长时另一个栈缩短。栈，且最好是一个栈增长时另一个栈缩短。栈，且最好是一个栈增长时另一个栈缩短。栈，且最好是一个栈增长时另一个栈缩短。栈，且最好是一个栈增长时另一个栈缩短。栈，且最好是一个栈增长时另一个栈缩短。 top1top1top1top1 top2top2top2top2 4.2 4.2 栈的应用举例栈的应用举例由于栈结构具有的后进先出的固有特性，由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。是几个栈应用的例子。 4.2.1 4.2.1 数制转换数制转换十进制十进制NN和其它进制数的转换是计算机和其它进制数的转换是计算机实现计算的基本问题实现计算的基本问题 ,,其解决方法很多其解决方法很多 ,,其中其中一个简单算法基于下列原理一个简单算法基于下列原理 :: N=(n div d) N=(n div d)**d+n mod dd+n mod d ( ( 其中其中:div:div为整除运算为整除运算 ,mod,mod为求余运算为求余运算)) 例如例如 ((1348)1348)1010=(2504)=(2504)88，，其运算过程如下：其运算过程如下： n n div 8 n mod 8n n div 8 n mod 8 1348 168 4 1348 168 4 168 21 0 168 21 0 21 2 5 21 2 5 2 0 2 2 0 2 void conversion( void conversion( intint n ) { n ) { Stack< Stack s;> s; while(nwhile(n){ s.push(n%8);){ s.push(n%8); n=n/8; } n=n/8; } while(! while(! s.isEmptys.isEmpty()){()){ s.pop(es.pop(e);); coutcout<

                    本文档为【数据结构3栈和队列】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构3栈和队列

你可能还喜欢