队列及其实现.

Presentation on theme: "队列及其实现."— Presentation transcript:

1 队列及其实现

2 定义 特性 队列 ( Queue ) 队列是只允许在一端删除，在另一端插入的顺序表
允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out)

3 template <class Type> class Queue { public:
队列的抽象数据类型 template <class Type> class Queue { public: Queue ( int=10 ); //构造函数 void EnQueue ( const Type & item); //进队 Type DeQueue ( ); //出队列 Type GetFront ( ); //取队头元素值 void MakeEmpty ( ); //置空队列 int IsEmpty ( ) const ; //判队列空否 int IsFull ( ) const; //判队列满否 }

4 #include <assert.h> template <class Type> class Queue {
队列的数组表示  循环队列的类定义 #include <assert.h> template <class Type> class Queue { public: Queue ( int=10 ); ~Queue ( ) { delete [ ] elements; } void EnQueue ( const Type & item); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) { front = rear = 0; }

5 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; }

6 队列的进队和出队 进队时队尾指针先进一 rear = rear + 1，再将 新元素按 rear 指示位置加入。
出队时队头指针先进一 front = front + 1，再 将下标为 front 的元素取出。 队满时再进队将溢出出错；队空时再出队将 队空处理。

7 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。
循环队列 (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

8 循环队列的进队和出队

9 循环队列部分成员函数的实现 template <class Type> Queue<Type>::
Queue ( int sz ) : front (0), rear (0), maxSize (sz) { elements = new Type[maxSize]; assert ( elements != 0 ); } template <class Type> void Queue<Type>:: EnQueue ( const Type & item ) { assert ( !IsFull ( ) ); rear = (rear+1) % MaxSize; elements[rear] = item;

10 template <class Type>
Type Queue<Type>::DeQueue ( ) { assert ( !IsEmpty ( ) ); front = ( front+1) % MaxSize; return elements[front]; } Type Queue<Type>::GetFront ( ) {

11 链式队列在进队时无队满问题，但有队空问题。 队空条件为 front == NULL
队列的链接表示 — 链式队列 队头在链头，队尾在链尾。 链式队列在进队时无队满问题，但有队空问题。 队空条件为 front == NULL

12 链式队列类的定义 template <class Type> class Queue;
template <class Type> class QueueNode { friend class Queue<Type>; private: Type data; //队列结点数据 QueueNode<Type> *link; //结点链指针 QueueNode ( Type d=0, QueueNode *l=NULL ) : data (d), link (l) { } };

13 template <class Type> class Queue {
public: Queue ( ) : rear ( NULL ), front ( NULL ) { } ~Queue ( ); void EnQueue ( const Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ); //实现与~Queue( )同 int IsEmpty ( ) const { return front == NULL; } private: QueueNode<Type> *front, *rear; //队列指针 };

14 链式队列成员函数的实现 template <class Type>
Queue<Type>::~Queue ( ) { //队列的析构函数 QueueNode<Type> *p; while ( front != NULL ) { //逐个结点释放 p = front; front = front→link; delete p; }

15 template <class Type> void Queue<Type>:: EnQueue ( const Type & item ) {
if ( front == NULL ) //空, 创建第一个结点 front = rear = new QueueNode <Type> ( item, NULL ); else //队列不空, 插入 rear = rear→link = new QueueNode }

16 template <class Type> Type
Queue<Type>::DeQueue ( ) { //删去队头结点，并返回队头元素的值 assert ( !IsEmpty ( ) ); //判队空的断言 QueueNode<Type> *p = front; Type retvalue = p→data; //保存队头的值 front = front→link; //新队头 delete p; return retvalue; }

17 template <class Type>
Type Queue<Type>::GetFront ( ) { //若队不空，则函数返回队头元素的值; 若 //队空，则函数返回0。 assert ( !IsEmpty ( ) ); return front→data; }

18 队列的应用举例 — 逐行打印二项展开式 (a + b)i 的系数 杨辉三角形 (Pascal’s triangle)

19 分析第 i 行元素与第 i+1行元素的关系 目的是从前一行的数据可以计算下一行的数据

20 从第 i 行数据计算并存放第 i+1 行数据

21 利用队列打印二项展开式系数的程序 #include <stdio.h> #include <iostream.h>
#include "queue.h" void YANGVI ( int n ) { Queue q; //队列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1); int s = 0;

22 for ( int i=1; i<=n; i++ ) { //逐行计算
cout << endl; q.EnQueue (0); for ( int j=1; j<=i+2; j++ ) { //下一行 int t = q.DeQueue ( ); q.EnQueue ( s+t ); s = t; if ( j != i+2 ) cout << s << ' '; }

23 优先级队列 (Priority Queue)
优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素 例如下表：任务的优先权及执行顺序的关系 数字越小，优先权越高

24 优先队列的类定义 #include <assert.h> #include <iostream.h>
$include <stdlib.h> const int maxPQSize = 50; //缺省元素个数 template <class Type> class PQueue { public: PQueue ( ); ~PQueue ( ) { delete [ ] pqelements; } void PQInsert ( const Type & item ); Type PQRemove ( );

25 void makeEmpty ( ) { count = 0; }
int IsEmpty ( ) const { return count == 0; } int IsFull ( ) const { return count == maxPQSize; } int Length ( ) const { return count; } private: Type *pqelements; //存放数组 int count; //队列元素计数 }

26 优先队列部分成员函数的实现 template <class Type>
PQueue<Type>::PQueue ( ) : count (0) { pqelements = new Type[maxPQSize]; assert ( pqelements != 0 ); //分配断言 } template <class Type> void PQueue<Type> :: PQInsert ( const Type & item ) { assert ( !IsFull ( ) ); //判队满断言 pqelements[count] = item; count ++；

27 template <class Type>
Type PQueue<Type>::PQRemove ( ) { assert ( !IsEmpty ( ) ); //判队空断言 Type min = pqelements[0]; int minindex = 0; for ( int i=1; i<count; i++ ) //寻找最小元素 if ( pqelements[i] < min ) //存于min { min = pqelements[i]; minindex = i; } pqelements[minindex] = pqelements[count-1]; count-- ; //删除 return min; }