数据结构初阶之队列(C语言实现)

数据结构初阶之队列(C语言实现),第1张

队列的定义查一下百度百科就可以,很简单,本文只谈顺序队列,不涉及循环队列。

队列(常用数据结构之一)_百度百科

文章主要目的是为了用链表的形式实现队列常用的接口函数,一般有初始化,销毁,队尾插入,删除队头,返回队头,返回队尾,判空和返回当前队列元素个数。

首先先给出队列元素的定义和整个队列的形式

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	
	QNode* head;
	QNode* tail;
}Queue;

初始化

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

销毁

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
        cur=next;
	}

	pq->head = pq->tail = NULL;
}

队尾插入

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

删除队头

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	// 
	// 
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

返回队头

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

返回队尾

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

判空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

返回当前队列元素个数

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	int size = 0;
	while (cur)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

队列也是相对而言比较简单的,但是这里的OJ题并不简单,准确地说使用C语言实现并不简单,接下来会更新关于栈和队列地相互实现以及循环队列的OJ题。

欢迎分享,转载请注明来源:内存溢出

原文地址:http://outofmemory.cn/langs/921869.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-05-16
下一篇2022-05-16

随机推荐

发表评论

登录后才能评论

评论列表(0条)

    保存