数组实现循环队列

63 阅读 0 评论 42 点赞

我是靠谱客的博主健忘烤鸡，最近开发中收集的这篇文章主要介绍数组实现循环队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、为了有效的处理队列，我们需要两个指针，一个用于指向队首元素所在的位置（front），一个用于指示队尾待插入的位置(rear)。

2、将数组想象成一个循环的圆形以此克服对空间的无效利用。

3、边界条件判断

由于在循环数组中，入队时队尾追赶队首，出队时队首追赶队尾，当队空或队满时都有front == rear, 故无法用此作为判定标准

解决办法：

（1）留空位。当队列还有一个空位时就认为队列已满

（2）标记。引进一个新的变量，可以是bool型，当队尾正好在队头前面时，指示队列已满；或者用一个整形变量来计算队列中元素的个数

（3）将一个或两个指针设置成某个不会出现的值来指示空或满状态，如当队空时将front设置成-1

下面介绍第一种方法：

队空时： front == rear

队满时：(rear + 1) % maxSize == front

代码：

enum ErrorCode

{
    success,

    underflow,

    overflow

};

const int maxQueue = 100;
 
template <class QueueEntry>
class MyQueue
{

public:

         MyQueue()
         {
         	front = rear = 0;
		 }

 

         // 判断队列是否为空
         bool empty() const
         {
         	return front == rear;
		 }

         // 入队操作
         ErrorCode append(const QueueEntry &item)
         {
         	if(full())
         		return overflow;
         	else{
					entry[rear] = item;
					rear = (rear + 1) % maxQueue;     			
				}
         		
         		return success;			 
		 }

         // 出队操作
         ErrorCode serve()
         {
         	if(empty())
         		return underflow;
         	else{
         		front = (front + 1) % maxQueue;
         			
         		return success;
			}
		 }

         // 获取队头元素
         ErrorCode retrieve(QueueEntry &item) const
         {
         	if(empty())
         		return underflow;
         	else{
         		item = entry[front];
         		return success;
			}
		 }

         // 判断队列是否已满
         bool full() const
         {
         	return (rear + 1) % maxQueue == front;
		 }

         // 获取队列已有元素个数
         int size() const
         {
         	MyQueue temp = *this;
         	
         	int count = 0;
         	
         	while(!temp.empty()){
         		temp.front = (temp.front + 1) % maxQueue;
         		
         		count++;
			}
			
			return count;
		 }

         // 清除队列所有元素

         void clear()
         {
         	while(!empty())
         		front = (front + 1) % maxQueue;
			
		 }

         // 获取队头元素并出队

         ErrorCode retrieve_and_serve(QueueEntry &item)      
         {
         	if(empty())
			 	return underflow;
			else{
				item = entry[front];
				
         		front = (front + 1) % maxQueue;
         			
         		return success;
			}  		
		 }

 

private:

         // 请不要修改数据成员.


         int front;                             // 队头下标

         int rear;                              // 队尾下标

         QueueEntry entry[100];       // 队列容器

};