头文件
- /*
- * my_queue.h
- *
- * Created on: Dec 3, 2018
- * Author: lgh
- */
- #ifndef INCLUDE_MY_QUEUE_H_
- #define INCLUDE_MY_QUEUE_H_
- #include <stdio.h>
- #include <malloc.h>
- /* 队列: 只允许在表的一端 (队尾 rear) 进行插入操作, 而在另一端 (队头 front) 进行删除操作的线性表
- * 插入操作简称为入队 删除操作简称为出队 队列具有先进先出的特点
- */
- /*===== 队列的入队, 出队示意图 ========
- *
- * 出队 ----------------- 入队
- * <--- a1,a2,a3,...,an <---
- * -----------------
- *
- *================================*/
- typedef enum
- {
- OK=0, // 正确
- ERROR=1, // 出错
- TRUE=2, // 为真
- FALSE=3 // 为假
- }status;
- typedef int ElemType; // 宏定义队列的数据类型
- #define MAX_SIZE 20
- /* 一, 使用数组存储队列的称为静态顺序队列
- * 二, 使用动态分配的指针的称为动态顺序队列 */
- // [这里的是动态顺序队列]
- typedef struct
- {
- ElemType *pBase; // 数组指针
- ElemType front; // 队头索引
- ElemType rear; // 队尾索引
- int maxSize; // 当前分配的最大容量
- }queue;
- // 创建空队列 queueCapacity - 队列容量
- status initQueue(queue *PQueue,int queueCapacity);
- // 销毁队列
- void destroyQueue(queue *PQueue);
- // 清空队列
- void clearQueue(queue *PQueue);
- // 判断队列是否为空
- status isEmpityQueue(queue *PQueue);
- // 判断队列是否为满
- status isFullQueue(queue *PQueue);
- // 获得队列长度
- int getQueueLen(queue *PQueue);
- // 新元素入队 [先进先出原则: 在队尾的位置插入] element - 要插入元素
- status enQueue(queue *PQueue,ElemType element);
- // 新元素出队, 同时保存出队的元素 [先进先出原则: 在队头的位置删除]
- status deQueue(queue *PQueue,ElemType *pElement);
- // 遍历队列
- void queueTraverse(queue *PQueue);
- #endif /* INCLUDE_MY_QUEUE_H_ */
源文件
- /*
- * my_queue.c
- *
- * Created on: Dec 3, 2018
- * Author: lgh
- */
- #include "my_queue.h"
- /* 队列: 只允许在表的一端 (队尾 rear) 进行插入操作, 而在另一端 (队头 front) 进行删除操作的线性表
- * 插入操作简称为入队 删除操作简称为出队 队列具有先进先出的特点
- */
- /*===== 队列的入队, 出队示意图 ========
- *
- * 出队 ----------------- 入队
- * <--- a1,a2,a3,...,an <---
- * -----------------
- *
- *================================*/
- // 创建队列 queueCapacity - 队列容量
- status initQueue(queue *PQueue,int queueCapacity)
- {
- // 给数组指针分配内存
- PQueue->pBase = (ElemType *)malloc(sizeof(ElemType)*queueCapacity);
- if(!PQueue->pBase)
- {
- printf("给数组指针分配内存失败 \ n");
- return ERROR;
- }
- PQueue->front = 0; // 最开始创建时, 队头索引为 0
- PQueue->rear = 0; // 最开始创建时, 队尾索引为 0
- PQueue->maxSize = queueCapacity;
- return OK;
- }
- // 销毁队列
- void destroyQueue(queue *PQueue)
- {
- free(PQueue); // 释放队列数组指针指向的内存
- PQueue = NULL; // 队列数组指针重新指向 NULL, 避免成为野指针
- }
- // 清空队列
- void clearQueue(queue *PQueue)
- {
- PQueue->front = 0; // 队头索引清 0
- PQueue->rear = 0; // 队尾索引清 0
- }
- // 判断队列是否为空
- status isEmpityQueue(queue *PQueue)
- {
- if( PQueue->front == PQueue->rear ) // 队头 == 队尾, 说明为空
- return TRUE;
- return FALSE;
- }
- /*
- * 在循环队列中,"队满" 和 "队空" 的条件有可能是相同的, 都是 front==rear,
- * 这种情况下, 无法区别是 "队满" 还是 "队空".
- * 针对这个问题, 有 3 种可能的处理方法:
- *(1)另设一个标志以区别是 "队满" 还是 "队空".(即入队 / 出队前检查是否 "队满"/"队空")
- *(2)设一个计数器, 此时甚至还可以省去一个指针.
- *(3)少用一个元素空间, 即约定队头指针在队尾指针的下一位置时就作为 "队满" 的标志,
- * 即 "队满" 条件为:(PQueue->rear+1)%MAX_SIZE == PQueue->front.
- * [这里采用了第 3 种处理方法]
- */
- // 判断队列是否为满
- status isFullQueue(queue *PQueue)
- {
- if( (PQueue->rear+1)%PQueue->maxSize == PQueue->front ) // 队列满
- return TRUE;
- return FALSE;
- }
- // 获得队列长度
- int getQueueLen(queue *PQueue)
- {
- // 正常情况下, 队列长度为队尾队头指针之差, 但如果首尾指针跨容量最大值时, 要 %
- return (PQueue->rear - PQueue->front + PQueue->maxSize)%PQueue->maxSize;
- }
- // 新元素入队 [先进先出原则: 在队尾的位置插入] element - 要插入元素
- status enQueue(queue *PQueue, ElemType element)
- {
- if(isFullQueue(PQueue)==TRUE)
- {
- printf("队列已满, 不能再插入元素了!\n");
- return FALSE;
- }
- // 向队列中添加新元素
- PQueue->pBase[PQueue->rear] = element;
- PQueue->rear = (PQueue->rear+1) % PQueue->maxSize; // 将 rear 赋予新的合适的值
- return TRUE;
- }
- // 新元素出队, 同时保存出队的元素 [先进先出原则: 在队头的位置删除]
- status deQueue(queue *PQueue,ElemType *pElement)
- {
- // 如果队列为空, 则返回 false
- if(isEmpityQueue(PQueue)==TRUE)
- {
- printf("队列为空, 出队失败!\n");
- return FALSE;
- }
- *pElement = PQueue->pBase[PQueue->front]; // 先进先出
- PQueue->front = (PQueue->front+1) % PQueue->maxSize; // 移到下一位置
- return TRUE;
- }
- // 遍历队列
- void queueTraverse(queue *PQueue)
- {
- int i = PQueue->front; // 从头开始遍历
- printf("遍历队列:\n");
- while(i != PQueue->rear) // 如果没有到达 rear 位置, 就循环
- {
- printf("%d", PQueue->pBase[i]);
- i = (i+1) % PQueue->maxSize; // 移到下一位置
- }
- printf("\n");
- }
- int main()
- {
- // 定义的指针必须分配动态内存空间;
- queue *pQueue=malloc(sizeof(queue));
- if(OK!=initQueue(pQueue,50))
- {
- printf("队列初始化失败.\n");
- return -1;
- }
- queueTraverse(pQueue);
- // 给队列赋值;
- int i;
- for(i=0;i<21;i++)
- {
- enQueue(pQueue,i);
- }
- queueTraverse(pQueue);
- // 进列;
- enQueue(pQueue,10);
- queueTraverse(pQueue);
- // 出列;
- ElemType *pElement=malloc(sizeof(ElemType));
- deQueue(pQueue,pElement);
- queueTraverse(pQueue);
- // 获取队列长度;
- int length=getQueueLen(pQueue);
- printf("length=%d\n",length);
- // 销毁队列;
- destroyQueue(pQueue);
- free(pElement);
- return 0;
- }
结果:
遍历队列:
遍历队列:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
遍历队列:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 10
遍历队列:
- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 10
- length=21
来源: http://www.bubuko.com/infodetail-2871855.html