Data Structure--队列基本接口的实现(详细)

素颜马尾好姑娘i 2022-10-30 15:19 145阅读 0赞

## 队列 ##

队列也是比较简单的,主要理解管道式通路,注意理解**先进先出**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

### 队列 ###

typedef int QDataType;
    
    typedef struct QNode{ 
    		
    	struct QNode* _next;	//下一个节点的地址
    	QDataType _data;		//数据
    	
    }QNode;
    
    typedef struct Queue{ 
    
    	QNode* _front;	//类似于单链表的理解
    	QNode* _rear;	//下一个指向
    }Queue;

### 接口声明 ###

还是和上面的一样,对于比较简单的就不重点讲解了

//1.初始化
    void queueInit(Queue* q);
    //2.检查容量
    QNode* creatNode(QDataType data);
    //3.队尾入队
    void queuePush(Queue* q, QDataType data);
    //4.队头出队
    void queuePop(Queue* q);
    //5.大小
    int queueSize(Queue* q);
    //6.判空
    int queueEmpty(Queue* q);
    //7.销毁
    void queueDestory(Queue* q);

### 接口实现 ###

#### 1.初始化 ####

void queueInit(Queue* q){ 
    
    	q->_front = q->_rear = NULL;	//直接让指向为空即可
    }

#### 2.检查容量 ####

QNode* creatNode(QDataType data){ 
    
    	QNode* node = (QNode*)malloc(sizeof(QNode));	//动态开辟空间
    	
    	node->_data = data;	//指向新的数据
    	node->_next = NULL;	//下一个地址为空
    	return node;
    }

#### 3.队尾入队 ####

void queuePush(Queue* q, QDataType data){ 
    
    	QNode* node = creatNode(data);		//先进行创建
    
    	if (q->_front == NULL)	//如果没有元素存在
    		q->_front = q->_rear = node;	//直接进行赋予
    	else{ 
    	//如果有元素存在
    		q->_rear->_next = node;		//下一个节点指向node 
    		q->_rear = node;		//更新
    	}
    }

#### 4.队头出队 ####

void queuePop(Queue* q){ 
    	
    	if (q->_front){ 		//存在元素再进行
    		QNode* next = q->_front->_next;		//定义一个next的节点记住下一个地址
    		free(q->_front);	//释放空间
    		q->_front = next;	//对front指向改变
    
    		//判断是否为空
    		if (q->_front == NULL)
    			q->_rear == NULL;
    	}
    }

#### 5.大小 ####

int queueSize(Queue* q){ 
    
    	int num = 0;			//定义一个整型数组进行计数
    	QNode* cur = q->_front;	//定义节点指向下一个
    	while (cur){ 		//下一个存在的时候进行循环
    		
    		++num;
    		cur = cur->_next;	//循环
    	}
    	return num;
    
    	//也可以直接在结构体变量内部定义一个size变量,能更简易的获取
    }

#### 6.判空 ####

int queueEmpty(Queue* q){ 
    
    	if (q->_front == NULL)	//直接看front节点的指向
    		return 1;
    	return 0;
    }

#### 7.销毁 ####

void queueDestory(Queue* q){ 
    
    	QNode* cur = q->_front;	//指向下一个
    	while (cur){ 	//循环
    		
    		QNode* next = cur->_next;	//先定义一个节点,用来保存下一个节点的地址
    		free(cur);	//释放
    		cur = next;	//循环
    	}
    	q->_front = q->_rear = NULL;	//最后将front 和rear节点变为空
    }

这一节也挺好理解的,基本上和我们之前讲过的顺序表,单链表,双向链表的处理思路是一致的,只要你将之前的掌握了,这里就没有问题的!!!多敲代码,一起加油!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/25766531689542898b409d114b8e2bc9.png