数据结构-用面向对象语言描述-殷人昆-第三章课件.ppt

第三章 栈与队列 数据结构电子教案 第三章 栈与队列 栈 队列 栈 ( Stack ) 只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO --Last In First Out) 栈的抽象数据类型 栈的数组存储表示 — 顺序栈 顺序栈的操作 template class T void SeqStackT::overflowProcess() { //私有函数：当栈满则执行扩充栈存储空间处理 T *newArray = new T[2*maxSize]; //创建更大的存储数组 for (int i = 0; i = top; i++) newArray[i] = elements[i]; maxSize += maxSize; delete [ ]elements; elements = newArray; //改变elements指针 } template class T bool SeqStackT::Push(const T x) { //若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull() == true) overflowProcess(); //栈满 elements[++top] = x; //栈顶指针先加1, 再进栈 return true; //进栈成功 } template class T bool SeqStackT::Pop(T x) { //函数退出栈顶元素并返回栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top--]; //栈顶指针退1 return true; //退栈成功 } template class T bool SeqstackT::getTop(T x) const{ //若栈不空则函数返回该栈栈顶元素 if (IsEmpty() == true) return false; x = elements[top]; return true; } template class E // 构造函数 SeqStackE::SeqStack(int sz) : top(-1) , maxSize(sz) { elements = new E[maxSize]; } 队列 ( Queue ) 定义 队列是只允许在一端删除，在另一端插入的线性表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out) 队列的抽象数据类型 队列的进队和出队原则 进队时先将新元素按 rear 指示位置加入，再将队尾指针加一 rear = rear + 1。 队尾指针指示实际队尾的后一位置。 出队时按队头指针指示位置取出元素，再将队头指针进一 front = front + 1， 队头指针指示实际队头位置。 队满时再进队将溢出出错（假溢出） ； 解决假溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列。 循环队列 (Circular Queue) 队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: front = (front+1) % maxSize; 队尾指针进1: rear = (rear+1) % maxSize; 队列初始化：front = rear = 0; 队空条件：front == rear; 队满条件：(rear+1) % maxSize == front 循环队列操作的定义 void MakeEmpty() { front = rear = 0; } bool IsEmpty() const { return front == rear; } bool IsFull() const { return (rear+1) % maxSize == front; } template class T SeqQueueE::SeqQueue(int sz) : front(0), rear(0), maxSize(sz) { //构造函数 elements = new T[maxSize]; assert ( e