循环队列的基本定义 ：
 
顺序存储结构定义：
 
typedef struct{
    QElemType *base;
    int Front,Rear;
}CQueue;
 
 
 

循环队列的基本操作：
 
1、初始化一个队列
 
2、清空一个队列
 
3、判断一个队列是否为空
 
4、求队列的长度
 
5、入队列操作
 
6、出队列操作
 
7、取队头元素
 
8、历遍操作
 

1、初始化一个队列
 
void InitCQueue(CQueue &Q){
    Q.base=new QElemType [QueueSize];
    Q.Front=Q.Rear=0;
}
 
2、清空一个队列
 
void ClearCQueue(CQueue &Q){
    delete [] Q.base;
    InitCQueue(Q);
}
 
3、判断一个队列是否为空
 
bool QueueEmpty(CQueue Q){
    return Q.Front==Q.Rear?true:false;
}
 
4、求队列的长度
 
int QueueLength(CQueue Q){
    return (Q.Rear-Q.Front+QueueSize)%QueueSize;
}
 
5、入队列操作
 
void EnQueue(CQueue &Q,QElemType e){
    if((Q.Rear+1)%QueueSize == Q.Front){
        printf("error !!! Queue is full !!!");return ;
    }
    Q.base[Q.Rear]=e;
    Q.Rear=(Q.Rear+1)%QueueSize;
}
 
6、出队列操作
 
void DeQueue(CQueue &Q,QElemType &e){
    if(Q.Front==Q.Rear){
        printf("error !!! Queue is empty !!!");return ;
    }
    e=Q.base[(Q.Front)%QueueSize];
    Q.Front=(Q.Front+1)%QueueSize;
}
 
7、取队头元素
 
void GetHead(CQueue Q,QElemType &e){
    if(Q.Front==Q.Rear){
        printf("error !!! Queue is empty !!!");return ;
    }
    e=Q.base[Q.Front];
}
 
8、历遍操作
 
void QueueTraverse(CQueue Q){
    for(int i=Q.Front;i!=Q.Rear;i=(i+1)%QueueSize){
        printf("%d%c",Q.base[i],(i+1)%QueueSize==Q.Rear?'\n':' ');
    }
}
 

完整的调试代码：
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define QElemType int
#define QueueSize 11
using namespace std;
typedef struct{
    QElemType *base;
    int Front,Rear;
}CQueue;

void InitCQueue(CQueue &Q){
    Q.base=new QElemType [QueueSize];
    Q.Front=Q.Rear=0;
}
void ClearCQueue(CQueue &Q){
    delete [] Q.base;
    InitCQueue(Q);
}
bool QueueEmpty(CQueue Q){
    return Q.Front==Q.Rear?true:false;
}
int QueueLength(CQueue Q){
    return (Q.Rear-Q.Front+QueueSize)%QueueSize;
}
void EnQueue(CQueue &Q,QElemType e){
    if((Q.Rear+1)%QueueSize == Q.Front){
        printf("error !!! Queue is full !!!");return ;
    }
    Q.base[Q.Rear]=e;
    Q.Rear=(Q.Rear+1)%QueueSize;
}
void DeQueue(CQueue &Q,QElemType &e){
    if(Q.Front==Q.Rear){
        printf("error !!! Queue is empty !!!");return ;
    }
    e=Q.base[(Q.Front)%QueueSize];
    Q.Front=(Q.Front+1)%QueueSize;
}
void GetHead(CQueue Q,QElemType &e){
    if(Q.Front==Q.Rear){
        printf("error !!! Queue is empty !!!");return ;
    }
    e=Q.base[Q.Front];
}
void QueueTraverse(CQueue Q){
    for(int i=Q.Front;i!=Q.Rear;i=(i+1)%QueueSize){
        printf("%d%c",Q.base[i],(i+1)%QueueSize==Q.Rear?'\n':' ');
    }
}
int main()
{
    CQueue Q;
    InitCQueue(Q);
    int e;
    if(QueueEmpty(Q)){
        for(int i=0;i<10;i++){
            //printf("%d\n",i);
            EnQueue(Q,i);
        }
    }
    printf("Front : %d Rear : %d\n",Q.Front,Q.Rear);
    //printf("%d\n",Q.base[0]);

    QueueTraverse(Q);
    for(int i=0;i<9;i++){
        DeQueue(Q,e);
        printf("%d %d %d  F: %d R: %d\n",i,e,QueueLength(Q),Q.Front,Q.Rear);
    }
    GetHead(Q,e);printf("%d\n",e);

    for(int i=0;i<4;i++){
        //printf("%d\n",i);
        EnQueue(Q,i);
    }
    printf("Front : %d  Rear : %d\n",Q.Front,Q.Rear);
    for(int i=0;i<3;i++){
        DeQueue(Q,e);
        printf("%d %d %d  F: %d R: %d\n",i,e,QueueLength(Q),Q.Front,Q.Rear);
    }
    ClearCQueue(Q);
    if(QueueEmpty(Q)){
        printf("Front : %d  Rear : %d\n",Q.Front,Q.Rear);
    }

    return 0;
}
 
 

循环队列的顺序存储结构
 
在上次，我们讲到的是，队列的顺序存储结构也是由ArrayList实现的，从此就可以看出，在入队时候的时间复杂度为O(1)，但是在出队时候的时间复杂度为O(n)，这是因为，每次在出队后要将数组后面的有效元素前移一位。
 所以，这里就会用到循环队列，显然，这种队列也是顺序存储结构，在这个循环队列中也会去实现接口Queue。
 首先，我们要想到的是如何将一般的队列改变为循环队列。
 
和之前一般的队列的顺寻存储结构一样，默认初始数组容量为10（循环队列的数组实际容量为11，这是因为要空出一个数组空间，至于为什么，将在后面进行解释）；
定义一个头指针front和尾指针rear，用这两个指针去维护循环队列中元素的入队和出队；
定义一个size，去统计当前循环队列中的元素的有效个数；
 
现在，我们先看一下循环队列是如何入队和出队的。
 初始时：
 
 
入队一个元素：
 
 
出队一个元素：
 
 这样，front和rear指针就可以很轻松的去维护循环队列的入队和出队，并且它们的时间复杂度都为O(1)，但是要注意特殊情况的存在，比如，当数组的0角标没有元素但7角标也有元素的时候，rear指针就要移动到front的前面，如下图所示：
 
 
这个时候很明显，循环队列已经满了，所以我们就会想到，如何判断循环队列什么时候为满，什么时候为空？
 
其实，利用它的周期性可以很明显的得出结论：
 队列为满的时候：(rear+1)%n == front; (n为数组的总长度；如上图：(0+1)%8等于1也就是等于front指向的位置)
 如果出现这种情况，如下图示：
 
 
因为，我们每次的出队，front指针都会向后面移动一位，而rear指针是不会移动的，如果我们将上图的两个元素全部出队列，会出现这样的情况：
 
 
很显然，判断队列为空也为:(rear+1)%n == front;
 
这样的话就会重复，所以这就是我们之前说，为什么要在创建循环队列数组的时候多创建一个元素空间的原因了。
 因此，判断队列为空的条件就为：rear == front;
 如下图：
 
 
如上图，我们现在入队一个元素：
 
 
每次在入队的时候，将rear指针始终指向队尾最后一个元素的空间。
 并且每次入队的时候，rear的变化也要注意：rear = (rear+1)%n;
 
说了这么多，我们就来看一下具体的代码实现。
 首先和我们之前一样，先来看看它的顺序存储结构：
 
package DS01.动态数组;
import java.util.Iterator;
/**
 * @author 七夏
 * @param <E>
 * @version 1.0
 * 循环队列:如果我们默认创建一个为容量为10的的循环队列时，我们须在该循环队列容量的基础上再加1，
 * 这是为了在判断循环队列是否为空时，起到作用
 *
 * 循环队列为满时的条件：(rear+1)%data.length 等于 front
 * 循环队列为空时的条件：front == rear
 * 元素每次进队时，队头front每次更新：front = (front+1)%data.length
 * 元素每次出队时，队尾rear每次更新：rear = (rear+1)%data.length
 * 函数 E getRear() 在获取队尾元素时的方法为：data[(rear-1+data.length)%data.length]
 */
public class ArrayQueueLoop<E> implements Queue<E>{
	//设置默认初始容量（后面会加1）
    private static final int DEFAULT_CAPACITY = 10;
    private E[] data;
    private int front;
    private int rear;
    private int size;

    public ArrayQueueLoop(){
        this(DEFAULT_CAPACITY);
    }
    public ArrayQueueLoop(int capacity){
        if(capacity <= 0){
            throw new IllegalArgumentException("指定容量错误："+capacity);
        }
        data = (E[])(new Object[capacity+1]);//加1，让数组多出一个空间
        front = 0;
        rear = 0;
        size = 0;
    }
}
 
现在，看一下入队代码：
 
	@Override
    public void enqueue(E e) {
    	//判断队列是否满
        if((rear + 1)%data.length == front){
            //扩容
            resize(data.length*2-1);
        }
        data[rear] = e;
        //更新rear队尾指针位置
        rear = (rear+1)%data.length;
        size++;
    }
 
出队：
 
	@Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        //拿出对头元素
        E res = data[front];
        //更新front对头指针位置
        front = (front+1)%data.length;
        size--;
        //缩容
        if(size <= (data.length-1)/4 && (data.length-1)/2 >= 10){
            resize(data.length/2+1);
        }
        return res;
    }
 
扩容：
 
	private void resize(int newLen) {
        E[] newData = (E[])(new Object[newLen]);
        int p = front;
        int i = 0;
        while(true){
            newData[i] = data[p];
            i++;
            p = (p+1)%data.length;
            //如果p指针等于rear队尾指针时，结束循环
            if(p == rear){
                break;
            }
        }
        /*
        上述while循环相当于下述for循环
        for(int i = 0,p = front;p != rear;i++,p = (p+1)%data.length){
			newData[i] = data[p];
		}
        */
        front = 0;
        rear = size;
        data = newData;
    }
 
实现iterator方法：
 和之前都大致类似，在这里，我们在内部类中首先定义一个p指针，用来遍历循环队列，在hasNext函数中，只要p指针不等于rear队尾指针，说明该循环队列“尚不为空”（当前指向的元素后面还有元素）；next函数中，创建res变量获取当前元素，之后将更新p指针的位置，最终返回res。
 
	@Override
    public Iterator<E> iterator() {
        return new ArrayQueueLoopIterator();
    }
    private class ArrayQueueLoopIterator implements Iterator<E>{
        int p = front;
        @Override
        public boolean hasNext() {
            return p != rear;
        }

        @Override
        public E next() {
            E res = data[p];
            //更新p指针的指向位置
            p = (p+1)%data.length;
            return res;
        }
    }
 
其他方法：
 在这些方法中，我们要注意toString方法和getRear方法，在getRear方法中，我们直接返回data[(rear-1+data.length)%data.length]。
 
	@Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0 && front == rear;
    }
    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

    @Override
    public E getRear() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        return data[(rear-1+data.length)%data.length];
    }

    @Override
    public void clear() {
        data = (E[])(new Object[DEFAULT_CAPACITY+1]);
        front = 0;
        rear = 0;
        size = 0;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("ArrayQueue: %d/%d \n",getSize(),data.length-1));
        sb.append('[');
        if(isEmpty()){
            sb.append(']');
        }else{
            for (int i = front; i != rear; i = (i+1)%data.length) {
                sb.append(data[i]);
                if((i+1)%data.length == rear){
                    sb.append(']');
                }else{
                    sb.append(',');
                }
            }
        }
        return sb.toString();
    }

 五、队列的定义


 定义：队列（queue）：队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。


 队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入操作的一端称为队尾，允许删除操作的一端称为队头。


 队列与现实生活中的排队机制很像，排在队头的出队，而想入队则只能从队尾开始。


 ===============================================================================


 队列：


 顺序存储结构：（循环队列）


 



 #define N 10


 typedef int data_t;


 typedef struct 


 {


  data_t data[N]； //数据存储


  int length； //不能用，注意想想方式 


 }Node;


 



 ===============================================================================


 六、循环队列


 线性表有顺序存储和链式存储两种结构，队列作为特殊的线性表，自然也有顺序队列和链式队列两种形式。


 但是，队列的顺序存储却有很大的缺陷。如果我们要建立元素个数为n的队列，则需要建立一个数组长度不小于n的数组，数组下标为0的为队头，当最大下标的为队尾。若有元素要入队，则只需将其存储在第n+1个位置即可。


 而若想出队，则删除了下标为0的元素后，所有在其后的元素都需要向前移动一格，即保持下标为0的元素为队头。但这样做显然浪费了大量时间。


 解决该问题的方法就是不再限制下标为0的元素为队头，每次出队后，队头自动变成当前数组下标最小的元素即可。这样就无需所有元素向前移动。


 但是，若如此做，则会造成大量的已出队的元素的存储空间浪费。而且，若此时入队元素已经大于n，则我们需要更大的存储空间才行，但队头位置有大量空间未利用，空间浪费严重。


 解决以上问题的方法就是如果后面满了，则我们就从头开始，也就是将队列做成头尾相接的循环。我们把这种头尾相接的顺序存储结构的队列称为循环队列。


 这样，我们就需要两个指示其队头（front）和队尾（rear）的下标变量。


 typedef int data_t;


 typedef struct


 {


  data_t data[MAXSIZE];


  int front； 头位置下标


  int rear； 尾位置下标


 }SqQueue;


 



 循环队列的操作：


 1、创建空的循环队列（CreateSqQueue）


 2、判断是否为空队列（SqQueueEmpty）


 3、判断是否为满队列（SqQueueFull）


 4、新数据元素入队（EnQueue）


 5、数据元素出去（OutQueue）


 6、求队长（SqQueueLenght）


 7、遍历循环队列（VisitSqQueue）


 



 当front==rear时，此时队头和队尾重合，则该队列为空队列；当(rear+1)%QueueSize==front时，此时队尾的下个位置就是队头，则该队列为满队列。注意rear的位置不是队尾元素的位置，而是队尾元素的下一个位置，即当队列满时，队列中还有一个空闲存储空间，但我们规定该状态下就是满队列。


 那么，定义好队列的的队头和队尾位置，我们来考虑怎样计算队列长度。


 当rear>front时，表示队尾在队头右边，此时队列长度为rear-front；当rear<front时，表示队尾在队友左边，此时计算队列长度应分成两部分，即rear一部分，QueueSize-front一部分，总体长度为rear-front+QueueSize。


 通用计算队列长度的公式是


 length=(rear-front+QueueSize)%QueueSize


 1、判断队是否为空EmptyQueue


 //代码见附录


 2、判断队是否为满FullQueue


 //代码见附录


 3、入队操作EnQueue


 //代码见附录


 4、出队操作DeQueue


 //代码见附录


 从循环队列的特性我们可以看出，循环队列虽然操作较为简单，但是由于队列定长，因此会出现数据溢出问题。这时我们需要考虑使用队列的链式存储结构。


 ===============================================================================


 七、队列的链式存储结构及实现


 队列的链式存储结构本质上是从单链表演化而来的。将单链表改造成链式队列，如果将头结点做为队头，最后一个节点做为队尾，则该队列的出队操作方便，而入队操作较慢；反之，如果将头结点做为队尾，最后一个节点做为队头，则该队列的入队操作方便，而出队操作较慢。


 那么，能否将单链表稍加改进，使得该链式队列的入队操作和出队操作一样方便呢？


 答案是可以的，只需要改进头结点。将“头结点存储一个next指针”改为“头结点存储两个指针front和rear”，front指针指向队头，rear指针指向队尾。这样我们进行出队/入队操作时，只需要访问这两个指针就能快速地找到队头/队尾。


 1、队列的链式存储结构定义


 将单链表的头结点稍加改造


 typedef int data_t;


 typedef struct node_t//定义单链表


 {


  data_t data;


  struct node_t *next;

 


 } linknode_t, *linklist_t;


 typedef struct//定义链式队列


 {


  linklist_t front, rear;


 } linkqueue_t;


 



 链式队列的操作：


 申请的头指针为lq，lq->front == lq->rear


 1、创建空链式队列（CreateLinkQueue）


 2、判断是否为空（LinkQueueEmpty） rear == front ！= NULL


 3、清空链式队列（ClearLinkQueue）


 4、求链式队列的长度（LinkQueueLength）


 5、新数据元素入队（EnLinkQueue） rear指向最后元素


 6、数据元素出队（DeLinkQueue）


 7、遍历整个链式队列数据元素（PrintLinkQueue）


 



 2、判定链式队列是否为空


 由于单链表的属性，链式队列几乎不会出现“队列已满”的情况，因此不考虑判定链式队列是否已满的操作。


 判定链式队列是否为空，只需要判定队列的front指针是否为空即可。


 //代码见附录


 3、队列的链式存储结构——入队操作


 入队操作其实就是在链表尾部插入节点。新来的数据节点附在当前rear节点之后，并将rear节点指向该节点即可。


 //代码见附录


 4、队列的链式存储结构——出队操作


 出队操作就是将链表的头结点的后继节点出队，并将其之后的节点设置为头结点的后继节点。若链表除头结点外仅剩一个元素，则需将rear指向头结点。


 //代码见附录


 



 对于循环队列和链式队列的比较，二者从时间复杂度上来说都是O(1)，不过链式队列需要花费额外的申请节点的时间，而且链式队列删除节点也需要一些时间。从空间上来说，循环队列有固定长度，就意味着循环队列有其存储上限，因此也就存在元素溢出以及空间浪费等问题，而链式队列则不存在这些问题。


 总体来说，若可以大致确定元素个数的情况下，推荐使用循环队列；若无法事先预知元素个数，则应使用链式队列。


 ===============================================================================


 ======================================================================

/**************************
循环队列的顺序存储结构

功能代码包含：
1）循环队列的顺序存储结构的数据结构定义
2）初始化循环队列
3）往循环队列中插入元素--入队
4）删除循环队列中的元素--出队
5）求循环队列的实际长度

注意：代码不进行debug，只实现基本功能

Author:tmw
date:2018-3-9
**************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXSIZE 100 //定义队列大小
#define error -65530;

/**循环队列的顺序存储结构的数据结构定义**/
typedef struct SqQueue
{
    int data[MAXSIZE];
    int front;  /**头指针**/
    int rear;   /**尾指针**/
}SqQueue;

/**初始化循环队列**/
void initSqQueue( SqQueue *Q )
{
    Q->front = 0;
    Q->rear = 0;
}

/**往循环队列中插入元素e--入队**/
bool EnQueue( SqQueue *Q, int e )
{
    /**入队前提：队列不能满**/
    if( ( Q->rear+1 ) % MAXSIZE == Q->front )
        return false;

    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXSIZE;

    return true;
}

/**出队操作，并返回出队元素**/
int DeQueue( SqQueue *Q )
{
    /**出队前提条件：队列非空**/
    if( Q->front == Q->rear )
        return error;

    int e = Q->data[Q->front];
    Q->front = ( Q->front+1 ) % MAXSIZE;

    return e;
}

/**求循环队列的实际长度**/
int len_of_SqQueue( SqQueue *Q )
{
    return ( Q->rear + MAXSIZE - Q->front ) % MAXSIZE;
}




 梦想还是要有的，万一实现了呢~~~ヾ(◍°∇°◍)ﾉﾞ