数据结构-栈和队列（一）

目录

1.栈

1.1 栈的概念及结构

1.2 栈的实现

初始化栈：

入栈：

判空函数：

出栈：

获取栈顶元素：

获取栈中有效元素的个数：

销毁栈：

完整代码：

测试：

2. 队列

2.1 队列的概念及结构

2.2 队列的实现

队列的初始化：

队尾入队列：

判空函数：

队头出队列：

获取队列头部元素：

获取队列尾部元素：

获取队列中有效元素个数：

销毁队列：

 完整代码：

测试：

1.栈

1.1 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

数据进栈出栈遵循后进先出的原则：

下面看两道例题：

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA 

答案是B。

2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1

答案是C。

这道题说可以在进栈的过程中出栈，ABD不用说，只有C，先出栈的是3，说明此时栈里面1和2肯定还在，而1不可能在2之前出栈，所以选C。

1.2 栈的实现

实现栈有两种方式，一种是数组栈，一种是链式栈：

这里我们采用数组栈，因为数组在尾插的代价比较小。

首先，我们来定义一个结构体：

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;//栈顶元素位置
	int capacity;//容量
}ST;

下面我们来实现栈：

初始化栈：

初始化很简单，但要注意断言pst是否为空。（pst是结构体变量的地址，永远不为空，所以需要断言）

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//指向栈顶元素的下一个位置
	pst->capacity = 0;
}

入栈：

入栈时，我们要为栈开辟空间，然后才能插入数据。由于只有入栈需要开辟空间，所以这里我们并没有封装开辟空间的函数，直接在入栈函数里面开辟空间就行。

当pst->top=pst->capacity=0时，说明此时还没有就开辟空间，所以我们给它开辟4个字节大小。下次再进去，不等于0，空间就增容到上次的2倍。

void STPush(ST* pst, STDatatype x)
{
	//开辟空间
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity = 0 ? 4 : (pst->capacity) * 2;
		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//插入
	pst->a[pst->top] = x;
	pst->top++;
}

判空函数：

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

出栈：

出栈只需要将pst->top--即可，但是注意要断言此时的栈不能为空。

STEmpty函数是用来判断栈是否为空，它的返回值类型是bool型，bool型返回true或false，当pst->top=0时，说明此时栈为空，返回true，取反!true为假，断言报错。

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}

获取栈顶元素：

直接返回栈顶元素即可，pst->top是栈顶元素的下一个位置，所以要返回pst->top-1处的值。

STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}

获取栈中有效元素的个数：

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

销毁栈：

因为是数组栈，所以直接free数组名即可。

void STDestory(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

完整代码：

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
STTest1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);

	printf("%d ", STTop(&st));
	STPop(&st);

	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	STDestory(&st);
}

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

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;
//初始化栈
void STInit(ST* pst);
//入栈
void STPush(ST* pst, STDatatype x);
//出栈
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈顶元素
STDatatype STTop(ST* pst);
//获取栈中有效元素个数
int STSize(ST* pst);
//销毁栈
void STDestory(ST* pst);

Stack.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDatatype x)
{
	//开辟空间
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity = 0 ? 4 : (pst->capacity) * 2;
		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//插入
	pst->a[pst->top] = x;
	pst->top++;
}
//判空函数
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
//获取栈顶元素
STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}
//获取栈中有效数据的个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
//销毁栈
void STDestory(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

测试：

2. 队列

2.1 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列中的元素遵循先进先出的原则

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头 

队列很好理解，就像在食堂打饭一样，先排进队的先打饭，打完饭先走，

2.2 队列的实现

要实现队列，最好使用链表的方式，因为数组头删效率比较低。

我们先来定义一个结构体：

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

很明显，这是个单链表，我们要实现队列，还要知道队列的头和尾，以及队列中有效数据的个数，所以索性把它们也定义成一个结构体：

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

phead就是队列的头，ptail就是队列的尾 

下面我们来实现队列吧。

队列的初始化：

//初始化队列
void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	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->ptail == NULL)
	{
		assert(pq->phead == NULL);
		pq->phead = pq->ptail=newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

判空函数：

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

队头出队列：

这相当于单链表的头删，注意分情况，一个节点和多个节点要单独写，同时要用判空函数QueueEmpty()断言队列是否为空。

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个节点
	//多个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail= NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

获取队列头部元素：

//获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

获取队列尾部元素：

//获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

获取队列中有效元素个数：

//获取队列中有效元素个数
int Queuesize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

销毁队列：

//销毁队列
void DestoryQueue(Queue* pq)
{
	assert(pq);
	while (pq->phead)
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

 完整代码：

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
QueueTest1()
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);

	QueuePop(&pq);
	printf("%d ", QueueFront(&pq));

	QueuePush(&pq, 3);
	QueuePush(&pq, 4);

	printf("%d ", QueueBack(&pq));

	while (!QueueEmpty(&pq))
	{
		printf("%d ", QueueFront(&pq));
		QueuePop(&pq);
	}
	DestoryQueue(&pq);
}
int main()
{
	QueueTest1();
	return 0;
}

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

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

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDatatype x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部元素
QDatatype QueueFront(Queue* pq);
//获取队列尾部元素
QDatatype QueueBack(Queue* pq);
//获取队列中有效元素个数
int Queuesize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//销毁队列
void DestoryQueue(Queue* pq);

Queue.c 

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

//初始化队列
void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	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->ptail == NULL)
	{
		assert(pq->phead == NULL);
		pq->phead = pq->ptail=newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

//判空函数
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size ==0 ;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个节点
	//多个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail= NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

//获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

//获取队列中有效元素个数
int Queuesize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//销毁队列
void DestoryQueue(Queue* pq)
{
	assert(pq);
	while (pq->phead)
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

测试：

以上就是栈和队列的实现了，下一节我们讲几个栈和队列QJ题，

未完待续。。。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/120657.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

在 Python 中使用 Selenium 按文本查找元素

在 Python 中使用 Selenium 按文本查找元素

我们将通过示例介绍在Python中使用selenium通过文本查找元素的方法。 在 Python 中使用 Selenium 按文本查找元素 软件测试是检查应用程序是否满足用户需求的技术。 该技术有助于使应用程序成为无错误的应用程序。 软件测试可以手动完成&#xff0c;也可以通过某些软件完成。…
阅读更多...
解决Docker启动之npm版本不兼容问题

解决Docker启动之npm版本不兼容问题

报错内容&#xff1a; npm WARN read-shrinkwrap This version of npm is compatible with lockfileVersion1, but package-lock.json was generated for lockfileVersion2. Ill try to do my best with it! npm WARN tar ENOENT: no such file or directory, open /home/wvp-…
阅读更多...
ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？

ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？

&#xff08;本文引自mic老师文档&#xff09; 之前分享过一期 HashMap 的面试题&#xff0c;然后有个小伙伴私信我说&#xff0c;他遇到了一个 ConcurrentHashMap 的问题不知道怎么回答。 于是&#xff0c;就有了这一期的内容&#xff01;&#xff01; …
阅读更多...
Skywalking介绍

Skywalking介绍

一个优秀的项目&#xff0c;除了具有高拓展的架构、高性能的方案、高质量的代码之外&#xff0c;还应该在上线后具备多角度的监控功能。现在企业中的监控服务也有很多&#xff0c;Skywalking除了提供多维度、多粒度的监控之外&#xff0c;也提供了良好的图形化界面以及性能剖析…
阅读更多...
Python--- lstrip()--删除字符串两边的空白字符、rstrip()--删除字符串左边的空白字符、strip()--删除字符串右边的空白字符

Python--- lstrip()--删除字符串两边的空白字符、rstrip()--删除字符串左边的空白字符、strip()--删除字符串右边的空白字符

strip() 方法主要作用&#xff1a;删除字符串两边的空白字符&#xff08;如空格&#xff09; lstrip() 方法 left strip&#xff0c;作用&#xff1a;只删除字符串左边的空白字符 rstrip() 方法&#xff0c;作用&#xff1a;只删除字符串右边的空白字符 strip 英 /strɪp…
阅读更多...
Ansible playbook自动化运维工具详解

Ansible playbook自动化运维工具详解

Ansible playbook自动化运维工具详解 一、playbook的相关知识1.1、playbook 的简介1.2、playbook的 各部分组成 二、基础的playbook剧本编写实例三、 playbook的定义、引用变量3.1、基础变量的定义与引用3.2、引用fact信息中的变量 四、playbook中的when条件判断和变量循环使用…
阅读更多...
P02项目诊断报警组件（学习操作日志记录、单元测试开发）

P02项目诊断报警组件（学习操作日志记录、单元测试开发）

★ P02项目诊断报警组件 诊断报警组件的主要功能有&#xff1a; 接收、记录硬件设备上报的报警信息。从预先设定的错误码对照表中找到对应的声光报警和蜂鸣器报警策略&#xff0c;结合当前的报警情况对设备下发报警指示。将报警消息发送到消息队列&#xff0c;由其它组件发送…
阅读更多...
Collection集合 迭代器遍历Iterator 和集合增强For

Collection集合 迭代器遍历Iterator 和集合增强For

迭代器遍历Iterator 标准写法: 增强For for(类型 名称 : 集合 ) 举例: 不仅可以集合也可以数组 底层仍然是iterator
阅读更多...
设计模式—结构型模式之装饰器模式

设计模式—结构型模式之装饰器模式

设计模式—结构型模式之装饰器模式 适配器是连接两个类&#xff0c;可以增强一个类&#xff0c;装饰器是增强一个类。 向一个现有的对象添加新的功能&#xff0c;同时又不改变其结构。属于对象结构型模式。 创建了一个装饰类&#xff0c;用来包装原有的类&#xff0c;并在保…
阅读更多...
ZZ308 物联网应用与服务赛题第E套

ZZ308 物联网应用与服务赛题第E套

2023年全国职业院校技能大赛 中职组 物联网应用与服务 任 务 书 &#xff08;E卷&#xff09; 赛位号&#xff1a;______________ 竞赛须知 一、注意事项 1.检查硬件设备、电脑设备是否正常。检查竞赛所需的各项设备、软件和竞赛材料等&#xff1b; 2.竞赛任务中所使用的…
阅读更多...
解决ERR: cURL error 77: Unable to initialize NSS: -8023

解决ERR: cURL error 77: Unable to initialize NSS: -8023

研发反映一个问题，上传文件时失败，日志内错误信息如下： ERR: cURL error 77: Unable to initialize NSS: -8023 (SEC_ERROR_PKCS11_DEVICE_ERROR) ... 这个功能使用了腾讯云的点播服务。因此立即联系了腾讯云客服。 搞了很久问题依旧。 反复测试，发现上传视频文件，错…
阅读更多...
精解括号匹配问题与极致栈设计：揭开最大栈和最小栈的奥秘

精解括号匹配问题与极致栈设计：揭开最大栈和最小栈的奥秘

目录 括号匹配问题最小栈最大栈 最大栈和最小栈是极致栈的两个重要变种。最大栈用于存储当前匹配的最大值&#xff0c;而最小栈用于存储当前匹配的最小值。 括号匹配问题 这个问题我们来看力扣20题的描述&#xff1a; 给定一个只包括 ‘(’&#xff0c;‘)’&#xff0c;‘{’…
阅读更多...
大数据毕业设计选题推荐-营业厅营业效能监控平台-Hadoop-Spark-Hive

大数据毕业设计选题推荐-营业厅营业效能监控平台-Hadoop-Spark-Hive

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…
阅读更多...
RTC实时时钟——DS1302

RTC实时时钟——DS1302

DS1302目录 一、DS1302简介引脚定义与推荐电路 二、芯片手册1.操作寄存器的定义2.时序定义dc1302.cds1302.h 三、蓝桥杯实践 一、DS1302简介 RTC(Real Time Clock):实时时钟&#xff0c;是一种集成电路&#xff0c;通常称为时钟芯片。现在流行的串行时钟电路很多&#xff0c;如…
阅读更多...
把wpf的窗体保存为png图片

把wpf的窗体保存为png图片

昨晚在stack overflow刷问题时看到有这个问题&#xff0c;今天早上刚好来尝试学习一下 stack overflow的链接如下&#xff1a; c# - How to render a WPF UserControl to a bitmap without creating a window - Stack Overflow 测试步骤如下&#xff1a; 1 新建.net frame…
阅读更多...
企业微信vs个人微信：对比对照一览表

企业微信vs个人微信：对比对照一览表

继微信后&#xff0c;腾讯推出了企业微信。企业微信可以添个人微信为好友&#xff0c;有群聊和朋友圈&#xff0c;粗看起来与个人微信十分相似&#xff0c;那么它们有什么区别呢&#xff1f; 企业微信和个人微信的区别是什么&#xff0c;咱今天两张图来对比看看~
阅读更多...
输电线路AR可视化巡检降低作业风险

输电线路AR可视化巡检降低作业风险

随着现代工业的快速发展&#xff0c;各行业的一线技术工人要处理的问题越来越复杂&#xff0c;一些工作中棘手的问题迫切需要远端专家的协同处理。但远端专家赶来现场往往面临着专家差旅成本高、设备停机损失大、专业支持滞后、突发故障无法立即解决等痛点。传统的远程协助似乎…
阅读更多...
数据结构与算法-(11)---有序表(OrderedList)

数据结构与算法-(11)---有序表(OrderedList)

&#x1f308;个人主页: Aileen_0v0 &#x1f525;系列专栏:PYTHON学习系列专栏 &#x1f4ab;"没有罗马,那就自己创造罗马~" 目录 知识回顾及总结 有序表的引入 ​编辑 实现有序表 1.有序表-类的构造方法 2.有序表-search方法的实现 3.有序表-add方法的实现…
阅读更多...
勒索病毒最新变种.halo勒索病毒来袭，如何恢复受感染的数据？

勒索病毒最新变种.halo勒索病毒来袭，如何恢复受感染的数据？

导言&#xff1a; 在当今数字化时代&#xff0c;网络犯罪分子不断进化&#xff0c;勒索病毒已经成为一种广泛传播的网络威胁。本文91数据恢复将深入介绍.halo勒索病毒&#xff0c;包括它的工作原理、如何从中恢复被加密的数据文件以及如何采取预防措施来保护自己免受感染。当面…
阅读更多...
AD教程 （十）Value值的核对

AD教程 （十）Value值的核对

AD教程 &#xff08;十&#xff09;Value值的核对 填写器件位号 直接根据原理图的原始编号进行更改 通过位号编辑器快速更改 点击工具&#xff0c;选择标注&#xff0c;选择原理图标注&#xff0c;进入位号编辑器 可以在位号编辑器中 设置处理顺序&#xff0c;从上往下还是从…
阅读更多...
最新文章

Copyright @ 2022~2023