第4章+栈、队列和递归试卷.pptx

数据结构—C++实现;第4章　栈、队列和递归;第4章 栈、队列和递归;栈（stack）是限定仅在表尾一端进行插入或删除操作的特殊线性表。 对于栈来说, 允许进行插入或删除操作的一端称为栈顶（top）,而另一端称为栈底（bottom）。 不含元素栈称为空栈; 向栈中插入一个新元素称为入栈或压栈; 从栈中删除一个元素称为出栈或退栈。 栈又称为后进先出（Last In First Out，LIFO）的线性表。 ;图4.1 栈的结构示意图 ;栈的实例;栈 结 构 示 例;1、初始化 2、求长度 3、取栈顶元素 4、入栈 5、出栈 6、判断栈是否为空栈 7、清空栈 ;1、栈的顺序存储 2、栈的链式存储 3、栈的两种存储结构的比较;图4-2　 栈的顺序存储结构及其操作过程;templateclass ElemType class SeqStack { protected: int top; // 栈顶指针 int maxSize; // 栈最大容量 ElemType *elems;// 元素存储空间 ;顺序栈的栈底在数组的底端，S-elems[0]表示栈底元素； S-top=-1 表示栈空； S-top=MAXSIZE-1 表示栈满； 入栈时，首先将S-top加1，用以指示新的栈顶位置，再把元素放到这个位置上。 出栈时，首先取出栈顶元素，再将S-top减1，使栈顶指针指示新的栈顶元素。 栈满时入栈会“上溢出”，栈空时出栈会“下溢出”。;public: SeqStack(int size = DEFAULT_SIZE); virtual ~SeqStack(); int GetLength() const; bool IsEmpty() const; void Clear(); Status Push(const ElemType e); Status Top(ElemType e) const; Status Pop(ElemType e); …… }; ;templateclass ElemType SeqStackElemType::SeqStack(int size) // 操作结果：构造一个最大容量为size的空栈 { maxSize = size; if (elems != NULL) delete []elems; elems = new ElemType[maxSize]; top = -1; } ;templateclass ElemType SeqStackElemType::~SeqStack() // 操作结果：销毁栈 { delete []elems; } ;template class ElemType int SeqStackElemType::GetLength() const // 操作结果：返回栈中元素个数 { return top+1; } ;templateclass ElemType bool SeqStackElemType::IsEmpty() const // 操作结果：如栈为空，则返回true，否则返回false { return top == -1; } ;templateclass ElemType void SeqStackElemType::Clear() { top = -1; } ;templateclass ElemType Status SeqStackElemType::Push(const ElemType e) { if (top == maxSize - 1) // 栈已满 return OVER_FLOW; else { elems[++top] = e; // 将元素e追加到栈顶 return SUCCESS; // 操作成功 } };templateclass ElemType Status SeqStackElemType::Top(ElemType e) const { if (IsEmpty()) // 栈空 return UNDER_FLOW; else { e = elems[top]; // 用e返回栈顶元素 return SUCCESS; // 栈非空,操作成功 } };templateclass ElemType Status SeqStackElemType::Pop(ElemType e) { if (IsEmpty()) // 栈空 return UNDER_FLOW; else { e = elems[top--];