1. Toy模板网首页
  2. > Toy博客

队列--C语言实现数据结构

6月前 作者：一个大不遛 分类：Toy博客 阅读(15) 违法举报

这篇具有很好参考价值的文章主要介绍了队列--C语言实现数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

本期带大家一起用C语言实现队列🌈🌈🌈

1、队列的概念

队列是一种线性数据结构，它按照先进先出（FIFO）的原则进行操作。可以把队列想象成排队买票或者排队上公交车的队伍。

顺序队列由一个连续的内存区域组成，可以存储多个元素。队列有两个指针，分别指向队头（Front）和队尾（Rear）。
链式队列由一系列节点构成，每个节点包含存储的元素值和指向下一个节点的指针
队列的基本操作包括：

  1. 入队（Enqueue）：将新元素插入到队尾，如果队列已满则无法插入。
  2. 出队（Dequeue）：移除队头元素，并返回该元素，如果队列为空则无法执行。
  3. 获取队头元素（Front）：获取队头元素的值，但不对队列进行修改。
  4. 判断队列是否为空（isEmpty）：判断队列中是否没有任何元素。
  5. 判断队列是否已满（isFull）：判断队列是否已经达到了最大容量。

队列的操作遵循先进先出的原则，即先入队的元素先出队。在队列中，新元素被插入到队列的末尾，而出队操作始终从队列的头部进行。

队列常用于需要顺序处理任务或数据的场景，例如处理请求、消息传递、广度优先搜索等算法实现。此外，队列还可以通过循环队列的方式来实现，使得已经出队的元素可以再次被插入到队列的末尾，有效地利用内存空间。

2、队列的操作流程

队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

3 、队列的结构

队列通常使用数组或链表来实现。以下是两种常见的队列结构：

  1. 基于数组的队列（顺序队列）：

    • 使用一个固定大小的数组来保存队列元素。
    • 需要维护队头和队尾的索引，分别指向队列的第一个元素和最后一个元素。
    • 入队操作将元素添加到队尾，并更新队尾索引。
    • 出队操作将队头元素移除，并更新队头索引。
    • 注意，入队操作可能导致队列满（队尾索引达到数组末尾）的情况，需要进行特殊处理。

  2. 基于链表的队列（链式队列）：

    • 使用链表来动态存储队列元素。
    • 需要维护队头和队尾节点指针，分别指向队列的第一个节点和最后一个节点。
    • 入队操作创建一个新节点，并将其链接到链表末尾，更新队尾指针。
    • 出队操作移除队头节点，并更新队头指针。
    • 注意，链式队列没有固定的大小限制，可以根据需要动态调整。

无论是基于数组还是链表的队列，其核心思想都是维护队头和队尾指针，并通过头部和尾部的插入和删除操作实现先进先出的特性。根据具体的应用场景和需求，选择适合的队列实现方式

在这里我们使用链表来实现队列，避免了用数组队列更新队头数据的遍历，时间复杂度低

4、队列的实现

4.1 队列的结构设计

Queue结构体，它表示整个队列。该结构体包含两个指针成员head和tail，分别指向队列的头部节点和尾部节点
QNode的结构体，它表示队列中的节点。该结构体包含一个指向下一个节点的指针next，以及一个数据data

typedef int QDataTYpe;

typedef struct QueueNode
{
	struct QueueNode* next;

	QDataTYpe data;
}QNode;

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

4.2 队列的初始化

现在主函数当中创建了一个Queue q
然后传入q的地址，进行初始化
将队列的头部指针和尾部指针设为NULL，并将队列的大小初始化为0

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

	pq->size = 0;
}

4.3 入队

在函数内部，首先进行断言assert(pq)来确保指针pq不为空。

然后，通过动态内存分配malloc来创建一个新的节点newnode，并将其类型转换为QNode*。

接下来，检查是否成功分配内存，如果分配失败，则输出错误信息并返回。

然后，将新节点的数据成员data赋值为传入的参数x，同时将新节点的下一个指针next设置为NULL，新节点表示当前节点是队列的尾部节点。

接着，根据队列是否为空，有两种情况处理：

  • 如果队列为空，即头部指针head为NULL，表示当前队列没有任何节点，此时将头部指针和尾部指针都指向新节点newnode。
  • 如果队列不为空，即头部指针head不为NULL，表示当前队列已存在节点，此时将队列尾部节点的下一个指针next指向新节点newnode，然后将尾部指针tail更新为新节点newnode
  • 最后，将队列的大小size加1，表示新增了一个节点。
队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习 
void QueuePush(Queue* pq,QDataTYpe x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));;

	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;

		pq->tail = newnode;
	}
	pq->size++;

}

4.4 判断队列是否为空

判断队列是否为空的话，相对来说是比较简单的
有两种判断方法
根据队列的头指针是否为空判断
根据队列当中的数据个数size判断

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

4.5 出队

出队列的话我们需要先判断当前队列是否为空
队列为空的话那我们就直接返回
队列不为空的话又分两种情况
1、队头指针==队尾指针

2、队头指针！=队尾指针
队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习 
void QueuePop(Queue* pq)
{
	assert(pq);

	if (QueueEmpty(pq))
	{
		printf("队列为空\n");
		return;
	}

	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;

	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

4.6 获取队头数据

获取队头数据的话，需要先判断队列是否为空，为空的话就直接返回
队列不为空，返回队头数据

QDataTYpe QueueFront(Queue* pq)
{
	assert(pq);

	if (QueueEmpty(pq))
	{
		printf("队列为空\n");
		return;
	}

	else
		return pq->head->data;
}

4.7 获取队尾数据

获取队尾数据的话，同样需要判断队列是否为空，为空的话也就直接返回
队列不为空的话，返回队尾数据

QDataTYpe QueueBack(Queue* pq)
{
	assert(pq);

	if (QueueEmpty(pq))
	{
		printf("队列为空\n");
		return;
	}
	else
		return pq->tail->data;
}

4.8 获取队列当中数据的个数

获取队列数据的个数，直接返回pq->size

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

4.9 队列的销毁

使用循环遍历队列中的所有节点，直到遍历到最后一个节点，即当前节点为NULL


void QueueDestroy(Queue* pq)
{

	assert(pq);

	QNode* cur = pq->head;

	while (cur != NULL)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;

	}

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;

}

5、栈和队列OJ题

5.1 队列模拟栈

队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

使用两个队列来实现栈的重点在于以下几点：

  1. 始终保持一个队列为空，另一个队列非空。
  2. 入数据时，将元素入队到不为空的队列中。
  3. 出数据时，将非空队列中的元素转移到空队列中，直到队列中只剩下一个元素。
  4. 出队原先非空队列的数据，原先非空队列变为空，即可实现栈的后进先出操作。

通过将元素入队到非空队列、转移到空队列以及出队的操作，可以模拟栈的后进先出特性

队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

typedef int QDataTYpe;

typedef struct QueueNode
{
	struct QueueNode* next;

	QDataTYpe data;
}QNode;

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



void QueueInit(Queue* pq);


void QueueDestroy(Queue* pq);

void QueuePush(Queue* pq,QDataTYpe x);

void QueuePop(Queue* pq);

bool QueueEmpty(Queue* pq);

QDataTYpe QueueFront(Queue* pq);

QDataTYpe QueueBack(Queue* pq);

int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
	pq->head = NULL;
	pq->tail = NULL;

	pq->size = 0;
}


void QueueDestroy(Queue* pq)
{

	assert(pq);

	QNode* cur = pq->head;

	while (cur != NULL)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;

	}

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;

}


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


void QueuePush(Queue* pq,QDataTYpe x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));;

	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;

		pq->tail = newnode;
	}
	pq->size++;

}


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

	if (QueueEmpty(pq))
	{
		printf("队列为空\n");
		return;
	}

	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;

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




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;
}


int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}


typedef struct {
    Queue q;
    Queue p;
} MyStack;


MyStack* myStackCreate() {
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
    {
        return NULL;
    }
    QueueInit(&obj->p);
    QueueInit(&obj->q);
		return obj;
}

void myStackPush(MyStack* obj, int x) {

    if(QueueEmpty(&obj->p))
    {
        QueuePush(&obj->q,x);
    }
    else
    {
        QueuePush(&obj->p,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue*Empty=&obj->q;
    Queue*NoEmpty=&obj->p;
    if(QueueEmpty(&obj->p))
    {
        Empty=&obj->p;
        NoEmpty=&obj->q;
    }

    while(QueueSize(NoEmpty)>1)
    {
        QueuePush(Empty,QueueFront(NoEmpty));

        QueuePop(NoEmpty);
    }

    int top=QueueFront(NoEmpty);
    QueuePop(NoEmpty);
    return top;
}

int myStackTop(MyStack* obj) {
    if(QueueEmpty(&obj->p))
    {
        return QueueBack(&obj->q);
    }
    else
    return QueueBack(&obj->p);
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q)&&QueueEmpty(&obj->p);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q);
    QueueDestroy(&obj->p);
    free(obj);
}

5.2 栈模拟队列

栈模拟队列
队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习
栈模拟队列的话，可以想象成一个连通器
队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习



typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;


//初始化
void STInit(ST* ps);

//销毁
void STDestroy(ST* ps);

//压栈

void STPush(ST* ps,STDataType x);


//出栈

void STPop(ST* ps);

//判空

bool STEmpty(ST* ps);

//栈顶

STDataType STTop(ST* ps);

//个数

int STSize(ST* ps);



void STInit(ST* ps)
{

	assert(ps);

	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}


void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;

	ps->top = 0;
}




void STPush(ST* ps,STDataType x)
{

	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));

		if (tmp == NULL)
		{
			perror("realloc :fail");
			return;
		}

		ps->a = tmp;

		ps->capacity = newcapacity;

	}
	ps->a[ps->top++] = x;

}

bool STEmpty(ST* ps)
{

	return ps->top == 0;
}

void STPop(ST* ps)
{

	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}


STDataType STTop(ST* ps)
{

	assert(ps);

	return ps->a[ps->top - 1];

}


int STSize(ST* ps)
{
	assert(ps);

	return  ps->top;

}



typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
    
    
}

void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->pushst,x);

}

int myQueuePop(MyQueue* obj) {
    int ret=myQueuePeek(obj);
    STPop(&obj->popst);
    return ret;
   
}

int myQueuePeek(MyQueue* obj) {
     if(STEmpty(&obj->popst))
    {
        while(!(STEmpty(&obj->pushst)))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushst);
        STDestroy(&obj->popst);

    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

5.3 循环队列

循环队列
队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习
解决循环队列问题的话
我们可以先定义固定大小的数组，用来存储元素
例如，我们需要一个可以存储3个数据的数组，我们现在就开辟4个数据的空间，以便于我们操作队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习




typedef struct {
    int front;
    int rear;
    int size;
    int *a;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj) ;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->size=k+1;
    obj->front=0;
    obj->rear=0;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
   if((obj->rear+1)%(obj->size)==obj->front)
   return false;
   obj->a[obj->rear]=value;
   obj->rear++;
   obj->rear%=obj->size;
   return true;
}

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

int myCircularQueueFront(MyCircularQueue* obj) {
    if(obj->rear==obj->front)
    return -1;
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(obj->rear==obj->front)
    return -1;
    

    return obj->a[(obj->rear-1+obj->size)%obj->size];

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->rear==obj->front)
    return true;
    return false;
}

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

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->a=NULL;
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

6、感谢与交流✅

🌹🌹🌹如果大家通过本篇博客收获了,对队列有了新的了解的话
那么希望支持一下哦如果还有不明白的，疑惑的话，或者什么比较好的建议的话，可以发到评论区，
我们一起解决，共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯

队列--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习文章来源地址https://www.toymoban.com/news/detail-563596.html

到了这里，关于队列--C语言实现数据结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 队列（C语言实现）

    数据结构 队列（C语言实现）

            任其事必图其效；欲责其效，必尽其方。——欧阳修；本篇文章主要写的是什么是队列、以及队列是由什么组成的和这些组成接口的代码实现过程。（ 大多细节的实现过程以注释的方式展示请注意查看 ）    话不多说安全带系好，发车啦 （建议电脑观看） 。 附

    2024年02月11日
    浏览(23)
  • C语言实现队列--数据结构

    C语言实现队列--数据结构

    😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️ 💥个人主页：🔥🔥🔥大魔王🔥🔥🔥 💥所属专栏：🔥魔王的修炼之路–数据结构🔥 如果你觉得这篇文章对你有帮助，请在文章结尾处留下你的 点赞 👍和 关注 💖，支持一

    2024年02月05日
    浏览(24)
  • 队列--C语言实现数据结构

    队列--C语言实现数据结构

    本期带大家一起用C语言实现队列🌈🌈🌈 队列是一种线性数据结构，它按照先进先出（FIFO）的原则进行操作。可以把队列想象成排队买票或者排队上公交车的队伍。 顺序队列 由一个连续的内存区域组成，可以存储多个元素。队列有两个指针，分别指向队头（Front）和队尾（

    2024年02月16日
    浏览(15)
  • 数据结构——队列（C语言实现）

    数据结构——队列（C语言实现）

    队列是一种特殊的线性结构，数据只能在一端插入，数据也只能在另一端进行删除。插入数据的那一端称之为队尾，插入数据的动作称之为入队。删除数据的那一端称之为队头，删除数据的动作称之为出列。队列遵守的是FIFO原则（Frist In First Out），即先进先出原则。 队列具

    2024年02月03日
    浏览(35)
  • 数据结构：队列（Python语言实现）

    数据结构：队列（Python语言实现）

    队列是一种 先进先出 的数据结构（特殊的线性结构），在队列 尾部 插入新元素，在队列 头部 删除元素。 一般队列的基本操作如下： create：创建空队列。 enqueue：将新元素加入队列的尾部，返回新队列。 dequeue：删除队列头部元素，返回新队列。 front：返回队列头部的元素

    2024年02月13日
    浏览(18)

  • 【C/C++数据结构与算法】C语言栈与队列

    目录 一、栈 二、队列 三、循环队列 特性： 顺序存储，后进先出 优点是可随机访问，尾部增删效率高 缺点是可能会浪费空间，不知道头部增删 特性： 链式存储，先进先出 优点是无空间浪费，头部增删效率高 缺点是不能随机访问，尾部增删效率低 特性： 顺序存储，先进先

    2024年02月09日
    浏览(34)
  • C数据结构与算法——队列 应用（C语言纯享版 迷宫）

    C数据结构与算法——队列 应用（C语言纯享版 迷宫）

    实验任务 (1) 掌握顺序循环队列及其C语言的表示； (2) 掌握入队、出队等基本算法的实现； (3) 掌握顺序循环队列的基本应用（求解迷宫通路）。 实验内容 使用C语言实现顺序循环队列的类型定义与算法函数； 编写main()函数并根据需要修改、补充相关的类型定义与函数，以实

    2024年02月15日
    浏览(23)
  • 【数据结构与算法】队列的实现

    【数据结构与算法】队列的实现

    🌠 作者：@ 阿亮joy. 🎆 专栏：《数据结构与算法要啸着学》 🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先

    2024年02月07日
    浏览(29)
  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者：@ 阿亮joy. 🎆 专栏：《数据结构与算法要啸着学》 🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、

    2024年01月20日
    浏览(24)
  • 【一起学习数据结构与算法】优先级队列(堆)

    【一起学习数据结构与算法】优先级队列(堆)

    如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了 优先级队列 这种数据结构。 优先级队列（priority queue） 是0个或多个元素的集

    2024年01月19日
    浏览(25)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包