null队列1.队列
2.队列的应用举例－－打印二项展开式的系数队列1 .队列（queue）1 .队列（queue）1) 定义：插入在一端进行，删除在另一端进行的线性
表．又称先进先出（FIFO：First In First Out）
例： A0 A1 A2 … An-1
front(队头) rear(队尾)
2) 队列的抽象数据类型（队列的6种基本操作）
template
class Queue
{ public:
Queue (int =10); //构造
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
void EnQueue (const Type &item);
Type DeQueue ( ); //返回队头元素并删除
Type GetFront( ); //取队头元素
void MakeEmpty ( ); //置空队列
int IsEmpty( ) const; //若队空返回1,否则返回0
int IsFull( ) const; //若队满返回1,否则返回0
}null3) 循环队列－－队列的顺序存储表示(Circular Queue)
队列也有两种存储方式：顺序方式、链接方式。
顺序方式： front=rear时为空队列约定：front指向实际队头元素的前一个位置
rear 指向实际的队尾元素
∴rear - front = 队中元素的个数。
null
队列在插入、删除过程中会发生：
再插入时会发生溢出,假溢出
null环：把element数组看成是一个逻辑环，即：
队头指针进１：front = (front + 1) % maxsize
队尾指针进１：rear = (rear + 1) % maxsize
但这时有一个新问题：
这时如何区分队满与队空？
书中采用宁可浪费一个存储位置。也就是说队列中最多放maxsize-1个元素，即从0～maxsize-2．
(rear+1) % maxsize == front 一定是队满
front==rear 一定是队空
队中元素个数:(rear-front+maxsize)%maxsize
null下面是循环队列的类声明以及成员函数的声明：
#include
template class Queue
{ public:
Queue (int=10);
~Queue( ) {delete [] elements;}
void EnQueue( const Type &item);
Type DeQueue ( );
Type GetFront( );
void MakeEmpty ( ) {front=rear=0;}
int IsEmpty( ) const {return front==rear;}
int IsFull( ) const {return (rear+1) % maxsize==front;}
int Length( ) const {return (rear - front + maxsize) % maxsize;}
private:
int rear,front;
Type * elements;
int maxsize;
}
null循环队列插入与删除的实现：
插入操作（队尾）
template
void Queue ::EnQueue(const Type &item)
{ assert (!IsFull( )); //断言：队列不满继续放
rear= (rear+1) % maxsize;
element [rear]=item;
}null删除操作（队头）
template
Type Queue::DeQueue( )
{//返回队头元素并删除
assert (!IsEmpty( ));
front=(front+1) % maxsize;
return element[front];
}4) 链式队列4) 链式队列与链栈一样，链式队列由两个类来表示：结点类，链式类．
template class Queue;
template class QueueNode
{ friend class Queue ;
private:
Type data;
QueueNode *link;
QueueNode (Type d=0, QueueNode * l=NULL):
data(d),link(l){ }
};nulltemplate class Queue
{ public:
Queue( ):rear(NULL),front(NULL){}
~Queue( );
void EnQueue(const Type &item);
Type DeQueue( );
Type GetFront( );
void MakeEmpty( );
int IsEmpty( ) const {return front == NULL;}
private:
QueueNode *front,*rear;
};null插入：template
void Queue::EnQueue(const Type &item)
{ if (front==NULL)
front=rear=new QueueNode(item,NULL);
else rear=rear->link=new QueueNode(item,NULL);
}
删除：template
Type Queue::DeQueue( )
{ assert(!IsEmpty( ));
QueueNode *p=front;
Type retvalue=p->data;
front=front->link;
if (rear==p) rear=NULL;
delete p;
return retvalue;
}2. 队列的应用举例2. 队列的应用举例打印二项展开式(a+b) 的系数
(a+b)1 =a+b
(a+b)2 =a2 +2ab+b2
(a+b)3 =a3 +3a2 b+3ab2+b3
…
1 1 i=1
1 2 1 i=2
1 3 3 1 i=3
1 4 6 4 1 i=4
1 5 10 10 5 1 i=5 杨辉三角形
1 6 15 20 15 6 1 i=6
这个系数当i=1,2,...,n非常有规律，如果将每行两边加零，null 显然求i+1行的系数要利用已求得的i行的系数．
利用队列：111添加2q:01i=2001331生成i=3添加0s=0t=1s+t
s=ts+t
s=ts+t
s=ts+t
s=t0012每当取一个系数到t中，就把该元素在队中删除，同时还要输出（打印）1q:添加一个零s=0t=1t=1s=1s=1∴当由i行系数生成i+1行系数后，这i行系数已经打印输出，并且不在队列中了．11null具体算法：
#include
#include
#include “queue.h”
void YANGHUI(int n)
{ Queue q;
q.MakeEmpty ( );
q.EnQueue(1); q.EnQueue(1);
int s=0;
for(int i=1;i<=n;i++) //逐行处理，i=1,2,...,n
{ cout<
本文档为【数据结构：队列】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483