C语言实现队列
1.队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out).
入队列:进行插入操作的一端称为队尾。
出队列:进行删除操作的一端称为队头。
2.队列的实现
队列也可以用数组和链表的结构实现,使用链表的结构更优一点,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
2.1队列的结构
// 链式结构:表示队列中每个节点的结构
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构,用两个指针来维护一个队列
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
2.2头文件Queue.h
//Queue.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
// 链式结构:表示队列中每个节点的结构
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构,用两个指针来维护一个队列
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
void QPrint(Queue* q);
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
2.3函数实现文件Queue.c
2.3.1初始化和销毁
2.3.1.1初始化
函数实现:
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->_front = q->_rear = NULL;
}
2.3.1.2销毁
函数实现:
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur)
{
QNode* next = cur->_pNext;
free(cur);
cur = next;
}
q->_front = q->_rear = NULL;
}
2.3.2入队列和出队列
2.3.2.1队尾入队列
函数实现:
// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);
//创建一个节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!\n");
exit(1);
}
newnode->_data = x;
newnode->_pNext = NULL;
if (q->_front == NULL)
{
q->_front = q->_rear = newnode;
}
else
{
q->_rear->_pNext = newnode;
q->_rear = newnode;
}
}
打印函数:
//打印
void QPrint(Queue* q)
{
QNode* cur = q->_front;
while (cur)
{
printf("%d ", cur->_data);
cur = cur->_pNext;
}
printf("\n");
}
测试代码:
#include "Queue.h"
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QPrint(&q);
QueueDestroy(&q);
}
int main()
{
test();
return 0;
}
2.3.2.2队头出队列
函数实现:
// 队头出队列
void QueuePop(Queue* q)
{
assert(q && q->_front);
//只有一个节点,删除后尾节点需要修改为NULL
if (q->_front->_pNext == NULL)
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* newphead = q->_front->_pNext;
free(q->_front);
q->_front = newphead;
}
}
测试代码:
#include "Queue.h"
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePop(&q);
QueuePop(&q);
QPrint(&q);
QueueDestroy(&q);
}
int main()
{
test();
return 0;
}
2.3.3获取队列头部尾部元素
2.3.3.1获取队列头部元素
函数实现:
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q && q->_front); //断言首元素不能为空
return q->_front->_data;
}
2.3.3.2获取队列尾部元素
函数实现:
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q && q->_rear); //断言尾元素不能为空
return q->_rear->_data;
}
测试代码:
#include "Queue.h"
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QPrint(&q);
printf("%d\n",QueueFront(&q));
printf("%d\n", QueueBack(&q));
QueueDestroy(&q);
}
int main()
{
test();
return 0;
}
2.3.4 获取队列中有效元素个数
函数实现:
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
QNode* cur = q->_front;
int count = 0;
while (cur)
{
count++;
cur = cur->_pNext;
}
return count;
}
测试代码:
#include "Queue.h"
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QPrint(&q);
printf("%d\n", QueueSize(&q));
QueueDestroy(&q);
}
int main()
{
test();
return 0;
}
2.3.5检测队列是否为空
函数实现:
// 检测队列是否为空
int QueueEmpty(Queue* q)
{
assert(q);
if (q->_front == NULL)
{
return 0;
}
else
{
return -1;
}
}
测试代码:
#include "Queue.h"
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QPrint(&q);
int i = QueueEmpty(&q);
if (i == 0)
{
printf("队列为空!\n");
}
else
{
printf("队列不为空!\n");
}
QueueDestroy(&q);
}
int main()
{
test();
return 0;
}
2.4 参考代码
//Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
// 链式结构:表示队列中每个节点的结构
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构,用两个指针来维护一个队列
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
void QPrint(Queue* q);
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
//Queue.c
#include "Queue.h"
//打印
void QPrint(Queue* q)
{
QNode* cur = q->_front;
while (cur)
{
printf("%d ", cur->_data);
cur = cur->_pNext;
}
printf("\n");
}
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->_front = q->_rear = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);
//创建一个节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!\n");
exit(1);
}
newnode->_data = x;
newnode->_pNext = NULL;
if (q->_front == NULL)
{
q->_front = q->_rear = newnode;
}
else
{
q->_rear->_pNext = newnode;
q->_rear = newnode;
}
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q && q->_front);
//只有一个节点,尾节点需要修改
if (q->_front->_pNext == NULL)
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else
{
QNode* newphead = q->_front->_pNext;
free(q->_front);
q->_front = newphead;
}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q && q->_front);
return q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q && q->_rear);
return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
QNode* cur = q->_front;
int count = 0;
while (cur)
{
count++;
cur = cur->_pNext;
}
return count;
}
// 检测队列是否为空
int QueueEmpty(Queue* q)
{
assert(q);
if (q->_front == NULL)
{
return 0;
}
else
{
return -1;
}
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur)
{
QNode* next = cur->_pNext;
free(cur);
cur = next;
}
q->_front = q->_rear = NULL;
}
//test.c
#include "Queue.h"
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//QueuePop(&q);
//QueuePop(&q);
QPrint(&q);
//printf("%d\n",QueueFront(&q));
//printf("%d\n", QueueBack(&q));
//printf("%d\n", QueueSize(&q));
int i = QueueEmpty(&q);
if (i == 0)
{
printf("队列为空!\n");
}
else
{
printf("队列不为空!\n");
}
QueueDestroy(&q);
}
int main()
{
test();
return 0;
}
原文地址:https://blog.csdn.net/CSQCSQCC/article/details/140292445
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!