数据结构、算法与应用-C++描述6.ppt

Chapter6 队列(Queues) The Abstract Data Type Formula-Based Representation Linked Representation Applications 本章重点 队列的实现 队列的应用 队列(Queues) 定义 是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾(rear)，而删除元素的那一端被称为队首(front)。 队列是一个先进先出（ first-in-first-out, FIFO）的线性表。 队列 队列 公式化描述 公式6-1 location (i)=i-1 性质 front:0 rear:最后一个元素的位置 空队列:rear=-1 公式化描述 公式6-2 location(i)=location(1)+ i-1 性质 front:location(1) rear:location(最后一个元素) 空队列:rearfront 插入操作 location(i)=location(1)+ i-1 公式化描述 公式6-3 location(i)=(location(1)+i-1)% Maxsize 性质 front:指向队列首元素的下一个位置(逆时针方向) rear:队列尾 空队列:front = rear 队列满? 队列满? 循环队列的进队和出队 公式化类Queue templateclass T class Queue { // FIFO 对象 public: Queue(int MaxQueueSize = 10); ~Queue() {delete [] queue;} bool IsEmpty() const {return front == rear;} bool IsFull() const {return ( ((rear + 1) % MaxSize == front) ? 1 : 0);} T First() const; //返回队首元素 T Last() const; // 返回队尾元素 QueueT Add(const T x); QueueT Delete(T x); 公式化类Queue private: int front; //与第一个元素在反时针方向上相差一个位置 int rear; // 指向最后一个元素 int MaxSize; // 队列数组的大小 T *queue; // 数组 } ; 构造函数 templateclass T QueueT::Queue(int MaxQueueSize) {// 创建一个容量为MaxQueueSize的空队列 MaxSize = MaxQueueSize + 1; queue = new T[MaxSize]; front = rear = 0; } 公式化类Queue templateclass T T QueueT::First() const {// 返回队列的第一个元素 // 如果队列为空，则引发异常OutOfBounds if (IsEmpty()) throw OutOfBounds(); return queue[(front + 1) % MaxSize]; } 公式化类Queue templateclass T T QueueT::Last() const {// 返回队列的最后一个元素 // 如果队列为空，则引发异常OutOfBounds if (IsEmpty()) throw OutOfBounds(); return queue[rear]; } 公式化类Queue templateclass T QueueT QueueT::Add(const T x) {// 把x 添加到队列的尾部 // 如果队列满，则引发异常NoMem if (IsFull()) throw NoMem(); rear = (rear + 1) % MaxSize; queue[rear] = x; return *this; } 公式化类Queue templateclass T QueueT QueueT::Delete(T x) {// 删除第一个元素，并将其送入x // 如果队列为空，则引发异常OutOfBounds if (IsEmpty()) throw OutOfBounds(); front = (front + 1) % MaxSize; x = queue[front]; return *this; } 链表描述 可以使用单向链表来实现一个队列。 思考：链表中使用几个指针？ 链表描述 需要两个变量front和rear来分别跟踪队列的两端。。 链表描述的两种方式 思考：性能相同吗？ 链表插