[数据结构] 队列与循环队列

た入场券 2022-10-14 14:58 186阅读 0赞

### 目录 ###

*  一. 队列概念
 *  二. 队列的实现
 *  三. 循环队列
 *   *  1. 存储方式
     *  2. 代码实现

# 一. 队列概念 #

队列只允许在一端进行数据插入，在另一端进行数据删除的线性表，特性为先进先出(FIFO)，入队列在队尾进行插入操作，出队列在对头进行删除操作。

# 二. 队列的实现 #

普通队列通过链式进行存储，队列的链式存储有易操作空间大小容易扩充的特性。  
  在这里对队列的基本操作，就不再详细解释，直接看代码。

typedef char QDataType;
    
    // 链式结构：表示队列
    typedef struct QListNode
    { 
    	struct QListNode* _pNext;
    	QDataType _data;
    }QNode;
    // 队列的结构
    typedef struct Queue
    { 
    	QNode* _front;
    	QNode* _rear;
    }Queue;
    
    QListNode* BuySListNode(QDataType x)
    { 
    	QListNode* pNew = (QListNode*)malloc(sizeof(QListNode));
    	pNew->_data = x;
    	pNew->_pNext = NULL;
    
    	return pNew;
    }
    // 初始化队列
    void QueueInit(Queue* q)
    { 
    	QNode* pHead = BuySListNode(0);
    	if (pHead == NULL)
    	{ 
    		return;
    	}
    
    	pHead->_pNext = NULL;
    
    	q->_front = q->_rear = pHead;
    }
    
    // 队尾入队列
    void QueuePush(Queue* q, QDataType data)
    { 
    	assert(q);
    
    	QListNode* newNode = BuySListNode(data);
    
    	q->_rear->_pNext = newNode;
    	q->_rear = newNode;
    }
    
    // 队头出队列
    void QueuePop(Queue* q)
    { 
    	assert(q);
    
    	if (QueueEmpty(q))
    	{ 
    		return;
    	}
    
    	QListNode* delNode = q->_front->_pNext;
    	q->_front->_pNext = delNode->_pNext;
    
    	// 如果队列中只有一个节点，则出队后将队尾指针指向队头
    	if (delNode->_pNext == NULL)
    	{ 
    		q->_rear = q->_front;
    	}
    	free(delNode);
    }
    
    // 获取队列头部元素
    QDataType QueueFront(Queue* q)
    { 
    	assert(q && !QueueEmpty(q));
    
    	return q->_front->_pNext->_data;
    }
    
    // 获取队列队尾元素
    QDataType QueueBack(Queue* q)
    { 
    	assert(q && !QueueEmpty(q));
    	return q->_rear->_data;
    }
    
    // 获取队列中有效元素个数
    int QueueSize(Queue* q)
    { 
    	assert(q);
    
    	int count = 0;
    	QListNode* pCur = q->_front->_pNext;
    	
    	while (NULL != pCur)
    	{ 
    		count++;
    		pCur = pCur->_pNext;
    	}
    
    	return count;
    }
    
    // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
    int QueueEmpty(Queue* q)
    { 
    	assert(q);
    	return NULL == q->_front->_pNext;
    }
    
    // 销毁队列
    void QueueDestroy(Queue* q)
    { 
    	assert(q);
    
    	QListNode* delNode = q->_front;
    
    	while (delNode)
    	{ 
    		q->_front = delNode->_pNext;
    		free(delNode);
    		delNode = q->_front;
    	}
    
    	q->_front = q->_rear = NULL;
    }

# 三. 循环队列 #

## 1. 存储方式 ##

在循环队列的实现中，使用数组来实现循环队列，但是在数组中对队列进行出队入队操作时，在出队时将队头指针后移，前方空间就无法使用，则造成了空间的浪费，入队时队尾指针移动，可能会将指针移至超出队列的范围，会造成溢出的情况。  
  所以要使用一些算法来解决上述问题。将循环队列中的存储问题分为以下几种情况：

front代表头指针，rear代表尾指针，queueSize代表数组大小
    1.队列满：
    		1). (rear+1)%queueSize = front (数组会少存储一个元素）
    		2). 使用count计数，count = queueSize 
    2. 队列空：front = rear
    3. 修改队头指针： front = (front+1)%queueSize
    4. 修改队尾指针：rear = (rear+1)%queueSize

## 2. 代码实现 ##

// 循环队列使用数组实现
    // 队列满：(rear + 1) % size = front 使用时少存储一个元素
    // 队头指针：front = (front + 1) % size
    // 队尾指针：rear = (rear + 1) % size
    
    typedef int DataType;
    
    typedef struct { 
    	DataType* data;
    	int front;
    	int rear;
    	int size;
    } MyCircularQueue;
    
    
    MyCircularQueue* myCircularQueueCreate(int k) { 
    	MyCircularQueue* mcq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    	if (NULL == mcq)
    	{ 
    		return NULL;
    	}
    
    	mcq->data = (DataType*)malloc(k * sizeof(DataType) + 1);
    	if (NULL == mcq->data)
    	{ 
    		return NULL;
    	}
    
    	mcq->front = mcq->rear = 0;
    	mcq->size = k + 1;
    
    	return mcq;
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) { 
    	if (obj->front == obj->rear)
    	{ 
    		return true;
    	}
    
    	return false;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) { 
    	if ((obj->rear + 1) % obj->size == obj->front)
    	{ 
    		return true;
    	}
    
    	return false;
    }
    
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { 
    	if (myCircularQueueIsFull(obj))
    	{ 
    		return false;
    	}
    
    	obj->rear = (obj->rear + 1) % obj->size;
    	obj->data[obj->rear] = value;
    	return true;
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj) { 
    	if (myCircularQueueIsEmpty(obj))
    		return false;
    
    	obj->front = (obj->front + 1) % obj->size;
    	return true;
    }
    
    int myCircularQueueFront(MyCircularQueue* obj) { 
    	return obj->data[obj->front];
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) { 
    	return obj->data[obj->rear];
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) { 
    	free(obj->data);
    	obj->data = NULL;
    }