队列的初识和实现

深碍√TFBOYSˉ_ 2024-04-03 09:28 39阅读 0赞

#### 文章目录 ####

*  队列的概念和结构
 *  实现
 *  链表实现代码
 *  循环队列
 *  循环队列的练习题
 *   *  参考答案【数组实现】

## 队列的概念和结构 ##

![在这里插入图片描述][0444a495887d47b48ed3ff7ad2400f38.png]

*  队列：***只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（FirstInFirstOut）***
 *  入队列：***进行插入操作的一端称为队尾***
 *  出队列：***进行删除操作的一端称为队头***
 *  空队列：不含任何数据元素的队列。

## 实现 ##

*  数组和链表都可以实现链表，但使用链表的结构会更优一些，如果使用数组的结构，出队列在数组头出数据，效率会比较低。  
    ![在这里插入图片描述][bf5a641cd38f442db2ee70de9a214f41.png]

## 链表实现代码 ##

typedef int QDataType;
    typedef struct QueueNode {
        
    	struct QueueNode* next;
    	QDataType data;
    } QueueNode;
    typedef struct Queue {
        
    	QueueNode* head;
    	QueueNode* tail;
    }Queue;

#define _CRT_SECURE_NO_WARNINGS
    #include"Queue.h"
    void QueueInit(Queue* pq) {
        
    	assert(pq);
    	pq->head = NULL;
    	pq->tail = NULL;
    }
    void QueueDestroy(Queue* pq) {
        
    	assert(pq);
    	QueueNode* cur = pq->head;
    	while (cur != NULL) {
        
    		QueueNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->head = pq->tail = NULL;
    }
    void QueuePush(Queue* pq, QDataType x) {
        
    	assert(pq);
    	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    	newNode->data=x;
    	newNode->next = NULL;
    	if (pq->head == NULL) {
        
    		pq->head = pq->tail = newNode;
    	}
    	else {
        
    		pq->tail->next = newNode;
    		pq->tail = newNode;
    	}
    }
    
    void QueuePop(Queue* pq) {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	QueueNode* newHead = pq->head->next;
    	free(pq->head);
    	pq->head = newHead;
    	if (pq->head == NULL) {
        
    		pq->tail=NULL;
    	}
    }
    QDataType QueueFront(Queue* pq) {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	return pq->head->data;
    }
      
    QDataType QueueBsck(Queue* pq) {
        
    	assert(pq);
    	assert(!QueueEmpty(pq));
    	return pq->tail->data;
    }
    
    
    int QueueSize(Queue* pq) {
        
    	assert(pq);
    	int n = 0;
    	QueueNode* cur = pq->head;
    	while (cur) {
        
    		n++;
    		cur = cur->next;
    	}
    	return n;
    }
    
    bool QueueEmpty(Queue* pq) {
        
    	assert(pq);
    	return pq->head == NULL;
    }

## 循环队列 ##

*  实现可以用数组或者链表实现
 *  重点：***循环链表，无论使用数组还是链表实现，都要多开一个空间，简单说：要存储k个数组的循环队列，要开k+1个空间，否则无法实现判空和判满。***  
    ![在这里插入图片描述][d93d41fd132e4b70b4964cb4af0a9557.png]  
    ![在这里插入图片描述][3c27d739f4bd4517a636eed063a12028.png]

## 循环队列的练习题 ##

*  [题目链接][Link 1]  
    ![在这里插入图片描述][05565752c8764e609040f9ca57de4b44.png]

### 参考答案【数组实现】 ###

typedef struct {
        
        int* a;//数组的首地址
        int front;//队头
        int tail;//队尾
        int k;//数据个数
    } MyCircularQueue;
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj);
    bool myCircularQueueIsFull(MyCircularQueue* obj);
    
    MyCircularQueue* myCircularQueueCreate(int k) {
        
        MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        cq->a=(int*)malloc(sizeof(int)*(k+1));
        cq->front=cq->tail=0;
        cq->k=k;
        return cq;
    }
    
    
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
        
        if(myCircularQueueIsFull(obj)) {
        
            return false;
        }
        obj->a[obj->tail]=value;
        ++obj->tail;
        obj->tail%=(obj->k+1);//保证tail会从数组尾重新回到数组头，实现理论循环
        return true;
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj) {
        
        if(myCircularQueueIsEmpty(obj)) {
        
            return false;
        }
        ++obj->front;
        obj->front%=(obj->k+1);//保证tail会从数组尾重新回到数组头，实现理论循环
        return true;
    }
    
    int myCircularQueueFront(MyCircularQueue* obj) {
        
        if(myCircularQueueIsEmpty(obj)) {
        
            return -1;
        }
        return obj->a[obj->front];
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) {
        
        if(myCircularQueueIsEmpty(obj)) {
        
            return -1;
        }
        int i=(obj->tail+obj->k)%(obj->k+1);//利用此公式找到理论的队尾元素在真是数组中的下标
        return obj->a[i];
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
        
        return obj->front==obj->tail;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) {
        
        return (obj->tail+1)%(obj->k+1)==obj->front;//利用此公式
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) {
        
        free(obj->a);
        free(obj);
    }

[0444a495887d47b48ed3ff7ad2400f38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7c3c347d7a0b4a4e863b48f1db10ca00.png
[bf5a641cd38f442db2ee70de9a214f41.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/73b53beb87ae4f608b5013e0a5865ab1.png
[d93d41fd132e4b70b4964cb4af0a9557.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/60a9bd2e84014c59a36b89c66e871087.png
[3c27d739f4bd4517a636eed063a12028.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/ccfeb7703fc44f3cab7610ddd0c81fcc.png
[Link 1]: https://leetcode.cn/problems/design-circular-queue/
[05565752c8764e609040f9ca57de4b44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7296f009205d4c5fb3101c319cccf3c0.png