循环队列
如果按照顺序队列存储方法，经过多次出入队列，可能会造成“假溢出”和内存浪费。为了避免顺序队列造成的假溢出，通常用顺序循环队列来实现队列的顺序存储。
顺序循环队列表示：
1：表示顺序循环队列的两个参数：队头指针front和队尾指针rear
2：队列初始化时，front和rear值都为零；
3：当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置；
4：当队列为空时，front与rear的值相等，但不一定为零；
5：队列空与满的时候front 与 rear 都是一样的。为了区分队列空与队列满，
方法一：添加一个标志位：flag。入队成功是flag= 1，出队成功：flag = 0；则队空判断条件是：front == rear && flag == 0；队满标志：front == rear&& flag == 1；
方法二：少用一个存储单元：队空：front == rear；队满：front == （rear +1）%QueueSzie；







顺序循环队列的实现
1：SCQueue.h头文件
#ifndef _SCQUEUE_H
#define _SCQUEUE_H

typedef char DataType;

#define QueueSize 40		//队列的容量
typedef  struct Squeue{
	DataType queue[QueueSize];
	int front,rear;			//队头指针和队尾指针
}SeqQueue;		

void InitQueue(SeqQueue *SCQ);
int QueueEmpty(SeqQueue SCQ);
int EnterQueue(SeqQueue *SCQ,DataType e);
int DeleteQueue(SeqQueue *SCQ,DataType *e);
int GetHead(SeqQueue SCQ,DataType *e);
void ClearQueue(SeqQueue *SCQ);

#endif


2：SCQueue.c文件
#include "SCQueue.h"

//初始化操作
void InitQueue(SeqQueue *SCQ)
{
	SCQ->front = SCQ->rear = 0;				//把队头指针和队尾指针同设为0
}

//判断是否为空
int QueueEmpty(SeqQueue SCQ)
{
	if(SCQ.front == SCQ.rear)			
		return 1;
	else 
		return 0;
}

//入队操作，成功返回1，失败为0
int EnterQueue(SeqQueue *SCQ,DataType e)
{
	if(SCQ->front == (SCQ->rear + 1) % QueueSize)			//插入新元素前确定是否已满
		return 0;
	else
	{
		SCQ->queue[SCQ->rear] = e;								//在队尾插入元素e
		SCQ->rear = (SCQ->rear + 1) % QueueSize;				//队尾指针后移
			return 1;
	}
}

//出队操作,成功返回1，失败为0
int DeleteQueue(SeqQueue *SCQ,DataType *e)
{
	if(SCQ->front == SCQ->rear)				//删除之前，判断是否为空
		return 0;	
	else
	{
		*e = SCQ->queue[SCQ->front];
		SCQ->front = (SCQ->front + 1) % QueueSize;			//队头指针后移
			return 1;
	}
}
//用e返回队头元素
int GetHead(SeqQueue SCQ,DataType *e)
{
	if(SCQ.front == SCQ.rear)			//删除元素前检查队列是否已空
		return 0;
	else
	{
		*e = SCQ.queue[SCQ.front];		//用e返回队头元素
		return 1;
	}
}

//清空队列
void ClearQueue(SeqQueue *SCQ)
{
	SCQ->front = SCQ->rear = 0;
}


3：main.c文件
#include <stdio.h>
#include "SCQueue.h"

void main()
{
	SeqQueue Q;				//声明一个顺序队列Q
	char str[] = "ABCDEFG";
	int i,length = 7;
	DataType x;

	InitQueue(&Q);			//初始化顺序队列
	for(i=0; i<length; i++ )
	{
		EnterQueue(&Q,str[i]);
	}
	DeleteQueue(&Q,&x);				//将队头元素出队列
	printf("出队列的元素是:%c\n",x);
	printf("顺序队列的元素为：");
	if(!QueueEmpty(Q))				//判断顺序表是否为空
	{
		for(i=Q.front; i<Q.rear; i++)
			printf("%c",Q.queue[i]);		//输出队头指针到队尾指针的元素
	}
	printf("\n");
}

今天说说队列。
认识队列这东西很久了，但一直都没有用到。就知道是基本的数据结构。在百度和google和一段时间思考后，我选用了循环队列。

从百度可以得知：
将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。大概就像这幅图那样。



声明头和尾变量，如果是入队就尾+1，出队头+1。因为循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。通常我都会设个count变量，计算队列是空还是满。

循环队列关键就是对动态内存分配的认识。
常用结构如下：
typedef struct                                        //循环列表结构
{
    int *base;
    int front;
    int rear;
}SqQueue;

常用函数如下：
int count = 0;

//构造一个空队列
int initQueue(SqQueue *Q) {
	Q->base = (int *) malloc(MAXSIZE * sizeof(int));
	if (!Q->base) {
		MsgS("malloc wrong!\n");
		return -1;
	}
	Q->front = Q->rear = 0;
	MsgS("initQueue ok!\n");
	return 0;
}

//判断队列是否为空
int isEmpty(SqQueue *Q) {
	if (count == 0 && Q->front == Q->rear)
		return 1;
	else
		return 0;
}

//判断队列是否为满
int isFull(SqQueue *Q) {
	if (count == 50 && Q->front == (Q->rear + 1) % MAXSIZE)
		return 1;
	else
		return 0;
}

//插入元素e为Q的新队尾元素
int enQueue(SqQueue *Q, Frame e) {
	if (isFull(Q)) {
		MsgS("Queue is full!\n");
		usleep(10*1000);
	}
	Q->base[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	MsgS("enQueue ok!\n");
	count++;
	return 0;
}

//删除Q的队头元素，用e返回其值
int deQueue(SqQueue *Q,Frame *e) {
	*e = Q->base[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	MsgS("deQueue ok!\n");
	count--;
	return 0;
}

1.   一循环队列，队头指针为front，队尾指针为rear，循环队列长度为N，其队内有效长度为_______


2.  在一个容量为25的循环队列中，若头指针front=16,尾指针rear=9，则该循环队列中共有元素是_18__

        
循环队列头指针为front，队列尾指针为rear，队列容量为M，则元素个数为（rear-front+M）%M

循环队列满时，数组中还有一个空的单元。如图4-12-8所示，我们认为，队列已经满了，也就是说，我们不允许出现4-12-7的右图情况出现。

 

队列满的条件是：
(rear+1)%QueueSize == front
通用的计算队列长度的公式为：
(rear - front+ QueueSize)%QueueSize





为了解决顺序队列中的"假溢出"问题，需要把数组想象为一个首尾相接的环，称这种数组为"循环数组"，存储在其中的队列成为"循环队列"。
解决队满、队空的判断问题有3种方法：


①设置一个布尔变量以区别队满还是队空。


②浪费一个元素的空间，用于区别队满还是队空。


③是用一个计数器记录队列中的元素个数（即队列长度）。


在使用中，大都采用第②种方法，即队头、队尾指针中有一个指向元素，而另一个指向空闲元素。
通常约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示在一维数组中的当前位置的前一个位置。这种顺序队说明如下：
①队头指针的引用为q->front，队尾指针的引用为q->rear。（q 为队列名）
②初始时，设置q->front=q->rear=0。
③入队操作：在队列未满时，队尾指针先加1（要取模），再送值到队尾指针指向的空闲元素。
④出队操作：在队列非空时，队头指针先加1（要取模），再从队头指针指向的队头元素处取值。
⑤队空的条件：q->front=q->rear；队满的条件：q->front=（q->rear+1）% QueueSize。
⑥队列长度为（q->rear+QueueSiz-q->front）% QueueSize。
在循环队列的操作时应注意，队头指针、队尾指针加1时，都要取模，以保持其值不出界。
 
在循环队列上实现的基本运算：
①初始化InitQueue(q)。
       void InitQueue(qnode*&q)  
{q=(qnode*)malloc(sizeof(snode));  ∥指针初始化
  q->rear=q->front=0;
 } 
②判定队列是否为空Emptyq(q)。
       int Emptyq(snode*q) 
 {if(q->rear=q->front)  
return 1;  
else return 0; 
} 


③入队列EnQueue(q,x)。
  int EnQueue(qnode*q,ElemType x)
 {if((q->rear+1)%QueueSize==q->front)    ∥队满 
 return 0; 
 q->rear=（q->rear+1）%QueueSize;        ∥队尾指针进1
  q->data［q->rear］=x;  
return 1;  
} } 
④出队列OutQueue(qnode*q,ElemType x)。
int OutQueue(qnode*q,ElemType x)  
{if(q->rear=q->front) 
 return 0; 
 q->front=（q->front+1）%QueueSize;      ∥队头指针进1
  x=q->data［q->front］;
  return 1;  }  } 


⑤取队头元素GetHead(q,x)。
int GetHead(qnode*q,ElemType &x) 
 {if(q->rear=q->front)
  return 0;
  x=q->data［（q->front+1）%QueueSize］; 
 return 1;  }  } 
双端队列
双端队列（DeQue）是限定插入删除操作在表的两端进行的线性表。这两端分别叫做端点1和端点2。在实际使用中，可以有输出受限的双端队列，即一个端点允许插入和删除，另一个端点只允许插入的双端队列和输入受限的双端队列，即一个端点允许插入和删除，另一个端点只允许删除的双端队列。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。

循环队列–C语言实现–数据结构

目录


循环队列C语言实现数据结构
目录

一 要求
二 循环队列
三 循环队列的算法设计
1 建立循环队列
2 置空队列
3 入队
4 出队
5 打印队

四 程序
1 程序的结构
2 程序源码

五 程序测试
1 入队列
2 出队列
3 打印队列

六 源程序及封装软件下载
下载地址
格格是一枚智能专业的本科在校生很愿意和各位大佬交流如果大家有愿意交朋友的可以加格格的QQ446019725声明是CSDN即可






（一） 要求


  
假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。


（二） 循环队列


  
定义：为充分利用向量空间，克服”假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现, 当然也可以利用顺序表来实现。顺序表就是我们熟悉的数组 eg. sun[] 。 
回顾：我们再来回顾一下关于顺序队列的重要知识点。队列通常与栈对应，栈是一种后进先出的单端（尾端）处理的数据结构；那么与之对应的队列是一种先进先出的双端（头尾两端）的数据结构。队列的特点就是在一段进行入队（存储数据）操作，在另一端进行出队（删除数据）操作。 
为什么设计循环队列：大家在处理队列的时候，会遇到如下情况。例如说：我们的队列空间能够容纳1000个元素。首先，格格入队1000个元素，队列上溢，此时为“真溢出”。那么现在我们进行出队操作，我们一直出队，一直出队， 知道1000个元素全部被删除，此时我们发现队列仍然处于“上溢”状态，why？ 其实原因很简单，在非循环队列当中，无论我们的front指（偏移）到哪里，只要我们的rear指（偏移）向上阙，那么队列就是“满溢”的。这就造成了空间明明还被占据着，但是队列却已经无用武之地的窘境。对于空间有限的计算机来说，这无疑是一种浪费。也不是一个优秀的程序猿想要看到的。所以在这种情况下，循环队列诞生了。循环队列当中的“满溢”只有一种情况，那就是所有数据空降都被占领了。而不会存在非循环队列当中的“假溢出”现象。



  
我们所常见的顺序循环队列通常有两种数据结构。


结构一



typedef struct
{
    datatype sequ[m];
    //sequ[]为我们所建立的顺序表（sequence）
    int  front,rear;
    //front表示队列头的偏移量，rear表示队列的尾的偏移量
}qu;//qu是队列（queue）的缩写



结构二



typedef struct
{
    datatype sequ[m];
    //sequ[]为我们所建立的顺序表（sequence）
    int  rear, quelen;
    //rear表示队列的尾的偏移量，quelen表示的是队列中元素的个数
}qu;//qu是队列（queue）的缩写


  
那通过观察这两种机构我们能够很容易的发现，数据结构并不是固定的。我们觉得那种算法比较更合理，我们觉得哪种数据结构方便我们设计算法，那么我们就建立哪种数据结构。在本文当中，我们采用第二种数据结构。显而易见的是，当我们采用第二种数据结构时，我们建立的一个队列指针（qu*sq）队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。


（三） 循环队列的算法设计

在上面我们了解了循环队列的数据机构，但是仅仅学会了数据结构还远远不够。我们设计数据结构的目的是为了更好的存储数据，并利用数据。下面我们来看一看关于循环队列我们要掌握哪些最基本的算法（利用数据机构）。

3.1 建立循环队列



//建立队
qu* creatqueue();//函数声明
qu* creatqueue()//函数实现
{
    qu *sq;
    sq=(qu*)malloc(sizeof(qu));
    return sq;  
}

3.2 置空队列



//置空队
void setnull(qu*);//函数声明
void setnull(qu *sq)//函数实现
{
    sq->rear = m - 1;
    sq->quelen = 0;
}

3.3 入队



//入队
void enqueue(qu*, datatype);//函数声明
void enqueue(qu*sq, datatype x)//函数实现
{
    if (sq->quelen == 5)
        printf("Errot! The queue will be overflow! \n");
    else if((sq->rear+1)==m)
    {
        sq->rear = (sq->rear + 1) % m;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("过5入队成功!\n");
    }
    else
    {
        sq->rear++;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("入队成功！\n");
    }
}



3.4 出队



//出队
datatype *dequeue(qu*);//函数声明
datatype *dequeue(qu*sq)//函数实现
{
    datatype sun=0;
    if (sq->quelen == 0)
    {
        printf("Error! The queue will be under flow!\n");
        return 0;
    }
    else if ((sq->rear + 1) >= sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen];
        return(&sun);
    }
    else    //  if(sq->rear < sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen + m];
        return(&sun);
    }
}




3.5 打印队



//打印队
void print(qu*);//函数声明
void print(qu*sq)//函数定义
{
    if (sq->quelen == 0)
        printf("Error! The queue is Null!\n");
    else if ((sq->rear + 1) >= sq->quelen)
    {
        int i = sq->rear + 1 - sq->quelen;
        for (i; i <= sq->rear; i++)
            printf("%d   ", sq->sequ[i]);
    }
    else
    {
        int t = sq->rear - sq->quelen + m +1;
        int time = 1;
        for (t; time <= (sq->quelen); time++)
        {
            printf("%d   ", sq->sequ[t]);
            t++;
            if (t == m)
            {
                t = 0;
                continue;
            }
            else
            {
                continue;
            }
        }
    }
    printf("\n");
}

（四） 程序

下面我们来设计一个程序测试我们的数据机构与算法

4.1 程序的结构



4.2 程序源码

注意：该程序由Microsoft Visual Studio Enterprise 2015编译器进行调试。受制于编译器品牌及版本不同等不可抗因素造成的编译失败，请自行调整。



#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define m 5

//循环队列的结构类型定义
typedef int datatype;
typedef struct
{
    datatype sequ[m];
    int  rear, quelen;
}qu;

//函数声明
qu* creatqueue();
void setnull(qu*);
void enqueue(qu*, datatype);
datatype *dequeue(qu*);
void print(qu*);

//主函数
void main()
{
    qu *sq= creatqueue();

    datatype x, *p;
    int key;

    setnull(sq);
    do
    {
        printf("1.Enter Queue   2.Delete Queue   3.clc display   4.print queue   -1.Quit:");
        scanf_s("%d", &key);
        switch (key)
        {
        case 1:  printf("Enter the Data:"); scanf_s("%d", &x);
            enqueue(sq, x);  break;
        case 2:  p = dequeue(sq);
            if (p != NULL) printf("%d\n", *p);
            break;
        case 3:system("cls"); break;
        case 4:print(sq); break;
        case -1: exit(0);
        }
    } while (1);
}

//建立队
qu* creatqueue()
{
    qu *sq;
    sq=(qu*)malloc(sizeof(qu));
    return sq;  
}
//置空队
void setnull(qu *sq)
{
    sq->rear = m - 1;
    sq->quelen = 0;
}

//入队
void enqueue(qu*sq, datatype x)
{
    if (sq->quelen == 5)
        printf("Errot! The queue will be overflow! \n");
    else if((sq->rear+1)==m)
    {
        sq->rear = (sq->rear + 1) % m;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("过5入队成功!\n");
    }
    else
    {
        sq->rear++;
        sq->sequ[sq->rear] = x;
        sq->quelen++;
        printf("入队成功！\n");
    }
}


//出队
datatype *dequeue(qu*sq)
{
    datatype sun=0;
    if (sq->quelen == 0)
    {
        printf("Error! The queue will be under flow!\n");
        return 0;
    }
    else if ((sq->rear + 1) >= sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen];
        return(&sun);
    }
    else    //  if(sq->rear < sq->quelen)
    {
        sq->quelen--;
        sun = sq->sequ[sq->rear - sq->quelen + m];
        return(&sun);
    }
}

//打印队列
void print(qu*sq)
{
    if (sq->quelen == 0)
        printf("Error! The queue is Null!\n");
    else if ((sq->rear + 1) >= sq->quelen)
    {
        int i = sq->rear + 1 - sq->quelen;
        for (i; i <= sq->rear; i++)
            printf("%d   ", sq->sequ[i]);
    }
    else
    {
        int t = sq->rear - sq->quelen + m +1;
        int time = 1;
        for (t; time <= (sq->quelen); time++)
        {
            printf("%d   ", sq->sequ[t]);
            t++;
            if (t == m)
            {
                t = 0;
                continue;
            }
            else
            {
                continue;
            }
        }
    }
    printf("\n");
}



（五） 程序测试

5.1 入队列



5.2 出队列



5.3 打印队列


  
前面已经用到了打印队列，所以格格不再赘述，大家由5.2&5.3可知打印队列是成功的。


(六) 源程序及封装软件下载


  
下载地址



  
格格是一枚智能专业的本科在校生，很愿意和各位大佬交流。如果大家有愿意交朋友的，可以加格格的QQ：446019725，声明是CSDN即可。