理解顺序队列和循环队列的差别

最编程 2024-01-31 16:09:15

...

一、队列的概念

只能在表的一端进行插入操作，只能在表的另一端进行删除操作，这种数据结构称为队列。把允许插入的一端叫队尾(rear)，允许删除的一端叫对头(front)。

二、队列的分类

采用链式存储结构实现的队列称为链队列。

三、顺序队列

顺序队列的表示

①顺序队列用一个向量空间（一般使用一维数组）来存放当前队列中的元素。
②由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。

2、顺序队列的基本操作
①入队时：将新元素插入rear所指的位置，然后将rear加1。
②出队时：删去front所指的元素，然后将front加1并返回被删元素。

注意：
　 ①当头尾指针相等时，队列为空。

顺序队列中的溢出现象

① "下溢"现象
　当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
② "真上溢"现象
　当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
③ "假上溢"现象
由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

四、循环队列

为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。

1、循环队列的基本操作
　循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：
① 方法一：
if(i+1==QueueSize) //i表示front或rear
i=0;
else
i++;

② 方法二--利用"模运算"
i=(i+1)%QueueSize；

2、循环队列边界条件处理
　循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
　解决这个问题的方法至少有三种：
① 另设一布尔变量以区别队列的空和满；
② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
③使用一个计数器记录队列中元素的总数（即队列长度）。

3、程序

DataType   
   int   
  
 
 
MAXSIZE   
     
  100 
 
 
 
 
  
 
 

   using namespace std; 
 
 
 
 
  
 
 
struct   
  _CirQueue  
  
 
 

   { 
 
 
 

 
 
front; //头指针，队非空时指向队头元素 
 
 
 
rear; //尾指针，队非空时指向队尾元素的下一位置 
 
 
 

   }CirQueue, *pCirQueue; 
 
 
 
 
  
 
 
 InitQueue(pCirQueue   
  
 
 
   
  Empty(pCirQueue   
  pQueue); 
 
 
 

   bool InsertQueue(pCirQueue pQueue, DataType x); 
 
 
 

   DataType OutQueue(pCirQueue pQueue); 
 
 
 
   
  GetHead(pCirQueue   
  pQueue); 
 
 
 
GetLength(pCirQueue   
  
 
 
 
  
 
 

   int _tmain(int argc, _TCHAR* argv[]) 
 
 
 

   { 
 
 
 
len = 0, data; 
 
 
 
myQueue; 
 
 
 

   InitQueue(&myQueue); 
 
 
 

   if (!Empty(&myQueue)) 
 
 
 

   { 
 
 
 

   printf("Queue is Empty"); 
 
 
 

   } 
 
 
 

   InsertQueue(&myQueue, 1); 
 
 
 

   InsertQueue(&myQueue, 2); 
 
 
 

   InsertQueue(&myQueue, 3); 
 
 
 

   InsertQueue(&myQueue, 4); 
 
 
 

   len = GetLength(&myQueue); 
 
 
 

   data = GetHead(&myQueue); 
 
 
 

   while (Empty(&myQueue)) 
 
 
 

   { 
 
 
 

   data = OutQueue(&myQueue); 
 
 
 

   cout<<endl<<data; 
 
 
 

   } 
 
 
 

   return 0; 
 
 
 

   } 
 
 
 
 
  
 
 

   //初始化：初始化一个新的队列 
 
 
 
 InitQueue(pCirQueue   
  
 
 

   { 
 
 
 

   memset(pQueue, 0, sizeof(CirQueue)); 
 
 
 

   } 
 
 
 
 
  
 
 

   //队列非空判断：若队列不为空，则返回true；否则返回false。 
 
 
 
   
  Empty(pCirQueue   
  pQueue) 
 
 
 

   { 
 
 
 

   if (pQueue->front != pQueue->rear) 
 
 
 

   { 
 
 
 

   return true; 
 
 
 

   } 
 
 
 

   else return false; 
 
 
 

   } 
 
 
 
 
  
 
 

   //入队列：在队列的尾部插入元素x，使元素x成为新的队尾。若 队列满，则返回false；否则，返回true。 
 
 
 

   bool InsertQueue(pCirQueue pQueue, DataType x) 
 
 
 

   { 
 
 
 
//判断队列是否已满 
 
 
 

   { 
 
 
 

   pQueue->data[pQueue->rear] = x; 
 
 
 

   pQueue->rear = (pQueue->rear + 1)%MAXSIZE; 
 
 
 

   return true; 
 
 
 

   } 
 
 
 

   else 
 
 
 
false; 
 
 
 

   } 
 
 
 
 
  
 
 

   //出队列：若队列不为空，则返回对头元素，并从对头删除该元素，对头指针指向原对头的后记元素；否则，返回元素NULL 
 
 
 

   DataType OutQueue(pCirQueue pQueue) 
 
 
 

   { 
 
 
 

 
 

   if (pQueue->front == pQueue->rear) 
 
 
 

   { 
 
 
 

   return NULL; 
 
 
 

   } 
 
 
 

   else 
 
 
 

   { 
 
 
 

   data = pQueue->data[pQueue->front]; 
 
 
 

   pQueue->front = (pQueue->front + 1)%MAXSIZE; 
 
 
 

   return data; 
 
 
 

   } 
 
 
 

   } 
 
 
 
 
  
 
 

   //取对头元素：若队列不空，则返回对头元素；否则，返回空元素NULL 
 
 
 
   
  GetHead(pCirQueue   
  pQueue) 
 
 
 

   { 
 
 
 

   if (pQueue->front == pQueue->rear) 
 
 
 

   { 
 
 
 
NULL; 
 
 
 

   } 
 
 
 

   else 
 
 
 

   { 
 
 
 
pQueue->data[pQueue->front]; 
 
 
 

   } 
 
 
 

   } 
 
 
 
 
  
 
 

   //求队列长度 
 
 
 
GetLength(pCirQueue   
  
 
 

   { 
 
 
 
length = 0, number = 0; 
 
 
 

   for (number = pQueue->front; number%MAXSIZE < pQueue->rear; number = (number+1)%MAXSIZE) 
 
 
 

   { 
 
 
 

   length++; 
 
 
 

   } 
 
 
 

   return length; 
 
 
 

   }

运行结果：

上一篇：循环队列（顺序队列）

下一篇：玩转数据结构：环形队列的奥秘

理解顺序队列和循环队列的差别

循环队列的数据结构 C 语言实现（详细）[易于理解］

简单模拟 Java 中循环队列的实现和队列接口的引入

循环队列的 java 实现 - 基于顺序存储结构

循环队列（顺序队列）的 JAVA 实现

深入理解如何用哈希表和优先队列实现求前K个元素的解题方法 - Java实战刷题指南

C++编程：实战教程 - 实现栈与队列(Deque) 容器适配器，探讨Stack和Queue的实现及Queueue（Deque）的问题。深入理解：如何模拟实现Priority Queue (优先级队列) - 实例与解题，以及仿射函数入门（第一部分）

玩转数据结构：探索顺序队列、循环队列和链队列的奥秘

全面解析顺序队列、循环队列和链式队列