队列

队列基本概念

队列( queue )是一种特殊的线性表结构，只从队尾插入新的元素，并且只从队首弹出元素。一般将队尾称为 rear，队首称为 front 。

队列基本操作

（1）入队：从队尾 rear 插入新元素；
（2）出队：从队首 front 弹出元素。

队列的特性

队列遵循 先进先出 的原则。比如元素 1、2、3、4、5 依次入队，且中途不存在出队过元素再次入队或其他元素入队，出队顺序为 1、2、3、4、5 。

---

循环顺序队列

循环顺序队列基本概念

顺序队列是用数组实现的队列，但是由于定义的数组的空间有限，可以想象一下，当队首 front 和 队尾 rear 经过一系列操作都往后移动时，之前所使用到的空间都不会再被使用了，这造成了空间上的浪费。

所以定义顺序队列往往采用更加高效的 循环顺序队列，其基本上就是在顺序队列的基础上加了一点小小的修改。

循环顺序队列的入队操作

循环顺序队列入队操作图解

初始状态下的循环顺序队列

元素1入队

元素2、3、4、5入队

循环顺序队列入队操作代码

//队列元素入队
void Enter_SqQueue(SqQueue *Q, int e){
    if((Q->rear + 1) % MAXSIZE == Q->front){
	printf("队列已满\n");
	return;
    }
    Q->data[Q->rear] = e;               //在队尾指向的地址赋值
    Q->rear = (Q->rear + 1) % MAXSIZE;  //队尾指针进1
}

---

循环顺序队列的出队操作

循环顺序队列出队操作图解

元素1出队

元素2、3、4、5出队

循环顺序队列出队操作代码

//队列元素出队
void Depart_SqQueue(SqQueue *Q, int *e){
    if(IsEmpty(Q)){
	printf("队列中无元素\n");
	return;
    }
    *e = Q->data[Q->front];             //取出队首指针指向的地址元素
    Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1
}

循环顺序队列中的循环示例

入队

此时队列rear虽然指向数组的最后，但循环操作可以使其重复利用之前使用的空间。

出队

类似的此时队列front指向数组的最后

---

循环顺序队列完整程序

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000

typedef int Elemtype;
typedef struct SqQueue{
	
    Elemtype data[MAXSIZE];
    int front;           //队列前指针
    int rear;            //队列后指针

}SqQueue;

//初始化
void Create_SqQueue(SqQueue *Q){
    Q->front = Q->rear = 0;
}

//判断队列是否为空
bool IsEmpty(SqQueue *Q){
    return Q->front == Q->rear;
}

//求得队列长度
int SqQueue_Length(SqQueue *Q){
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

//队列元素入队
void Enter_SqQueue(SqQueue *Q, int e){
    if((Q->rear + 1) % MAXSIZE == Q->front){
	printf("队列已满\n");
	return;
    }
    Q->data[Q->rear] = e;               //在队尾指向的地址赋值
    Q->rear = (Q->rear + 1) % MAXSIZE;  //队尾指针进1
}

//队列元素出队
void Depart_SqQueue(SqQueue *Q, int *e){
    if(IsEmpty(Q)){
	printf("队列中无元素\n");
	return;
    }
    *e = Q->data[Q->front];             //取出队首指针指向的地址元素
    Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1
}

//取队首
int Get_front(SqQueue *Q){
    if(IsEmpty(Q)){
	printf("队列为空\n");
	return -1;
    }
    return Q->data[Q->front];
}


int main(){
    SqQueue myQueue;
    Elemtype a[5] = {35, 30, 11, 23, 9};

    Create_SqQueue(&myQueue);
    for(int i = 0; i < 5; i++)
        Enter_SqQueue(&myQueue, a[i]);

    Elemtype e;
    Depart_SqQueue(&myQueue, &e);
    printf("出队元素: %d\n", e);

    printf("元素22入队并将所有元素出队: \n");
    Enter_SqQueue(&myQueue, 22);

    while(!IsEmpty(&myQueue)){
    	printf("%d ", Get_front(&myQueue));
    	Depart_SqQueue(&myQueue, &e);
    }

    return 0;
}

程序运行结果

---

链队列

链队列基本概念

链队列是链式的队列结构，其拥有一个 front 指针作为队首，一般队首 front 是不带数据的；还有一个 rear 指针作为队尾，队尾 rear 指向队列的最后一个元素。链队列的操作和链表也有一些相似之处。

链队列的入队操作

链队列入队操作图解

初始状态下的链队列

元素1入队

元素2、3入队

链队列入队操作代码

//链队列元素入队
void Enter_LinkQueue(LinkQueue *Q, int e){
    Linknode *node = (Linknode*)malloc(sizeof(Linknode));
    node->data = e;
    node->next = NULL;

    Q->rear->next = node;     //原先队列尾指针后继next指向新节点node
    Q->rear = node;           //尾指针重新指向新节点node
}

链队列的出队操作

链队列出队操作图解

元素1出队

链队列出队操作代码

当链队列只有一个元素并且将其出队时，需要特判一下，将链队列置于空队列的状态。

//链队列元素出队
void Depart_LinkQueue(LinkQueue *Q, int *e){
    if(Q->rear == Q->front) return;
    Linknode *p;
    p = Q->front->next;       //要删除的节点暂存给p
    *e = p->data;             //取出删除队头节点的数据
    Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点
	
    if(Q->rear == p)          //当队列只有一个元素的情况
    	Q->rear = Q->front;   
    free(p);
}

---

链队列完整程序

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int Elemtype;
//队列节点结构
typedef struct Linknode{

    Elemtype data;             //队列节点数据域
    struct Linknode *next;     //队列next指针域
	
}Linknode;

//链队列整体结构
typedef struct LinkQueue{

    Linknode *front;           //链队列首指针  队首指针不带数据
    Linknode *rear;            //链队列尾指针

}LinkQueue;

//初始化创建链队列
void Create_LinkQueue(LinkQueue *Q){
    Q->front = Q->rear = (Linknode*)malloc(sizeof(Linknode));
    Q->front->next == NULL;
}

//链队列元素入队
void Enter_LinkQueue(LinkQueue *Q, int e){
    Linknode *node = (Linknode*)malloc(sizeof(Linknode));
    node->data = e;
    node->next = NULL;

    Q->rear->next = node;     //原先队列尾指针后继next指向新节点node
    Q->rear = node;           //尾指针重新指向新节点node
}

//链队列元素出队
void Depart_LinkQueue(LinkQueue *Q, int *e){
    if(Q->rear == Q->front) return;
    Linknode *p;
    p = Q->front->next;       //要删除的节点暂存给p
    *e = p->data;             //取出删除队头节点的数据
    Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点
	
    if(Q->rear == p)          //当队列只有一个元素的情况
    	Q->rear = Q->front;  
    
    free(p);
}

//判断是否为空
bool IsEmpty(LinkQueue *Q){
    return Q->front == Q->rear;
}

//取队首
int Front_LinkQueue(LinkQueue *Q){
    if(IsEmpty(Q)){
	printf("队列为空\n");
	return -1;
    }
    return Q->front->next->data;
}

int main(){
    LinkQueue myQueue;
    Create_LinkQueue(&myQueue);

    Enter_LinkQueue(&myQueue, 1);
    Enter_LinkQueue(&myQueue, 2);
    Enter_LinkQueue(&myQueue, 3);
    printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue));
    
    Elemtype e;
    Depart_LinkQueue(&myQueue, &e);
    printf("出队的元素为 %d \n", e);
    printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue)); 
   	
    printf("\n所有元素出队：\n");
    while(!IsEmpty(&myQueue)){
    	printf("%d ", Front_LinkQueue(&myQueue));
    	Depart_LinkQueue(&myQueue, &e);
    }

    return 0;
}

程序运行结果