队的实现及思路

1.队列的定义

一端只能入，一端只能出。

2.循环队列

2.1方法1：（常用）

2.1.1结构体的定义

typedef int ElemType;
#define MaxSize 50    //定义队列中元素最大的个数
typedef struct{
    ElemType data[MaxSize];    //存放队列元素
    int front,rear;    //队头指针和队尾指针
}SqQueue;

 2.1.2循环队列的初始化

也就是将队列设置为空。

//初始化队列
void InitQueue(SqQueue* Queue){
    Queue->rear = Queue->front = 0;//将尾指针和头指针设置为0
}

2.1.3判断队空

两个指针同时指向同一个位置，则代表队列为空。

/*功能：判断队列是否为空
**参数：Queue传入的队列
**返回值：队列为空返回true，队列非空返回false
*/
bool isEmpty(SqQueue Queue){
    if(Queue.rear == Queue.front)//若首位指针指向同一个位置，则代表为空
        return true;//为空返回真
    return false;//否则返回假
}

2.1.4入队

入队时，在尾指针指向的位置插入数值，然后尾指针再移动。

什么时候是队满那，如队列中全部储存数据。就会发现front和rear指向同一个地方。无法判断到底

是队列是满，还是队列为空。方法一就是牺牲一个位置表示队满。即front=rear为队空，(rear+1)%MaxSize=front为队满。

/*功能：入队
**参数：Queue传入的队列的地址，x为写入的数据
**返回值：入队成功返回true，入队失败返回false
*/
bool EnQueue(SqQueue* Queue,ElemType x){
    if( (Queue->rear+1)%MaxSize == Queue->front)//判断是否队满
        return false;//如果队满则返回false，无法向队列中插入
    Queue->data[Queue->rear] = x;
    Queue->rear = (Queue->rear + 1)%MaxSize;//队尾指针加1取模
    return true;
}

 2.1.5出队

出队front指向的地址，先保存该数值再加1取模，还需要判断队空。

物理上没有删除，逻辑上删除了。

/*功能：出队
**参数：Queue传入的队列的地址，data传入要存储数据的地址
**返回值：出队成功返回true，出队失败返回false
*/
bool DeQueue(SqQueue* Queue,ElemType* data){
    if(Queue->rear == Queue->front)//如果队列为空
        return false;//则返回false
    *data = Queue->data[Queue->front];//取队列值
    Queue->front = (Queue->front + 1)%MaxSize;//队头指针加1取模
    return true;
}

2.2方法2：

它们的区别就是队空队满的判断。我们定义一个size，用来存储队列中的数据的个数。

 2.2.1结构体的定义

typedef int ElemType;
#define MaxSize 50    //定义队列中元素最大的个数
typedef struct{
    ElemType data[MaxSize];    //存放队列元素
    int size;//存储队列中的元素，方便判断队空和队满
    int front,rear;    //队头指针和队尾指针
}SqQueue;

2.2.2循环队列的初始化

/*功能：初始化队列
**参数：Queue传入的队列的地址
**返回值：无
*/
void InitQueue(SqQueue* Queue){
    Queue->rear = Queue->front = 0;//将尾指针和头指针设置为0
    Queue->size = 0;//设置队列大小为0
}

2.2.3判断队空

/*功能：判断队列是否为空
**参数：Queue传入的队列
**返回值：队列为空返回true，队列非空返回false
*/
bool isEmpty(SqQueue Queue){
    if(Queue.size == 0)//队列size=0则为空
        return true;
    return false;
}

2.2.4入队

/*功能：入队
**参数：Queue传入的队列的地址，x为写入的数据
**返回值：入队成功返回true，入队失败返回false
*/
bool EnQueue(SqQueue* Queue,ElemType x){
    if(Queue->size == MaxSize)//判断是否队满
        return false;//如果队满则返回false，无法向队列中插入
    Queue->data[Queue->rear] = x;
    Queue->rear = (Queue->rear + 1)%MaxSize;//队尾指针加1取模
    Queue->size++;//队列元素个数增加
    return true;
}

2.2.5出队

/*功能：出队
**参数：Queue传入的队列的地址，data传入要存储数据的地址
**返回值：出队成功返回true，出队失败返回false
*/
bool DeQueue(SqQueue* Queue,ElemType* data){
    if(Queue->size == 0)//如果队列为空
        return false;//则返回false
    *data = Queue->data[Queue->front];//取队列值
    Queue->front = (Queue->front + 1)%MaxSize;//队头指针加1取模
    Queue->size--;//队列元素个数减少
    return true;
}

 2.3方法3：

设置一个标志位tag，每次插入后把tag设置为1，若下次插入时tag==1且front==rear，则代表队满。每次删除后tag设置为0，若下次再次删除时tag==0且front==rear，则代表队空。

2.3.1结构体定义

typedef int ElemType;
#define MaxSize 50    //定义队列中元素最大的个数
typedef struct{
    ElemType data[MaxSize];    //存放队列元素
    bool tag;//标志位，与front和rear共同判断队满队空
    int front,rear;    //队头指针和队尾指针
}SqQueue;

2.3.2循环队列的初始化

/*功能：初始化队列
**参数：Queue传入的队列的地址
**返回值：无
*/
void InitQueue(SqQueue* Queue){
    Queue->rear = Queue->front = 0;//将尾指针和头指针设置为0
    Queue->tag = 0;
}

2.3.3判断队空

/*功能：判断队列是否为空
**参数：Queue传入的队列
**返回值：队列为空返回true，队列非空返回false
*/
bool isEmpty(SqQueue Queue){
    if( (Queue.tag == 0) && (Queue.front == Queue.rear) )//队列size=0则为空
        return true;
    return false;
}

2.3.4入队

/*功能：入队
**参数：Queue传入的队列的地址，x为写入的数据
**返回值：入队成功返回true，入队失败返回false
*/
bool EnQueue(SqQueue* Queue,ElemType x){
    if( (Queue->tag == 1) && (Queue->front == Queue->rear) )//判断是否队满
        return false;//如果队满则返回false，无法向队列中插入
    Queue->data[Queue->rear] = x;
    Queue->rear = (Queue->rear + 1)%MaxSize;//队尾指针加1取模
    Queue->tag = 1;//设置为插入标记
    return true;
}

2.3.5出队

/*功能：出队
**参数：Queue传入的队列的地址，data传入要存储数据的地址
**返回值：出队成功返回true，出队失败返回false
*/
bool DeQueue(SqQueue* Queue,ElemType* data){
    if( (Queue->tag == 0) && (Queue->front == Queue->rear) )//如果队列为空
        return false;//则返回false
    *data = Queue->data[Queue->front];//取队列值
    Queue->front = (Queue->front + 1)%MaxSize;//队头指针加1取模
    Queue->tag = 0;//设置为出队标记
    return true;
}

3.队列的链式存储

申请队头为

LinkQueue Queue = (QueueNode*)malloc(sizeof(QueueNode));

3.1结构体的定义

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;//链表数据
    struct LinkNode* next;//链表的下一个元素的地址
}LinkNode;//链表
typedef struct{
    LinkNode *front,*rear;//队列的头尾指针
}*LinkQueue;

3.2队列的初始化

/*功能：初始化队列
**参数：Queue传入地址的地址
**返回值：无
*/
void InitQueue(LinkQueue* Queue){
    (*Queue)->rear = (*Queue)->front = (LinkNode*)malloc(sizeof(LinkNode));//建立头结点
    (*Queue)->front->next = NULL;//设置队列为空
}

3.3判断队空

/*功能：判断队列是否为空
**参数：传入LinkQueue的指针
**返回值：队列为空返回true，队列非空返回false
*/
bool isEmpty(LinkQueue Queue){
    if( Queue->front == Queue->rear )//队列size=0则为空
        return true;
    return false;
}

3.4入队

入队从队尾入，即从尾指针插入。

/*功能：入队
**参数：Queue传入的队列的地址，x为写入的数据
**返回值：入队成功返回true，入队失败返回false
*/
bool EnQueue(LinkQueue* Queue,ElemType x){
    LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
    if(NewNode == NULL)//分配内存失败就返回false
        return false;
    NewNode->data = x;//把数据存入该结点中
    NewNode->next = NULL;//新节点的next域设置为NULL
    (*Queue)->rear->next = NewNode;//队尾插入新结点
    (*Queue)->rear = NewNode;//把尾指针移动到队尾
    return true;
}

3.5出队

若出队的为最后一个结点，则它单独处理。这个就是一个普通的链表删除。

/*功能：出队
**参数：Queue传入的队列的地址，data传入要存储数据的地址
**返回值：出队成功返回true，出队失败返回false
*/
bool DeQueue(LinkQueue* Queue,ElemType* data){
    if( (*Queue)->rear == (*Queue)->front )//如果队列为空
        return false;//则返回false
    LinkNode* TempNode = (*Queue)->front->next;//保存队头
    *data = TempNode->data;//取队列值
    (*Queue)->front->next = TempNode->next;//对头向后移动
    if( (*Queue)->rear == TempNode )//若删除的为最后一个结点
        (*Queue)->rear = (*Queue)->front;//单独更新尾指针
    free(TempNode);
    return true;
}