数据结构C语言版——队列+循环队列实现-创新互联

文章目录

队列
- 1.概念
- 2. 生活中队列应用
- 3. 队列的实现
- - 初始化队列
  - 入队列
  - 出队列
  - 获取队头元素
  - 获取队尾元素
  - 获取队列中元素个数
  - 判断队列是否为空
  - 销毁队列
- 2. 循环队列

创新互联建站专注于成安网站建设服务及定制，我们拥有丰富的企业做网站经验。热诚为您提供成安营销型网站建设，成安网站制作、成安网页设计、成安网站官网定制、重庆小程序开发服务，打造成安网络公司原创品牌,更为您提供成安网站排名全网营销落地服务。

队列 1.概念

和栈相反，队列(queue)是一种先进先出的线性表，它只允许在一端进行插入，而在另一端被删除。这和生活中的排队是类似的，最先排队的最先离开。在队列中运行被插入的一端叫做队尾，允许被删除的一端叫做队尾。

在这里插入图片描述

2. 生活中队列应用

比如我们去银行办理业务的时候需要去抽号机器上取一个号码，这起始就是队列的应用。每当有一个人取号后机器就会把这个号码入队列进行排队。等窗口工作人员进行叫号办理业务。

在这里插入图片描述

3. 队列的实现

队列可以用数组或者链表实现，使用链表实现会更加合适一些，因为如果使用数组实现在出队的时候效率会比较低。

队列的定义

因为是链表实现所以还要定义一个节点结构体，队列的结构题包含两个指针一个队头指针和一个队尾指针

typedef int QDataType;

typedef struct QListNode {QDataType data;
	struct QListNode* next;//下一个节点
}QNode;

typedef struct Queue
{QNode* front;//队头
	QNode* rear;//队尾
}Queue;

// 初始化队列
void QueueInit(Queue* q);
// 动态申请节点
QNode* BuyQNode(QDataType data);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

初始化队列

初始化队列比较简单，让队头和队尾指向NULL，因为此时队列里没有任何元素。

// 初始化队列
void QueueInit(Queue* q)
{assert(q);
	q->front = NULL;
	q->rear = NULL;
}

因为这是链表实现所以还要定义个动态申请节点的函数

// 动态申请节点
QNode* BuyQNode(QDataType data)
{QNode* node = (QNode*)(malloc(sizeof(QNode)));
	if (node == NULL)
	{printf("申请失败\n");
		exit(-1);
	}
	node->data = data;
	node->next = NULL;
	return node;
}

入队列

入队列需要考虑两种情况，第一种是队列为空的情况，队列为空要把队头和队尾指针都指向第一个元素，其他情况只需要把节点插入到队尾指针后面，再让对队尾指针往后走即可。

// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);
	QNode* node = BuyQNode(data);
	if (q->front == NULL)
	{q->front = node;
		q->rear = node;
	}
	else
	{q->rear->next = node;
		q->rear = q->rear->next;
	}
}

出队列

出队列要考虑到队列是否为空，为空是不能进行出队列操作的。出队列只需要让队头指针往后走，再释放队头节点。

// 队头出队列
void QueuePop(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	QNode* cur = q->front;
	q->front = q->front->next;
	free(cur);
}

获取队头元素

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->front->data;
}

获取队尾元素

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->rear->data;
}

获取队列中元素个数

和链表求长度是一样的

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);

	QNode* cur = q->front;
	int count = 0;
	while (cur != NULL)
	{count++;
		cur = cur->next;
	}
	
	return count;
}

判断队列是否为空

当队头指向NULL时说明队列为空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);
	
	return q->front == NULL;
}

销毁队列

销毁队列遍历一边队列，把每个节点给释放掉。

// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);
	QNode* cur = q->front;
	while (cur != NULL)
	{q->front = cur->next;
		free(cur);
		cur = q->front;
	}
	q->front = NULL;
	q->rear = NULL;
}

2. 循环队列

循环队列也是一种队列，再队列的顺序存储结构中，除了用一组连续的存储单元依次存放队头到队尾元素外，还需要两指针 front 和 rear 分别指向队头和队尾。

在这里插入图片描述

我们约定，初始化空队列时，让 front 和 rear 都赋为0，也就是指向数组的0下标。每当插入元素时尾指针加1，每当删除元素时头指针加1。

因为这时一个循环队列，当 f r o n t = = r e a r front == rear front==rear时，无法判断循环是满还是空。所以可以有两种选择，一种是做一个标记判断是否为满了，而是创建队列的时候多开一个空间，浪费掉这个空间方便判断。

我们采用第二种方式，约定 f r o n = = r e a r fron == rear fron==rear表示队列为空， r e a r + 1 = = f r o n rear+1 == fron rear+1==fron表示队列满了。

还有一个问题就是这是一个循环队列，当尾指针走到最后一个位置时如何走到下标为0的位置，我们可以巧妙的用一个公式，假设队列大小为 size。

头指针向后走： ( f r o n + 1 ) % s i z e (fron+1)\%size (fron+1)%size

尾指针向后走： ( r e a r + 1 ) % s i z e (rear + 1)\%size (rear+1)%size

在这里插入图片描述

代码实现

typedef struct {int* arr;
    int front;
    int rear;
    int size;//容量
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* QUeue(int k) {MyCircularQueue* obj = (MyCircularQueue*)(malloc(sizeof(MyCircularQueue)));

    //创建容量为k+1大小的队列，浪费1个空间
    obj->arr = (int*)(malloc(sizeof(int)*(k+1)));
    obj->front = 0;
    obj->rear = 0;
    obj->size = k+1;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj) == true)
    {return false;//满了
    }
    else
    {obj->arr[obj->rear] = value;
        obj->rear = (obj->rear+1) % (obj->size);
        return true;
    }

    
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
    {return false;
    }
    else
    {obj->front = (obj->front+1) % (obj->size);
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj) == true)
    {return -1;
    }
    return obj->arr[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
    {return -1;
    }
    return (obj->rear == 0) ? (obj->arr[obj->size-1]) : (obj->arr[obj->rear-1]);
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//约定 头位相遇就是空，尾+1是头就是满
    if (obj->front == obj->rear)
    {return true;
    }
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {//约定 头位相遇就是空，尾+1是头就是满
    if (((obj->rear)+1)%obj->size == (obj->front))
    {return true;
    }
    return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);
    obj->front = NULL;
    obj->rear = NULL;
    free(obj);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：数据结构C语言版——队列+循环队列实现-创新互联
文章地址：http://cqcxhl.com/article/dsdhcp.html

重庆分公司，新征程启航

数据结构C语言版——队列+循环队列实现-创新互联

其他资讯