[工学]第九章堆栈与队列.ppt

第二节 队列 链式队列的队头指针指向队列当前队头结点； 队尾指针指向队列的当前队尾结点 1．链式队列存储结构 五、链式队列 链式存储结构的队列称为链式队列 链式队列不带头结点更为简便，如上图 第二节 队列 2、链式队列类的定义和实现 template class T class LinQueue; template class T class QueueNode { friend class LinQueue T; private: QueueNodeT *next; T data; public: QueueNode(const T item,QueueNode T *ptrNext=NULL) { data=item; next=ptrNext; } ~QueueNode(){}; }; 第二节 队列 template class T class LinQueue { private: QueueNode T *front; QueueNode T *rear; int count; public: LinQueue(void); ~LinQueue(void); void Append(const T item); T Delete(void); T GetFront(void) const; int NotEmpty(void) const { return count!=0; } }; 第二节 队列 template class T LinQueue T::LinQueue() { front=rear=NULL; count=0; } template class T LinQueueT::~LinQueue(void) { QueueNodeT *p,*q; p=front; while(p!=NULL) { q=p; p=p-next; delete q; } count =0; front=rear=NULL; } 第二节 队列 template class T void LinQueueT::Append(const T item) //入队 { QueueNode T *newNode=new QueueNodeT(item,NULL); if(rear!=NULL) rear-next=newNode; rear=newNode; if(front==NULL) front=newNode; count++; } templateclass T T LinQueueT::GetFront(void)const { if(count==0) { cout队列已空！endl; exit(0); } return front-data; } 第二节 队列 template class T T LinQueueT::Delete(void) //出队 { if(count==0) { cout队列已空！endl; exit(0); } QueueNodeT *p=front-next ; T data=front-data; delete front; front=p; count--; return data; } * 第九章 栈与队列 第一节 栈 1．栈的基本概念 2．栈抽象数据类型 3 ．顺序栈类及应用 4 ．链式栈类 5 ．栈的应用 第二节 队列 1．队列的基本概念 2．队列的抽象数据类型 3．顺序队列 4、顺序循环队列类的定义和实现 5 、链式队列 6 、优先级队列 第一节 栈 第一节 栈 1． 栈的基本概念 2． 栈抽象数据类型 3 ．顺序栈类及应用 4 ．链式栈类 5 ．栈的应用 a 一．栈的基本概念 第一节 栈 堆栈的数据元素及元素之间的逻辑关系和线性表完全相同 堆栈：只允许在固定一端进行插入和删除操作的一种特殊线性表 栈顶：栈中允许进行插入和删除操作的一端称为栈顶，另一端称栈底 栈顶 栈底 退栈 进栈 栈顶的当前位置是动态的，标识栈顶当前位置的变量称为栈顶指针 堆栈的插入和删除操作通常称为进栈或入栈； 堆栈的删除操作通常称为出栈或退栈。 第一节 栈 每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原