【数据结构】—手把手带你用C语言实现栈和队列(超详细!)

这篇具有很好参考价值的文章主要介绍了【数据结构】—手把手带你用C语言实现栈和队列(超详细!)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络

                                  食用指南:本文在有C基础的情况下食用更佳 

                                 🔥这就不得不推荐此专栏了:C语言

                                 ♈️今日夜电波:Tell me —milet

                                               3:12 ━━━━━━️💟──────── 4:13                                                                                                                                     🔄   ◀️   ⏸   ▶️    ☰

                                💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍 


目录

🌸🌸后进先出—栈

什么是栈?

 什么是后进先出?

 栈的实现?

栈实现需要设置的参数 ?

 要实现的功能?

🌸栈的C语言代码实现

🌷初始化

🌷入栈

🌷判空

🌷 出栈

🌷取栈顶元素

🌷计算栈内数据个数 

🌷销毁栈

🌸栈的整体代码

头文件

函数实现

测试用例

💮💮先进先出—队列

什么是队列?

什么是先进先出? 

 队列的实现?

队列的实现需要设置的参数? 

 要实现的功能?

💮队列的C语言实现

🌼初始化

🌼入队列 

🌼判空 

🌼出队列 

🌼 取头节点元素

🌼取尾节点元素

🌼计算队列内数据个数

🌼销毁队列

💮队列的整体代码

头文件

函数实现

测试用例


后进先出—栈

什么是栈?

        栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

 什么是后进先出?

        一图让你明白~

【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络

 栈的实现?

        栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。但是由于数组是在定义完后对于空间是固定的,因此如果单纯用数组实现,如果申请空间过大会浪费空间,太小又会造成空间不够的问题,因此,本文采用支持动态增长的栈,也就是动态开辟空间的方法。

         对此,我们先了解一下咱们栈的操作

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。 

栈实现需要设置的参数 ?

        由于咱们要实现的是动态扩容因此定义如下:

// 支持动态增长的栈
typedef int STDataType;

typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

        此处对于相关栈所定义的元素进行解释:

       1、 STDataType* _a 作为动态扩容的作用。

        2、int _top 作为记录栈顶位置的作用。

        3、int _capacity 作为记录栈容量的作用。

啥意思呢?

         一图让你明白~

【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络

 要实现的功能?

        同我们之前所学的链表、线性表一样,需要实现基本的增、删、查、改!但是需要注意的是,我们的查与修只能在固定的一端进行!而不能进行改的操作!对此我们写出相应的接口函数。

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

栈的C语言代码实现

初始化

void StackInit(Stack* ps)
{
	assert(ps);

	ps->_a = NULL;

	ps->_capacity = 0;

	ps->_top = -1;
}

        注意:解释一下为什么这里top要设置成-1,主要是因为后续的操作中,比如:判空的操作的差异、在入栈时操作的差异,当然,top也可以设置成0,但后续的操作会有所差异。

入栈

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_capacity - 1 == ps->_top)//匹配上初始化top=-1
	{
		int newcap = ps->_capacity == 0 ? MAX : ps->_capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->_a, newcap*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->_capacity = newcap;
		ps->_a = tmp;
	}

	ps->_a[++ps->_top] = data;
}

        入栈时首先判断空间是否足够,如果不够则扩容,够则直接入栈

判空

int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->_top==-1;
}

 出栈

void StackPop(Stack* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));

	ps->_top--;
}

取栈顶元素

void StackPop(Stack* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));

	ps->_top--;
}

计算栈内数据个数 

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top+1;
}

销毁栈

void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;

}

栈的整体代码

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#define MAX 4
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 支持动态增长的栈
typedef int STDataType;

typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

函数实现

#include "stack.h"

void StackInit(Stack* ps)
{
	assert(ps);

	ps->_a = NULL;

	ps->_capacity = 0;

	ps->_top = -1;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_capacity - 1 == ps->_top)
	{
		int newcap = ps->_capacity == 0 ? MAX : ps->_capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->_a, newcap*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->_capacity = newcap;
		ps->_a = tmp;
	}

	ps->_a[++ps->_top] = data;
}

void StackPop(Stack* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));

	ps->_top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->_a[ps->_top];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top+1;
}

int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->_top==-1;
}

void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;

}

测试用例

#include"stack.h"

void test()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPop(&st);
	StackPush(&st, 4);
	StackPush(&st, 5);

	printf("%d\n", StackSize(&st));
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n%d\n", StackSize(&st));
	StackDestroy(&st);
}

int main()
{
	test();
	
	return 0;
}

测试结果:

【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络


先进先出—队列

什么是队列?

        队列只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。

什么是先进先出? 

        相信在前面了解过后进先出的你应该有一定的概念了,一图让你明白~

【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络

 队列的实现?

        队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。 

队列的实现需要设置的参数? 

        根据链表的定义如下:

typedef int QDataType;
// 链式结构:表示队列 

typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

        注意:QNode是基本的链表结构,而在QNode的基础上建立的Queue是作为真正的队列的结构,其中  _front 是作为记录队头位置的一个指针,而相应的  _rear 是作为记录队尾位置的一个指针。

        一图让你明了~ 

【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络

 要实现的功能?

        同我们之前所学的链表、线性表一样,需要实现基本的增、删、查、改!但是需要注意的是,增的操作在一端进行,而删的操作在另外一端进行,并且同栈一样不能进行改的操作!对此我们写出相应的接口函数。

// 初始化队列 
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);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

队列的C语言实现

初始化

void QueueInit(Queue* q)
{
	assert(q);

	q->_front = NULL;

	q->_rear = NULL;
}

        你可能有个问题?为什么需要将两个指针都置空呢?初始化指针是一方面,而最主要的是为了让两个指针在最开始都指向同一个位置然后头指针(也就是front)是只有在出队时才会移动的!尾指针(也就是rear)是只有在出队时才会移动的!这也是后续判空等操作的关键。

入队列 

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->_next = NULL;
	newnode->_data = data;

	if (q->_rear == NULL)
	{
		assert(q->_front == NULL);

		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
}

     入队列时需要判断头、尾指针是否为都为空,以此来确定是在头部插入还是在尾部插入。

判空 

int QueueEmpty(Queue* q)
{
	assert(q);

	return q->_front==NULL&&q->_rear==NULL;
}

        当头指针与尾指针都为空时,即该对列为空。

出队列 

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	if (q->_front == q->_rear)//一个节点
	{
		free(q->_front);
		q->_front = NULL;
		q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}

}

        出队列需要判断为一个节点还是多个节点的问题,一个节点则需要在释放空间的基础上再将两个指针置空,剩余多个则仅需将出队节点置空。

 取头节点元素

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)
{
	QNode* cur = q->_front;
	int size = 0;
	if (cur != NULL)
	{
		size++;
		while (cur != q->_rear)
		{
			size++;
			cur = cur->_next;
		}

	}	
		return size;
	
}

销毁队列

void QueueDestroy(Queue* q)
{
	assert(q);

	QNode* cur = q->_front;
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);

		cur = next;
	}
	q->_front = NULL;
	q->_rear = NULL;
}

队列的整体代码

头文件

#pragma once

#define _CRT_SECURE_NO_WARNINGS 01
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int QDataType;
// 链式结构:表示队列 

typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

// 初始化队列 
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);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

函数实现

#include "queue.h"

void QueueInit(Queue* q)
{
	assert(q);

	q->_front = NULL;

	q->_rear = NULL;
}

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->_next = NULL;
	newnode->_data = data;

	if (q->_rear == NULL)
	{
		assert(q->_front == NULL);

		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
}

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	if (q->_front == q->_rear)//一个节点
	{
		free(q->_front);
		q->_front = NULL;
		q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}

}

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)
{
	QNode* cur = q->_front;
	int size = 0;
	if (cur != NULL)
	{
		size++;
		while (cur != q->_rear)
		{
			size++;
			cur = cur->_next;
		}

	}	
		return size;
	
}

int QueueEmpty(Queue* q)
{
	assert(q);

	return q->_front==NULL&&q->_rear==NULL;
}

void QueueDestroy(Queue* q)
{
	assert(q);

	QNode* cur = q->_front;
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);

		cur = next;
	}
	q->_front = NULL;
	q->_rear = NULL;
}

测试用例

#include"queue.h"

void test()
{
	Queue qu;
	QueueInit(&qu);
	QueuePush(&qu, 1);
	QueuePush(&qu, 2);
	printf("%d\n", QueueBack(&qu));

	QueuePush(&qu, 3);
	QueuePush(&qu, 4);
	
	printf("%d\n", QueueSize(&qu));
	while(!QueueEmpty(&qu))
	{
		printf("%d ", QueueFront(&qu));
		QueuePop(&qu);
	}
	printf("\n%d\n", QueueSize(&qu));

	QueueDestroy(&qu);
}

int main()
{
	test();
	return 0;
}

测试结果:

【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络


                      感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o! 

                        ​​​​​​​                ​​​​​​​【数据结构】—手把手带你用C语言实现栈和队列(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表,学习,网络

                                                                           给个三连再走嘛~  文章来源地址https://www.toymoban.com/news/detail-631088.html

到了这里,关于【数据结构】—手把手带你用C语言实现栈和队列(超详细!)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构->顺序表实战指南,(手把手教会你拿捏数据结构顺序表)

    文章目录 ✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:橘橙黄又青-CSDN博客 今天开始我们正式进入数据结构的学习了,这篇简单了解一下: 线性表的存储结构:顺序存储结构、链式存储结构; 顺序表的定义:用一段物理地址连

    2024年01月25日
    浏览(60)
  • 数据结构->手把手教入门栈与列队(基础)

    ✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:橘橙黄又青-CSDN博客 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守 后

    2024年03月24日
    浏览(205)
  • 【初识数据结构】手把手教会你时间复杂度的计算方法

    前言   大家好啊,这里是幸麟 一名普通的大学牲 🧩希望可以不断的进步,因此也一直在学习 如果有写的不好或者写错的地方 欢迎在评论区指正 前言后的小前言 不知道在大家学习算法时有没有遇到这样一种情况,在看大佬题解或者讲解视频时 总能找到一个叫 时间复杂度

    2024年02月09日
    浏览(79)
  • 速学数据结构 | 手把手教你会单链表的构建方式

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 : 《初阶数据结构》《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊!今天给大家带来的是初阶数据结构中单链表的构建方式,手把手教会你单链表 !    ⛳️ 链表是指一种逻辑上是连在一

    2024年02月08日
    浏览(86)
  • 【图解数据结构】顺序表实战指南:手把手教你详细实现(超详细解析)

    🌈个人主页: 聆风吟 🔥系列专栏: 图解数据结构、算法模板 🔖少年有梦不应止于心动,更要付诸行动。 线性表(linear list):线性表是一种数据结构,由n个具有相同数据类型的元素构成一个有限序列。 线性表可以用数组、链表、栈等方式实现,常见的线性表有数组、链

    2024年01月22日
    浏览(59)
  • 【数据结构】万字一文手把手解读哈希————(开/闭散列)解决哈希冲突完整详解(6)

    前言 大家好吖,欢迎来到 YY 滴 数据结构 系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《

    2024年02月04日
    浏览(117)
  • 数据结构之链表 - 超详细的教程,手把手教你认识并运用链表

    顺序表只适合静态的查找和更新,不适合插入和删除元素, 因为在ArrayList中插入和删除元素时,由于需要将后序元素往前后者往后移动,所以时间复杂度会相当高,能达到O(N)。 为了解决这一问题,java 引入了 LinkedList(链表)。 链表是一种 逻辑上连续,物理上不连续 的存储结

    2024年02月09日
    浏览(56)
  • 数据结构:线性表————顺序表的实现、项目和OJ题目(手把手教你写代码)

    🌈 个人主页: 小新_- 🎈个人座右铭:“成功者不是从不失败的人,而是从不放弃的人!”🎈 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 🏆所属专栏:  话说那些与C++的爱恨情仇   欢迎订阅,持续更新中~~~                                           ✨让小新带着你

    2024年04月16日
    浏览(100)
  • 数据结构之栈和队列 - 超详细的教程,手把手教你认识并运用栈和队列

    栈:后进先出 队列:先进先出 栈:是一种特殊的 线性表 , 只允许在固定的一端插入或者删除元素 ,一个栈包含了栈顶和栈底。只能在栈顶插入或者删除元素。 栈的底层 是由 数组 实现的。 栈遵循先入后出原则,也就是先插入的元素得到后面才能删除,后面插入的元素比

    2024年02月07日
    浏览(78)
  • 手把手教你用YOLOv5算法训练数据和检测目标(不会你捶我)

    本人从一个小白,一路走来,已能够熟练使用YOLOv5算法来帮助自己解决一些问题,早就想分析一下自己的学习心得,一直没有时间,最近工作暂时告一段落,今天抽空写点东西,一是为自己积累一些学习笔记,二是可以为一些刚接触YOLOv5算法的小白们提供一些参考,希望大家

    2024年02月01日
    浏览(63)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包