静态循环队列的相关操作及详解

循环队列

队列通常分为两类：一是动态链式队列(其核心思想为链表，只是少了链表的一些功能)，二是静态(顺序)队列(其核心是用数组实现，准确一点讲是由向量空间来实现，向量空间好比是开辟的一块内存，由我们的指针来指向其地址)。顺序队列实际上是运算受限的顺序表，由于队列的队头和队尾的位置是变化的，通常设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。这种“假上溢”现象常常造成内存资源的浪费，这时就产生了循环队列(首尾相接)。循环队列克服“假上溢”现象的方法是：将向量空间想象成一个首尾相连的圆环，将循环队列存放在其中。循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。针对这样情况，有两种解决方法：一是少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空），；二是使用一个计数器记录队列中元素的总数（即队列长度）。我们通常使用第一种方法，也就是少用一个元素的空间。

循环队列相关操作思路

1.初始化：造数组，设其数组长度为n=5(规定当数组中有n-1个元素时已满)，初始化队头队尾值都为0；

2.入队

先判断队列是否已满：（队尾+1）%数组长度==队头是否成立？即队尾和队头紧挨着；

为队尾的下一个元素赋值；

让队尾加1；

3.出队

先判断队列是否为空：若队首和队尾相等，则该队列一定为空（但队首和队尾值不一定为0，这个由初始化、入队、出队等相关操作后的数组下标位置决定）

保存一份要出队的值；

让队头加1；

实例说明

?<SPAN style="FONT-SIZE: 14px">#include<stdio.h> 
#include<malloc.h>  
#include<stdlib.h>  
typedef struct Queue 
{ 
    int *pBase;//pBase指向数组名（通常静态队列都使用循环队列）  
    int front;//数组下标，这里规定从零开始  
    int rear; 
}QUEUE;//QUEUE代表了struct Queue  
void init(QUEUE *);//初始化  
bool en_queue(QUEUE *,int);//入队  
bool full_queue(QUEUE *);//判断循环队列是否已满  
bool del_queue(QUEUE *,int *);//出队  
bool empty_queue(QUEUE *);//判断循环队列是否为空  
bool traverse_queue(QUEUE *);//遍历输出  
int length(QUEUE *);//求循环队列的长度  
 
int main() 
{ 
    QUEUE Q; 
    int val; 
    init(&Q); 
    en_queue(&Q,1); 
    en_queue(&Q,2); 
    en_queue(&Q,3); 
    en_queue(&Q,4); 
    traverse_queue(&Q);       
    if(del_queue(&Q,&val)) 
        printf("出队成功，出队元素的值为：%d\n",val); 
    else 
        printf("出队失败！"); 
    traverse_queue(&Q);  
    printf("队列的长度为：%d\n",length(&Q)); 
     
    return 0; 
} 
void init(QUEUE *pQ) 
{ 
    pQ->pBase=(int *)malloc(sizeof(int)*5);//造数组，设其数组长度为n=5（规定当数组中有n-1个元素时已满），初始化时使Queue的成员front、rear的值都为0  
    if(NULL==pQ->pBase) 
    { 
        printf("动态内存分配失败！\n"); 
        exit(-1); 
    } 
    pQ->front=0; 
    pQ->rear=0; 
} 
bool full_queue(QUEUE *pQ) 
{ 
    if((pQ->rear+1)%5==pQ->front) 
        return true; 
    else 
        return false; 
} 
bool en_queue(QUEUE *pQ,int val) 
{ 
    if(full_queue(pQ)) 
    { 
        printf("队列已满，入队失败！\n"); 
        return false; 
    } 
    pQ->pBase[pQ->rear]=val; 
    pQ->rear=(pQ->rear+1)%5;//队尾加1  
    return true; 
} 
bool del_queue(QUEUE *pQ,int *pVal) 
{ 
    if(empty_queue(pQ)) 
        return false; 
    *pVal=pQ->pBase[pQ->front]; 
    pQ->front=(pQ->front+1)%5; 
    return true; 
} 
bool empty_queue(QUEUE *pQ) 
{ 
    if(pQ->rear==pQ->front)//因为队列不为空时，rear和front肯定不相等  
        return true; 
    else 
        return false; 
} 
bool traverse_queue(QUEUE *pQ) 
{ 
    int i=pQ->front; 
    if(empty_queue(pQ)) 
    { 
        printf("队列为空，遍历失败！\n"); 
        return false; 
    } 
    printf("队列元素有："); 
    while(i!=pQ->rear) 
    { 
        printf("%d  ",pQ->pBase[i]); 
        i=(i+1)%5;               
    } 
    printf("\n"); 
    return true; 
} 
int length(QUEUE *pQ) 
{ 
    int len=0; 
    int i=pQ->front;; 
    if(empty_queue(pQ)) 
        return 0;//队列为空，长度为0  
    while(i!=pQ->rear) 
    { 
        i=(i+1)%5; 
        ++len; 
    } 
    return len; 
}</SPAN> 

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Queue
{
 int *pBase;//pBase指向数组名（通常静态队列都使用循环队列）
 int front;//数组下标，这里规定从零开始
 int rear;
}QUEUE;//QUEUE代表了struct Queue
void init(QUEUE *);//初始化
bool en_queue(QUEUE *,int);//入队
bool full_queue(QUEUE *);//判断循环队列是否已满
bool del_queue(QUEUE *,int *);//出队
bool empty_queue(QUEUE *);//判断循环队列是否为空
bool traverse_queue(QUEUE *);//遍历输出
int length(QUEUE *);//求循环队列的长度

int main()
{
 QUEUE Q;
 int val;
 init(&Q);
 en_queue(&Q,1);
 en_queue(&Q,2);
 en_queue(&Q,3);
 en_queue(&Q,4);
    traverse_queue(&Q);     
    if(del_queue(&Q,&val))
  printf("出队成功，出队元素的值为：%d\n",val);
 else
  printf("出队失败！");
 traverse_queue(&Q);
    printf("队列的长度为：%d\n",length(&Q));
 
 return 0;
}
void init(QUEUE *pQ)
{
 pQ->pBase=(int *)malloc(sizeof(int)*5);//造数组，设其数组长度为n=5（规定当数组中有n-1个元素时已满），初始化时使Queue的成员front、rear的值都为0
 if(NULL==pQ->pBase)
 {
  printf("动态内存分配失败！\n");
  exit(-1);
 }
 pQ->front=0;
 pQ->rear=0;
}
bool full_queue(QUEUE *pQ)
{
 if((pQ->rear+1)%5==pQ->front)
  return true;
 else
  return false;
}
bool en_queue(QUEUE *pQ,int val)
{
 if(full_queue(pQ))
 {
  printf("队列已满，入队失败！\n");
  return false;
 }
    pQ->pBase[pQ->rear]=val;
 pQ->rear=(pQ->rear+1)%5;//队尾加1
 return true;
}
bool del_queue(QUEUE *pQ,int *pVal)
{
 if(empty_queue(pQ))
  return false;
    *pVal=pQ->pBase[pQ->front];
 pQ->front=(pQ->front+1)%5;
 return true;
}
bool empty_queue(QUEUE *pQ)
{
 if(pQ->rear==pQ->front)//因为队列不为空时，rear和front肯定不相等
  return true;
 else
  return false;
}
bool traverse_queue(QUEUE *pQ)
{
 int i=pQ->front;
 if(empty_queue(pQ))
 {
  printf("队列为空，遍历失败！\n");
  return false;
 }
 printf("队列元素有：");
 while(i!=pQ->rear)
 {
  printf("%d  ",pQ->pBase[i]);
  i=(i+1)%5;    
 }
 printf("\n");
 return true;
}
int length(QUEUE *pQ)
{
 int len=0;
 int i=pQ->front;;
 if(empty_queue(pQ))
        return 0;//队列为空，长度为0
 while(i!=pQ->rear)
 {
  i=(i+1)%5;
  ++len;
 }
 return len;
}

注意

1.指针只在入队和出队时移动，其它情况下不能移动。

2.队列初始化：front和rear的值都是零；

3.队列非空：front代表的是队列的第一个元

补充：软件开发 , C语言 ,