【精品数据结构】特殊线性表─栈、队、串.PPTVIP

§3.1 栈 (一)基本概念 栈是一种限定仅在表的一端进行插入与删除的线性表 允许进行插入与删除的这一端称为栈顶，而另一端称为栈底 不含元素的空表称为空栈 插入与删除分别称进栈与出栈。 栈也称作先进后出（First In Last Out）的线性表，简称FILO表 (一)基本概念 栈应用的例子 火车扳道站 进入单车道死胡同的汽车 记录中断返回地址（断点）的结构 (一)基本概念 可能的出栈次序 设n=3，按1,2，3的次序进栈，则可能的出栈次序为 1 2 3、1 3 2、2 1 3、2 3 1、3 2 1 不可能的次序是： 3 1 2 对任意元素k，若它后面有小于它的元素，则这些小于它的元素必须以“逆序”出现 (二) 基本操作 Init(s)：初始化栈s。设定一个空栈，栈的所有其它操作仅在此操作执行（或隐含执行）之后才能进行。 Empty(s)：判定函数。若栈s为空，返回“真”，否则返回“假”。 Push(s,x)：入栈函数。将元素x放到栈顶上，栈溢出时应返回特殊标志。 Pop(S)：出栈函数。栈s不空时，将栈顶元素摘除，并返回该元素。否则触发异常。 GetTop(s)：读栈顶元素函数。与Pop(s)类似，但不摘取栈顶元素。 Clear(s)：清除操作。使栈s重新变为一个空栈。这里，s是个已存在的栈。 Len(s)：求长度函数。返回栈s中元素个数。 (三) 基本操作使用示例 编写一个带编辑功能的从终端上接收字符的程序 若依次输入： 　　　　Cg#HIna##NA 则相当于输入CHINA 若依次输入 　　　　chi@CHINA 则相当于输入CHINA … … Init(s); ch = getch(); //读入一个字符 while (ch!=EOF) //当未读入结束符时，一直循环 { switch(ch) { case # : Pop(s); break; case @ : Clear(s); break; default: Push(s, ch); } ch = getch(); } (四)栈抽象类 template class TElem class TStack0 { protected: long len; public: long GetLen (void) {return len; }; char IsEmpty ( ) {return (len=0)? 1:0; }; virtual TElem Push (TElem elem) =0; virtual TElem Pop (void) =0; virtual TElem GetTop (void) =0; (四)栈抽象类 virtual TElem RollDown ( ) =0; virtual TElem RollUp ( ) =0; virtual void Clear ( ) =0; ? } (一) 存贮方法 栈是一种特殊的线性表，本节先介绍顺序存贮方式 用一维数组模拟连续的存贮空间 用一个量指示插入/删除端的位置，一般称该量为栈顶指针 (二) 顺序栈类 template class TElem class TStackSqu : public TStack0TElem { protected: TElem *room; TElem elemBuff; long size; ? long CopyRoom (TElem *objRoom, long n1, TElem *srcRoom, long n2); long ResizeRoom (long newSize); (二) 顺序栈类 public: TStackSqu (); TStackSqu (long mSize); ~TStackSqu (); ? virtual TElem Push (TElem elem); virtual TElem Pop (void); virtual TElem GetTop (void); ? virtual TElem RollDown ( ); virtual TElem RollUp ( ); virtual void Clear ( ); ? virtual void Print ( ); ?} (三) 基本操作的实现 template class TElem TStackSquTElem::TStackSqu ( ) { room=NUL