顺序队列

—— 头文件

#include <stdio.h>

构造入队列的函数

// 入队列
int enQueue(int *queue, int rear, int data){
	queue[rear] = data;
	return ++rear;
} 

构造展示队列元素的函数

// 展示队列元素
void show(int *queue, int length){
	for(int i = 0; i < length; i++){
		printf("%d ", queue[i]);
	}
	printf("\n");
} 

构造出队列的函数

// 出队列
int deQueue(int *queue, int front, int rear){
	while(front != rear){
		printf("出队元素：%d\n",queue[front]);
		front++;
	}
	return front;
} 

—— 主函数

int main(void){
	int queue[100];
	int rear, front;
	rear = front = 0;
	printf("进行入队列及出队列之前：front=%d，rear=%d\n", front, rear);
	// 进行入队列及出队列之前：front=0，rear=0
	
	rear = enQueue(queue, rear, 1);
	rear = enQueue(queue, rear, 2);
	rear = enQueue(queue, rear, 3);
	rear = enQueue(queue, rear, 4);
	show(queue, rear-front);  // 1 2 3 4
	front = deQueue(queue, front, rear);
	// outputs: 出队元素：1
	//		    出队元素：2
	//			出队元素：3 
	//			出队元素：4	
	
	printf("进行入队列及出队列之后：front=%d，rear=%d\n", front, rear);
	// 进行入队列及出队列之后：front=4，rear=4
	return 0;
} 

对顺序队列的优化 —— 环状队列

—— 头文件

#include <stdio.h>
#define max 5  // 表示顺序表申请的空间大小

构造初始化队列的函数

// 初始化队列
void init(int *queue){
	for(int i = 0; i < max-1; i++){
		queue[i] = 0;
	}
} 

构造入队列的函数

// 入队列 
int enQueue(int *queue, int front, int rear, int data){
	if((rear+1)%max==front){
		printf("空间已满");
		return rear; // rear最大值为 max-1(4)
	}
	queue[rear%max] = data;
	return ++rear;
}

构造展示队列元素的函数

// 展示队列元素
void show(int *queue, int front, int rear){
	// queue[0] ~ queue[3] ！！！ queue[4] == queue[0] ！！！ max=4 
	for(int i = front; i < rear; i++){
		printf("%d ", queue[i]);
	}
	printf("\n");
} 

构造出队列的函数

// 出队列 
int  deQueue(int *queue, int front, int rear){
	if(rear%max == front){  // 4==4
		printf("队列为空");
//		// 当检测出队列为空时，初始化
//		front = rear = 0; 
        return front; // 4
	}
	printf("出列元素：%d\n",queue[front]);
    front = (front + 1) % max;  // 1%5 2%5 3%5 4%5 
    return front;
}

—— 主函数

int main(void){
	int queue[max];
	init(queue);  // 将每一项初始化为 0 
	
	int front, rear;
	front = rear = 0;
	rear = enQueue(queue, front, rear, 1);
	rear = enQueue(queue, front, rear, 2);
	rear = enQueue(queue, front, rear, 3);
	rear = enQueue(queue, front, rear, 4);
	show(queue, front, rear);  // 1 2 3 4
	
	front = deQueue(queue, front, rear);  // 1
	front = deQueue(queue, front, rear);  // 2
	front = deQueue(queue, front, rear);  // 3
	front = deQueue(queue, front, rear);  // 4
	show(queue, front, rear);  // null 
	return 0;
} 

链队列

—— 头文件

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

结构体声明队列节点

// 链表中的节点结构
typedef struct myQNode{
    int data;
    struct myQNode *next;
} QNode;

构造创建链式队列的函数

// 创建链式队列的函数
QNode *initQueue(){
    // 创建一个头节点（节点的 next指向 NULL） 
    QNode *queue = (QNode*)malloc(sizeof(QNode));
    // 对头节点进行初始化
    queue->next = NULL;
    return queue;
}

构造尾插法插入链队列元素的函数

// 尾插法插入链式队列中元素的函数 
QNode *enQueue(QNode *rear, int data){
    // 用节点包裹入队元素
    QNode *enElem = (QNode*)malloc(sizeof(QNode));
    enElem->data = data;
    enElem->next = NULL;
    // 新节点与rear节点建立逻辑关系
    rear->next = enElem;
    // rear指向新节点
    rear = enElem;
    // 返回新的rear，为后续新元素入队做准备
    return rear;
}

构造出列函数

// 链式队列中元素出列的函数 
QNode *DeQueue(QNode *top, QNode *rear){
    if (top->next == NULL) {
        printf("\n队列为空");
        return rear;
    }
    QNode *p = top->next;
    printf("%d ", p->data);
    top->next = p->next;
    if (rear == p) {
        rear = top;
    }
    free(p);
    return rear;
}

—— 主函数

int main(void){
	QNode *top, *rear;
    top = rear = initQueue();  // 创建头尾结点
    
    // 向链式队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear = enQueue(rear, 1);
    rear = enQueue(rear, 2);
    rear = enQueue(rear, 3);
    rear = enQueue(rear, 4);
    
    // 入队完成，所有数据元素开始出队列
    rear = DeQueue(top, rear);
    rear = DeQueue(top, rear);
    rear = DeQueue(top, rear);
    rear = DeQueue(top, rear);
    rear = DeQueue(top, rear);
	return 0;
}