循环队列详解及队列的顺序表示和实现

循环队列——队列的顺序表示和实现

前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成一个环状空间.在操作上这种异同体现在:

相同点:

在顺序队列和循环队列中,进行出队、入队操作时,队首、队尾指针都要加 1 ,朝前移动。

不同点:

1. 在循环队列中当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结果是指向向量的下界 0 。而在顺序队列中,说明队已满,若此时采用的是动态顺序链,可以增加申请内存.若是采用静态顺序链,只能退出程序.

2. 顺序队列中q.front = q.rear 表示队空,q.rear = MAX_QUEUE_SIZE表示队满.而在循环队列中.front=q.rear表示队空,而无法用.rear=MAX_QUEUE_SIZE表示队满.

判断循环队列队满的两种方法(本文采用第二种方法):

1.另设一个标志位以区分队列是空还是满

2.少用一个元素空间,约定以”队列头指针在队列尾指针的下一位置上”,作为队列呈满状态的标志.

第二种方法的实现:

◆ rear 所指的单元始终为空。
◆ 循环队列为空: front=rear 。
◆ 循环队列满: (rear+1)%MAX_QUEUE_SIZE=front 。

循环队列操作及指针变化情况如下图所示:

循环队列虽然可以解决”假溢出”问题,但是它不能通过动态分配的一维数组来实现,所以在实现循环队列之前,一定要为它设定一个最大队列长度.如果无法预估所需的最大队列长度,只能采用来链表实现.

代码实现:

循环队列和顺序队列的头文件是一样的

#define true 1
#define false 0



#define MAX_QUEUE_SIZE 6

typedef int datatype;


typedef struct queue{
  datatype sp_queue_array[MAX_QUEUE_SIZE];
  
  int front;
  
  int rear;
}cir_queue;






cir_queue queue_init();


int queue_empty(cir_queue q);



int queue_en(cir_queue *q, datatype e);



int queue_de(cir_queue *q, datatype *e);


void queue_clear(cir_queue *q);



int get_front(cir_queue, datatype *e );



int queue_len(cir_queue q);


void queue_traverse(cir_queue q, void(*visit)(cir_queue q));


void visit(cir_queue s);



#include
#include
#include"cir_queue.h"

cir_queue queue_init()
{
  cir_queue q;
  q.front = q. rear = 0;
  return q;
}


int queue_empty(cir_queue q)
{
  return q.front == q.rear;
}

int queue_en(cir_queue *q, datatype e)
{
  
  if (q -> front == (q -> rear + 1) % MAX_QUEUE_SIZE)
    return false;
  
  q -> sp_queue_array[q -> rear] = e;
  q -> rear = (q -> rear + 1) % MAX_QUEUE_SIZE;
  return true;
}

int queue_de(cir_queue *q, datatype *e)
{
  
  if(q -> front == q -> rear)
    return false;
  

  *e = q -> sp_queue_array[q -> front];
  q -> front = (q -> front + 1 ) % MAX_QUEUE_SIZE;
  return true;
}


void queue_clear(cir_queue *q)
{
  q -> front = q -> rear = 0;
}

int get_front(cir_queue q, datatype *e)
{
  
  if (q.front == q.rear)
    return false;
  *e = q.sp_queue_array[q.front];
  return true;
}

int queue_len(cir_queue q)
{
  
  if(q.front > q.rear)
    return (q.rear + MAX_QUEUE_SIZE - q.front);
  else
    return (q.rear - q.front);
}


void queue_traverse(cir_queue q, void(*visit)(cir_queue q))
{
  visit(q);
}


void visit(cir_queue q)
{
  while(q.front != q.rear)
  {
    printf("%d ",q.sp_queue_array[q.front]);
    q.front = (q.front + 1) % MAX_QUEUE_SIZE;
  }
}


int main()
{
   cir_queue q = queue_init();
  queue_en(&q, 1);
  queue_en(&q, 2);
  queue_en(&q, 3);
  queue_en(&q, 4);
  queue_en(&q, 5);
  printf("此时队长:length=%dn", queue_len(q));
  queue_traverse(q, visit);
  printf("元素6再入队n");
  queue_en(&q, 6);
  queue_traverse(q, visit);
  datatype *x = (datatype *)malloc(sizeof(*x));
  queue_de(&q,x);
  printf("出队:%d,此时队长=%dn", *x, queue_len(q));
  printf("元素6再入队n");
  queue_en(&q, 6);
  printf("length=%dn", queue_len(q));
  queue_traverse(q,visit);
  datatype *e = (datatype *)malloc(sizeof(*e));
  queue_de(&q,e);
  printf("queue_de(),e=%d length=%dn", *e,  queue_len(q));
  queue_traverse(q, visit);
  queue_clear(&q);
  queue_traverse(q, visit);
  printf("length:%dn", queue_len(q));
}

运行截图:

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！