第四章栈和队列 栈和队列都是操作受限的线性表,应用十分广泛。 4.1栈( Stack) 定乂:栈是限制插入和删除操作只能在某一端进行的线性表,并按 先进后出(FILO)或后进先出(LIFO)的原则进行操作 进栈(Push) 出栈(Pop) 栈顶top ee 入栈顺序 2 eo e1 e2 en-2 en-1 出栈顺序: e 栈底 en-1 en-2 e2 e1 eo e 栈可以对序列实现求逆 2021222
2021/2/22 1 第四章 栈和队列 栈和队列都是操作受限的线性表，应用十分广泛。 4.1 栈（Stack） 定义：栈是限制插入和删除操作只能在某一端进行的线性表，并按 先进后出（F I L O )或后进先出（ＬIＦＯ）的原则进行操作 入栈顺序： e0 e1 e2 … en-2 en-1 出栈顺序： en-1 en-2 … e2 e1 e0 栈可以对序列实现求逆 en-1 e0 e1 en-2 … 进栈（Push） 出栈（Pop） 栈顶 top 栈底
栈的基本操作:(参见P104) (1)栈初始化 Stack(int=10)/构造函数 (2)进栈Push void Push( const Type item (3)出栈Pop Type Pop(; (4)判栈空 IsEmpty int IsEmpty(i return top=-1 (5)读取栈顶元素 GetTop Type GetTop(); (6)置空栈 Make Empty void MakeEmpty(i top=-1; 1 7)判栈满 IsFull int IsFullo const{ return top= maxSize;} 栈的封闭性及其抽象数据类型 在一个栈中,出入囗处称为栈顶,栈内最深处称为栈底。除 了栈顶元素外,其他元素不会被改变,因而栈的封闭性非常好, 使用起来非常安全。另外,在下面的栈的类定义中,体现了栈的 抽象数据类型,在此定乂中,所有栈的成员函数都是共有的,其 他类的成员函数都可以使用这些函数,但是,栈的存储表示和成 员函数的实现对其他类的成员来说都是隐蔽的。 2021222
2021/2/22 2 栈的基本操作： （参见P104） （1）栈初始化 Stack ( int = 10 );//构造函数 （2）进栈 Push void Push( const Type & item ); （3）出栈 Pop Type Pop( ); （4）判栈空 IsEmpty int IsEmpty( ) { return top==-1;} （5）读取栈顶元素 GetTop Type GetTop ( ); （6）置空栈MakeEmpty void MakeEmpty( ) { top=-1;} （7）判栈满IsFull int IsFull( ) const { return top==maxSize;} 栈的封闭性及其抽象数据类型： 在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除 了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好， 使用起来非常安全。另外，在下面的栈的类定义中，体现了栈的 抽象数据类型，在此定义中，所有栈的成员函数都是共有的，其 他类的成员函数都可以使用这些函数，但是，栈的存储表示和成 员函数的实现对其他类的成员来说都是隐蔽的
41.1顺序栈一一在顺序存储结构上实现的栈 include assert.h> C++断言功能 template class Stack∥顺序栈的类定义 i public Stack(int=10);/栈初始化,建立一个空栈,缺省大小为10 Stack(i delete []elements; j void push( const Type&item),∥将数据元素tem入栈 Type Pop( 将栈顶元素出栈 Type GetTopo 读渎取栈顶元素 void MakeEmpty(){top=1;}/置空栈,top=1表示栈为空 int IsEmpty (const( return top==-1 /y栈空 int isful() const{ return top= -maxSize-li}/判栈满 private /top= maxSize-1表示栈已满 Int top;栈顶指针(栈顶元素下标) Type* elements;/储顺序栈的数组 int maxSize;顺序栈的最大容量 2021222
2021/2/22 3 4.1.1 顺序栈－－在顺序存储结构上实现的栈 # include //C＋＋断言功能 template class Stack //顺序栈的类定义 { public: Stack ( int=10 );//栈初始化，建立一个空栈，缺省大小为10 ~Stack ( ) { delete [ ] elements ; } void Push ( const Type & item ); //将数据元素item 入栈 Type Pop ( ) ; //将栈顶元素出栈 Type GetTop ( ) ; //读取栈顶元素 void MakeEmpty ( ) { top=-1;} //置空栈，top=-1表示栈为空 int IsEmpty ( ) const { return top==-1;} //判栈空 int IsFull ( ) const { return top==maxSize-1;} //判栈满 private: //top=maxSize-1表示栈已满 int top;//栈顶指针（栈顶元素下标） Type * elements;//存储顺序栈的数组 int maxSize;//顺序栈的最大容量 }
顺序栈的基本操作(算法) (1)顺序栈初始化算法(构造函数) template Stack. Stack(int s) top(-1), maxSize(s) 健立一个最大尺寸为s的空栈,若分配不成功则错误处理 element- new Type[ manSize;创建顺序栈空间(数组) assert(elements! =0) //言语句:若条件成立,则继续;否则出错处理并终止执行 (2)顺序栈入栈算法 template void Stack Push(const Type item) 若栈不满,则将元素item插入到栈顶,否则出锆处理 aser(! IsFull()/.言:栈不满则继续执行 elements[++topl=item;/栈顶指针先加1,然后按此地址进栈 2021222
2021/2/22 4 顺序栈的基本操作（算法） （1）顺序栈初始化算法（构造函数） template Stack::Stack(int s):top(-1),maxSize(s) //建立一个最大尺寸为s 的空栈，若分配不成功则错误处理 { element=new Type[maxSize];//创建顺序栈空间（数组） assert( elements != 0); //断言语句：若条件成立，则继续；否则出错处理并终止执行 } （2）顺序栈入栈算法 template void Stack::Push(const Type & item) //若栈不满，则将元素item 插入到栈顶，否则出错处理 { assert( ! IsFull());//断言：栈不满则继续执行 elements[++top]=item;//栈顶指针先加1 ，然后按此地址进栈 }
(3)顺序栈出栈算法 template Type Stack PopO 若栈不空,则返回栈顶元素,并使栈顶指针退1;否则岀锆处理 assr(! IsEmptyo;/.言:若栈不空,则继续执行 return elements[top-];/返回栈顶元素,并使栈顶指针退1 (4)读取顺序栈栈顶元素算法 Template Type Stack GetTopO 若栈不空,则返回栈顶元素;否则出锆处理 assert(! IsEmptyo;/.言:若栈不空,则继续执行 return elements[top];/返回栈顶元素,注意:栈顶指针不变 2021222
2021/2/22 5 （3）顺序栈出栈算法 template Type Stack::Pop() //若栈不空，则返回栈顶元素，并使栈顶指针退 1 ；否则出错处理 { assert( ! IsEmpty());//断言：若栈不空，则继续执行 return elements[top--];//返回栈顶元素，并使栈顶指针退1 } （4）读取顺序栈栈顶元素算法 Template Type Stack::GetTop() //若栈不空，则返回栈顶元素；否则出错处理 { assert( ! IsEmpty());//断言：若栈不空，则继续执行 return elements[top];//返回栈顶元素，注意：栈顶指针不变 }
41.3链栈—利用链式存贮结构实现的栈 与顺序表一样,顺序栈的最大尺寸( maxSize)也难以确定,大 小了容易溢出,太大了又浪费空间。因此在动态性较强的应用领域, 宜采用链栈。 链栈的结构如下图所示。与单链表相似,但不设头结点,第 个结点即为栈顶。插入(入栈)与删除(出栈)操作均只能在表头 进 栈顶元素 栈底元素 p 当top=NULL时,表示空栈 2021222
2021/2/22 6 4.1.3 链栈——利用链式存贮结构实现的栈 与顺序表一样，顺序栈的最大尺寸（maxSize）也难以确定，太 小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域， 宜采用链栈。 链栈的结构如下图所示。与单链表相似，但不设头结点，第一 个结点即为栈顶。插入（入栈）与删除（出栈）操作均只能在表头 进行。 当 top = NULL 时，表示空栈 … ^ top 栈顶元素 栈底元素
链栈的定义: 链栈结点类的定义 template class stack;∥链栈类的前视声明 template class Stack Node friend class Stack * link StackNode(Type d=0. Stack Node*1-NULL) data(d)link(){}∥构造函数,初始化一链栈结点 2021222
2021/2/22 7 链栈的定义： 链栈结点类的定义： template class Stack; //链栈类的前视声明 template class StackNode { friend class Stack ; private: Type data; StackNode * link; StackNode(Type d=0,StackNode * l=NULL): data(d),link(l) { } //构造函数，初始化一链栈结点 } data link 链栈结点结构
链栈类的定义: template class Stack i publ Stack()top(NULL){}∥构造函数,初始化一个空链栈 Stack() ∥析构函数,释放链栈的所有结点,并使top=NULL。置栈空操作 void Push(const Type item) ∥栈操作 Type Popo //栈操作 Type Get Top( ∥读取栈顶元素 void Make Empty(( top=NULL, /置栈空操作,应先删除栈内所有结点 int IsEmpty() const{ return top=NULL;}∥)判栈空操作 int IsFull( const return 0) /判栈满,在链栈中该操作无意义 privat StackNode* top ∥栈顶指针 2021222
2021/2/22 8 链栈类的定义： template class Stack { public: Stack( ) : top(NULL) { } //构造函数，初始化一个空链栈 ~Stack( ); //析构函数，释放链栈的所有结点，并使top=NULL。置栈空操作 void Push(const Type & item); //入栈操作 Type Pop( ); //出栈操作 Type GetTop( ); //读取栈顶元素 void MakeEmpty( ) { top=NULL;} //置栈空操作，应先删除栈内所有结点 int IsEmpty( ) const {return top == NULL;} //判栈空操作 int IsFull ( ) const {return 0} //判栈满，在链栈中该操作无意义 private: StackNode * top; //栈顶指针 }
链栈的入栈算法: Template void Stack. Push(const Type item) 将数据元素item入栈 top=new StackNode(item, top) /创建一个新的链栈结点,并将该结点的data域置为item, link域置为top,最后将该结点的指针赋值给top.参见下图 Pp 原栈顶 ∧ (2) Item 新栈顶 2021222
2021/2/22 9 链栈的入栈算法： Template void Stack :: Push(const Type & item) //将数据元素item 入栈 { top=new StackNode(item,top); //创建一个新的链栈结点，并将该结点的data 域置为item ， //link 域置为top ,最后将该结点的指针赋值给top .参见下图 } … ^ top 原栈顶 新栈顶 item (1) (2)
比较与思考: (1)比较顺序栈与链栈的类定义 两者的类名相同,均为 Stack 两者成员函数的名、参数、返回类型与规格说明均相同,但 内部的实现有别 假定某大型软件系统原来使用顺序栈,因经常上溢,欲改用链 栈,请问哪些部分需要改动? 2021222
2021/2/22 10 比较与思考： （1）比较顺序栈与链栈的类定义 两者的类名相同，均为Stack 两者成员函数的名、参数、返回类型与规格说明均相同，但 内部的实现有别 假定某大型软件系统原来使用顺序栈，因经常上溢，欲改用链 栈，请问哪些部分需要改动？