快捷導(dǎo)航

循環(huán)隊(duì)列詳解及隊(duì)列的順序表示和實(shí)現(xiàn)

更新時(shí)間：2016年12月27日 09:43:11 投稿：lqh

這篇文章主要介紹了循環(huán)隊(duì)列詳解及隊(duì)列的順序表示和實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下

循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)

前面分析順序隊(duì)的時(shí)候,我們知道,順序隊(duì)存在”假溢出”的問題,這個(gè)問題有時(shí)會造成很大的內(nèi)存浪費(fèi),循環(huán)隊(duì)列就是為了解決這個(gè)問題而提出地一個(gè)很巧妙的辦法.循環(huán)隊(duì)列和順序隊(duì)列的主要區(qū)別在于:循環(huán)隊(duì)列將順序隊(duì)列臆造成一個(gè)環(huán)狀空間.在操作上這種異同體現(xiàn)在:

相同點(diǎn):

在順序隊(duì)列和循環(huán)隊(duì)列中,進(jìn)行出隊(duì)、入隊(duì)操作時(shí),隊(duì)首、隊(duì)尾指針都要加 1 ,朝前移動。

不同點(diǎn):

1. 在循環(huán)隊(duì)列中當(dāng)隊(duì)首、隊(duì)尾指針指向向量上界(MAX_QUEUE_SIZE-1) 時(shí),其加1 操作的結(jié)果是指向向量的下界 0 。而在順序隊(duì)列中,說明隊(duì)已滿,若此時(shí)采用的是動態(tài)順序鏈,可以增加申請內(nèi)存.若是采用靜態(tài)順序鏈,只能退出程序.

2. 順序隊(duì)列中q.front = q.rear 表示隊(duì)空,q.rear = MAX_QUEUE_SIZE表示隊(duì)滿.而在循環(huán)隊(duì)列中.front=q.rear表示隊(duì)空,而無法用.rear=MAX_QUEUE_SIZE表示隊(duì)滿.

判斷循環(huán)隊(duì)列隊(duì)滿的兩種方法(本文采用第二種方法):

1.另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)列是空還是滿

2.少用一個(gè)元素空間,約定以”隊(duì)列頭指針在隊(duì)列尾指針的下一位置上”,作為隊(duì)列呈滿狀態(tài)的標(biāo)志.

第二種方法的實(shí)現(xiàn):

◆ rear 所指的單元始終為空。
◆ 循環(huán)隊(duì)列為空: front=rear 。
◆ 循環(huán)隊(duì)列滿: (rear+1)%MAX_QUEUE_SIZE=front 。

循環(huán)隊(duì)列操作及指針變化情況如下圖所示:

循環(huán)隊(duì)列雖然可以解決”假溢出”問題,但是它不能通過動態(tài)分配的一維數(shù)組來實(shí)現(xiàn),所以在實(shí)現(xiàn)循環(huán)隊(duì)列之前,一定要為它設(shè)定一個(gè)最大隊(duì)列長度.如果無法預(yù)估所需的最大隊(duì)列長度,只能采用來鏈表實(shí)現(xiàn).

代碼實(shí)現(xiàn):

循環(huán)隊(duì)列和順序隊(duì)列的頭文件是一樣的

/* 循環(huán)隊(duì)列的接口定義頭文件 */
#define true 1
#define false 0


/* 隊(duì)的最大長度 */
#define MAX_QUEUE_SIZE 6
/* 隊(duì)列的數(shù)據(jù)類型 */
typedef int datatype;

/* 靜態(tài)鏈的數(shù)據(jù)結(jié)構(gòu) */
typedef struct queue{
  datatype sp_queue_array[MAX_QUEUE_SIZE];
  /* 隊(duì)頭 */
  int front;
  /* 隊(duì)尾 */
  int rear;
}cir_queue;


/* 靜態(tài)順序鏈的接口定義 */


/* 靜態(tài)鏈的初始化 */
cir_queue queue_init();

/* 判斷隊(duì)列是否為空,若為空
 * 返回true
 * 否則返回false
*/
int queue_empty(cir_queue q);


/* 插入元素e為隊(duì)q的隊(duì)尾新元素 
 * 插入成功返回true
 * 隊(duì)滿返回false
*/
int queue_en(cir_queue *q, datatype e);


/* 隊(duì)頭元素出隊(duì)
 * 用e返回出隊(duì)元素,并返回true
 * 若隊(duì)空返回false
*/
int queue_de(cir_queue *q, datatype *e);

/* 清空隊(duì) */
void queue_clear(cir_queue *q);


/* 獲得隊(duì)頭元素
 * 隊(duì)列非空,用e返回隊(duì)頭元素,并返回true
 * 否則返回false
*/
int get_front(cir_queue, datatype *e );


/* 獲得隊(duì)長 */
int queue_len(cir_queue q);

/* 遍歷隊(duì) */
void queue_traverse(cir_queue q, void(*visit)(cir_queue q));


void visit(cir_queue s);


/* 循環(huán)隊(duì)列的接口實(shí)現(xiàn)文件 */
#include<stdio.h>
#include<stdlib.h>
#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)
{
  /* 判斷隊(duì)是否已滿 */
  if (q -> front == (q -> rear + 1) % MAX_QUEUE_SIZE)
    return false;
  /* 入隊(duì) */
  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)
{
  /* 判斷隊(duì)列是否為空 */
  if(q -> front == q -> rear)
    return false;
  /* 用e返回隊(duì)頭元素 */

  *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)
{
  /* 判斷隊(duì)列是否為空 */
  if (q.front == q.rear)
    return false;
  *e = q.sp_queue_array[q.front];
  return true;
}

int queue_len(cir_queue q)
{
  /* 若front > rear */
  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("此時(shí)隊(duì)長:length=%d\n", queue_len(q));
  queue_traverse(q, visit);
  printf("元素6再入隊(duì)\n");
  queue_en(&q, 6);
  queue_traverse(q, visit);
  datatype *x = (datatype *)malloc(sizeof(*x));
  queue_de(&q,x);
  printf("出隊(duì):%d,此時(shí)隊(duì)長=%d\n", *x, queue_len(q));
  printf("元素6再入隊(duì)\n");
  queue_en(&q, 6);
  printf("length=%d\n", queue_len(q));
  queue_traverse(q,visit);
  datatype *e = (datatype *)malloc(sizeof(*e));
  queue_de(&q,e);
  printf("queue_de(),e=%d length=%d\n", *e,  queue_len(q));
  queue_traverse(q, visit);
  queue_clear(&q);
  queue_traverse(q, visit);
  printf("length:%d\n", queue_len(q));
}

運(yùn)行截圖: