队列
目录
队列
队列的定义
队列的分类
顺序队列
1.创建队列
2.销毁队列
3.入队
4.出队
5.判断队空
6.获得队长
7.获得队首元素
链式队列
1.创建队列
2.销毁队列
3.入队
4.出队
5.判断队空
6.获得队长
7.获得队首元素
队列的定义
在 C 语言中，队列（Queue）是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作。
以下是一个简单的队列定义：
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int front;int rear;} Queue;在这个定义中：
- data 数组用于存储队列中的元素。
- front 表示队列的前端，用于删除元素。
- rear 表示队列的后端，用于插入元素。
队列具有以下特点：
- 先进先出（FIFO）：先进入队列的元素先被取出。
- 当队列满时，不能再进行插入操作；当队列空时，不能再进行删除操作。
操作队列的主要函数通常包括：
- enqueue ：将元素插入队列后端。
- dequeue ：从队列前端删除元素并返回该元素。
- isFull ：判断队列是否已满。
- isEmpty ：判断队列是否为空。
队列的分类
队列主要有以下分类：
一、单向队列
1. 普通队列：遵循先进先出原则，在一端进行入队操作，另一端进行出队操作。
2. 优先队列：元素具有优先级，优先级高的元素先出队。
二、双向队列
可以在两端进行入队和出队操作，更加灵活。例如在某些场景下，可以从一端快速插入新元素，同时从另一端快速取出旧元素。
三、循环队列
把队列的头尾连接起来，形成一个环形。这样可以有效地利用存储空间，避免队列在进行大量入队和出队操作后出现“假满”或“假空”的情况。当队尾指针到达队列末尾时，如果还有空间可以继续循环到队列开头进行插入操作。
顺序队列
1.创建队列
LinkQueue *CreateLinkQueue()
{LinkQueue* lq = malloc(sizeof(LinkQueue));if(NULL == lq){perror("createlinkque error");return NULL;}lq->head= NULL;lq->tail=NULL;lq->clen=0;return lq;
}2.销毁队列
int DestroyLinkQueue(LinkQueue *queue)
{int len = GetSizeLinkQueue(queue);int i = 0 ;for(i = 0 ;i<len;i++){QuitLinkQueue(queue);}free(queue);return 0;
}3.入队
int EnterLinkQueue(LinkQueue *queue, DATATYPE *data)
{QueueNode* newnode = malloc(sizeof(QueueNode));if(NULL == newnode){perror("enterqueue error");return 1;}memcpy(&newnode->data,data,sizeof(DATATYPE));newnode->next= NULL;if(IsEmptyLinkQueue(queue)){queue->head = newnode;queue->tail= newnode;}else {queue->tail->next = newnode;queue->tail = newnode; }queue->clen++;return 0;
}4.出队
int QuitLinkQueue(LinkQueue *queue)
{if(IsEmptyLinkQueue(queue)) {return 1;}QueueNode* tmp = queue->head;queue->head = queue->head->next;if(NULL ==queue->head){queue->tail= NULL;}free(tmp);queue->clen--;return 0;}5.判断队空
int IsEmptyLinkQueue(LinkQueue *queue)
{return 0 == queue->clen;
}6.获得队长
int GetSizeLinkQueue(LinkQueue*que)
{return que->clen;
}7.获得队首元素
DATATYPE* GetHeadLinkQueue(LinkQueue* que)
{if(IsEmptyLinkQueue(que)){return NULL;}return &que->head->data;
}链式队列
1.创建队列
LinkQueue *CreateLinkQueue()
{LinkQueue* lq = malloc(sizeof(LinkQueue));if(NULL == lq){perror("createlinkque error");return NULL;}lq->head= NULL;lq->tail=NULL;lq->clen=0;return lq;
}2.销毁队列
int DestroyLinkQueue(LinkQueue *queue)
{int len = GetSizeLinkQueue(queue);int i = 0 ;for(i = 0 ;i<len;i++){QuitLinkQueue(queue);}free(queue);return 0;
}3.入队
int EnterLinkQueue(LinkQueue *queue, DATATYPE *data)
{QueueNode* newnode = malloc(sizeof(QueueNode));if(NULL == newnode){perror("enterqueue error");return 1;}memcpy(&newnode->data,data,sizeof(DATATYPE));newnode->next= NULL;if(IsEmptyLinkQueue(queue)){queue->head = newnode;queue->tail= newnode;}else {queue->tail->next = newnode;queue->tail = newnode; }queue->clen++;return 0;
}4.出队
int QuitLinkQueue(LinkQueue *queue)
{if(IsEmptyLinkQueue(queue)) {return 1;}QueueNode* tmp = queue->head;queue->head = queue->head->next;if(NULL ==queue->head){queue->tail= NULL;}free(tmp);queue->clen--;return 0;}5.判断队空
int IsEmptyLinkQueue(LinkQueue *queue)
{return 0 == queue->clen;
}6.获得队长
int GetSizeLinkQueue(LinkQueue*que)
{return que->clen;
}7.获得队首元素
DATATYPE* GetHeadLinkQueue(LinkQueue* que)
{if(IsEmptyLinkQueue(que)){return NULL;}return &que->head->data;
}
