【数据结构】栈和队列超详解！(Stack Queue)

文章目录

  • 前言
  • 一、栈
    • 1、栈的基本概念
    • 2、栈的实现（数组实现）
    • 3、栈的基本操作
      • 3.1 栈的结构设计
      • 3.2 栈常见的基本函数接口
    • 4、栈的实现
      • 4.1 初始化栈
      • 4.2 栈的销毁
      • 4.3 入栈
      • 4.4 出栈
      • 4.5 判空
      • 4.6 长度
      • 4.7 获取栈顶元素
  • 完整代码
      • Stack.h
      • Stack.c
      • Test.c
  • 二、队列
    • 1、队列的结构及概念
    • 2、队列的实现（单链表实现）
      • 1、队列的链式结构设计
      • 2、常用的功能接口
        • 2.1、初始化队列
        • 2.2、销毁队列
        • 2.3、入队列
        • 2.4、出队列
        • 2.5、获取队列头部元素
        • 2.6、获取队列尾部元素
        • 2.7、判空
        • 2.8、获取有效元素个数
    • 完整代码
      • Queue.h
      • Queue.c
      • Test.c

前言

在这里插入图片描述

一、栈

1、栈的基本概念

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

在这里插入图片描述

2、栈的实现（数组实现）

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小
在这里插入图片描述

3、栈的基本操作

压栈：栈的插入操作，也叫进栈/入栈/压栈，在栈顶进行数据操作。
出栈：栈的删除操作，也是在栈顶进行数据删除的。

3.1 栈的结构设计

typedef int STDataType;//方便修改类型
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

3.2 栈常见的基本函数接口

//初始化
void STInit(ST* pst);
//销毁栈
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//长度
int STSize(ST* pst);
//栈顶
STDataType STTop(ST* pst);

4、栈的实现

4.1 初始化栈

//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//指向栈顶下一个元素,若等于-1则指向栈顶元素，两种任选
	pst->capacity = 0;
}

4.2 栈的销毁

//销毁栈
void STDestroy(ST* pst)
{
	assert(pst);
	tree(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

4.3 入栈

在这里插入图片描述
代码：

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//判断栈是否已满，满了就扩容
	if (pst->top == pst->capacity)
	{
		//使用三目运算符进行第一次开辟空间和后续扩容空间
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		//判断realloc是否开辟成功
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//赋新值
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//插入
	pst->a[pst->top] = x;
	pst->top++;
}

4.4 出栈

在这里插入图片描述
代码：

//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

4.5 判空

//判空
bool STEmpty(ST* pst)
{
	assert(pst);  
	//返回值为0为假，非零为真
	return pst->top == 0;
}

4.6 长度

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

4.7 获取栈顶元素

注意：若栈顶指针初始化为pst->top = 0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为pst->a[pst->top++]，出栈操作为pst->a[- -pst->top]。因为栈顶指针若初始化为 0 时，则栈顶指针始终指向顺序栈将要入栈的位置，也就是栈顶指针的下标就是入栈元素的下标。

//栈顶
STDataType STTop(ST* pst)
{
	assert(pst);
	return pst->a[pst->top - 1];
}

完整代码

Stack.h

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

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

//初始化
void STInit(ST* pst);
//销毁栈
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//长度
int STSize(ST* pst);
//栈顶
STDataType STTop(ST* pst);

Stack.c

#include"Stack.h"

//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//指向栈顶下一个元素
	pst->capacity = 0;
}
//销毁栈
void STDestroy(ST* pst)
{
	assert(pst);
	tree(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	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("realloc fail");
			return;
		}
		pst->capacity = newcapacity;
		pst->a = tmp;
	}
	pst->a[pst->top] = x;
	pst->top++;	
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
//判空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
//长度
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
//栈顶
STDataType STTop(ST* pst)
{
	assert(pst);
	return pst->a[pst->top - 1];
}

Test.c

#include"Stack.h"

int main()
{
	ST st;
	//初始化
	STInit(&st);
	//插入+删除
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	STPop(&st);
	STPop(&st);
	//长度
	STSize(&st);
	//栈顶
	STTop(&st);
	//销毁
	STDestroy(&st);
	return 0;
}

二、队列

1、队列的结构及概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
在这里插入图片描述

2、队列的实现（单链表实现）

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
在这里插入图片描述
下面话不多说，直接开始代码实现

1、队列的链式结构设计

//链式结构 表示队列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;                                                                          
}QNode;
//队列的结构
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

2、常用的功能接口

//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDeatroy(Queue* pq);
//队尾入列
void QueuePush(Queue* pq, QDataType x);
//队头出列
void QueuePop(Queue* pq);
//获取队列头部元素
QDataType QueueFront(Queue* pq);
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
//检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);
2.1、初始化队列

只需要将头尾指针都指向空即可，元素个数为零

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
2.2、销毁队列

遍历链表，从头到尾依次删除结点，最后将头尾指针指向空，元素个数为0。

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

创建新节点，若队列为空，则将头指针和尾指针都指向新创建的节点，若不为空，则尾插，因为是链式存储，所以和单链表的尾插一样，将尾指针的next指向该节点，再把该节点设为新的尾节点

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
2.4、出队列

注意：出列要考虑队列是空还是只有一个结点又或者有多个结点，为空则在代码第一步就报错，若只有一个结点，则直接删除该结点，并将头尾俩指针指向空，若不止一个结点，可以创建一个临时指针来记录当前头指针，然后尾指针往后遍历，再free掉创建的临时指针，并置空

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
	if (pq->phead == NULL)
		pq->ptail = NULL;

	pq->size--;
}
2.5、获取队列头部元素

断言，然后直接返回队头指针指向的节点元素

//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
2.6、获取队列尾部元素

也是一样的，直接返回队尾指针指向的节点元素

//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->ptail->val;
}
2.7、判空

检测队列是否为空，如果为空返回非零结果，如果非空返回0


bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
2.8、获取有效元素个数
//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

完整代码

Queue.h

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

//链式结构 表示队列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;                                                                          
}QNode;
//队列的结构
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDeatroy(Queue* pq);
//队尾入列
void QueuePush(Queue* pq, QDataType x);
//队头出列
void QueuePop(Queue* pq);
//获取队列头部元素
QDataType QueueFront(Queue* pq);
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
//检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
//销毁队列
void QueueDeatroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	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");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		//现在newnode是新的尾结点
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//队头出列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead); 
	//保存当前节点
	QNode* tmp = pq->phead;
	//phead往下走
	pq->phead = pq->phead->next;
	free(tmp);
	tmp = NULL;
	if (pq->phead = NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}
//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);

	assert(pq->phead);
	return pq->phead->val;
}
//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->ptail;
}
//检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

Test.c

#include"Queue.h"

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	QueueDeatroy(&q);
	return 0;

}

在这里插入图片描述

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

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

相关文章

点对点协议PPP

点对点协议PPP

目录 一. PPP协议的特点1.1 PPP 协议应满足的需求1.2 PPP 协议的组成 二. PPP协议的帧格式2.1 PPP协议的透明传输2.1.1 同步传输2.1.2 异步传输 三. PPP协议的工作状态 \quad 一. PPP协议的特点 \quad \quad 用户到ISP的链路使用PPP协议 \quad \quad 1.1 PPP 协议应满足的需求 …
阅读更多...
面试题：HashMap 为什么不能一边遍历一遍删除

面试题：HashMap 为什么不能一边遍历一遍删除

文章目录 前言foreach 循环&#xff1f;HashMap 遍历集合并对集合元素进行 remove、put、add1、现象为什么会抛出这个异常呢&#xff1f;2、细究底层原理 前言 上面出现这样的原因是在使用 foreach 对 HashMap 进行遍历时&#xff0c;同时进行 put 赋值操作会有问题&#xff0c…
阅读更多...
6-6 堆排序 分数 10

6-6 堆排序 分数 10

typedef int Datatype; typedef struct {Datatype* elem; int Length; }SqList; typedef SqList HeapType; void swap(int* a, int* b) {int tmp *a;*a *b;*b tmp; } //建大堆 //m: 结点个数 s: 待下调父结点下标 void HeapAdjust(HeapType H, int s, int m) {int child …
阅读更多...
骨传导耳机和开放式耳机哪个对听力的损伤小一些？

骨传导耳机和开放式耳机哪个对听力的损伤小一些？

先说结论&#xff0c;骨传导耳机对听力的损伤更小&#xff0c;并且更值得入手。 其实骨传导耳机也算开放式耳机的一种&#xff0c;开放式耳机中又包括了骨传导耳机和气传导耳机&#xff0c;与其说骨传导耳机和入耳式耳机&#xff0c;不如说是骨传导耳机和气传导耳机&#xff0…
阅读更多...
代码随想Day36 | 435. 无重叠区间、763.划分字母区间、56. 合并区间

代码随想Day36 | 435. 无重叠区间、763.划分字母区间、56. 合并区间

435. 无重叠区间 这道题和前一天的射箭题目思想类似&#xff0c;用总区间个数-不重叠的区间个数等于需要去除的区间个数。首先对左边界排序&#xff0c;如果当前的左边界大于等于上一区间的右边界&#xff0c;则说明是一个不重叠的区间&#xff0c;否则&#xff0c;更新上一重…
阅读更多...
基于Web的智慧城市实验室主页系统设计与实现论文

基于Web的智慧城市实验室主页系统设计与实现论文

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对实验室信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差&…
阅读更多...
Layui实现自定义的table列悬停事件并气泡提示信息

Layui实现自定义的table列悬停事件并气泡提示信息

1、概要 使用layui组件实现table的指定列悬停时提示信息&#xff0c;因为layui组件中没有鼠标悬停事件支持&#xff0c;所以需要结合js原生事件来实现这个功能&#xff0c;并结合layui的tips和列的templte属性气泡提示实现效果。 2、效果图 3、代码案例 <!DOCTYPE html&g…
阅读更多...
Hdfs java API

Hdfs java API

1.在主机上启动hadoop sbin/start-all.sh 这里有一个小窍门&#xff0c;可以在本机上打开8088端口查看三台机器的连接状态&#xff0c;以及可以打开50070端口&#xff0c;查看hdfs文件状况。以我的主虚拟机为例&#xff0c;ip地址为192.168.198.200&#xff0c;所以可以采用下…
阅读更多...
如何处理好面试中的“压力测试”？

如何处理好面试中的“压力测试”？

作为一名求职者&#xff0c;在面试时有时遇到的是压力测试&#xff0c;有时则遇到的是一些无良企业单位&#xff0c;究竟如何把握忍耐的限度&#xff0c;才合格当一个能经受压力的员工&#xff0c;才能避免对无良单位的一味隐忍! 压力面试是指有意制造紧张&#xff0c;以了解求…
阅读更多...
Java_内部类枚举

Java_内部类枚举

内部类 内部类: 是类中的五大成分之一&#xff08;成员变量、方法、构造器、内部类、代码块)&#xff0c;如果一个类定义在另一个类的内部&#xff0c;这个类就是内部类。场景:当一个类的内部&#xff0c;包含了一个完整的事物&#xff0c;且这个事物没有必要单独设计时&#x…
阅读更多...
L1-042：日期格式化

L1-042：日期格式化

题目描述 世界上不同国家有不同的写日期的习惯。比如美国人习惯写成“月-日-年”&#xff0c;而中国人习惯写成“年-月-日”。下面请你写个程序&#xff0c;自动把读入的美国格式的日期改写成中国习惯的日期。 输入格式&#xff1a; 输入在一行中按照“mm-dd-yyyy”的格式给出月…
阅读更多...
SSL通配符详解

SSL通配符详解

通配符证书是一种特殊的SSL/TLS证书&#xff0c;它允许一个域名及其所有子域名使用相同的证书。这意味着&#xff0c;如果您有一个通配符证书&#xff0c;您可以为该证书中的任何子域名提供SSL/TLS加密&#xff0c;而无需为每个子域名单独购买和配置证书。 通配符证书使用通配…
阅读更多...
vue前端访问Django channels WebSocket失败

vue前端访问Django channels WebSocket失败

现象 前端报错&#xff1a;SSH.vue:51 WebSocket connection to ‘ws://127.0.0.1:8000/server/terminal/120.59.88.26/22/1/’ failed: 后端报错&#xff1a;Not Found: /server/terminal/120.79.83.26/22/1/ 原因 django的版本与channels的版本不匹配&#xff08;django…
阅读更多...
统计学基础知识

统计学基础知识

记录一些基础概念 1.总体&#xff1a;是指根据研究目的所确定的观察单位某项特征的集合。 2.样本&#xff1a;就是从总体中抽出的部分观察单位某项特征的集合。 3.参数&#xff1a;是用于描述总体特征的指标&#xff0c;如总体均数&#xff08;μ&#xff09;&#xff0c;总体标…
阅读更多...
XCP详解「4.1·问题-polling有效，DAQ无效」

XCP详解「4.1·问题-polling有效，DAQ无效」

改用DAQ模式后&#xff0c;没有周期报文发出&#xff0c;log如下 正常的LOG 排查发现 &#xff0c;Task里没有mapping CanXcp_MainFunction&#xff0c;只是mapping了Xcp_MainFunction这就导致了XCP polling模式功能正常&#xff0c;daq无数据 修改1 修改2, 如果还没奏效&…
阅读更多...
Oracle数据库本地部署结合内网穿透实现公网环境PLSQL远程访问

Oracle数据库本地部署结合内网穿透实现公网环境PLSQL远程访问

文章目录 前言1. 数据库搭建2. 内网穿透2.1 安装cpolar内网穿透2.2 创建隧道映射 3. 公网远程访问4. 配置固定TCP端口地址4.1 保留一个固定的公网TCP端口地址4.2 配置固定公网TCP端口地址4.3 测试使用固定TCP端口地址远程Oracle 前言 Oracle&#xff0c;是甲骨文公司的一款关系…
阅读更多...
详解接口测试

详解接口测试

目录 什么是接口&#xff1f; 接口协议的类型 接口测试是什么 HTTP接口的测试用例设计 HTTP接口的测试方法 什么是接口&#xff1f; 在面向对象编程中&#xff0c;接口是一个抽象的概念&#xff0c;用于定义类应该具有的方法和属性。一个类可以实现一个或多个接口&#xf…
阅读更多...
Golang导入导出Excel表格

Golang导入导出Excel表格

最近项目开发中有涉及到Excel的导入与导出功能&#xff0c;特别是导出表格时需要特定的格式&#xff08;单元格合并等&#xff09;&#xff0c;废话不多说&#xff0c;直接上代码了。 首先用到一个第三方库&#xff0c;实测还是很强大很好用的&#xff0c;就是这个https://git…
阅读更多...
官宣 | HelpLook已入驻企业微信应用市场

官宣 | HelpLook已入驻企业微信应用市场

HelpLook正式入驻企业微信第三方应用市场。 HelpLook支持自定义域名与AI站内搜索&#xff0c;能够帮助企业微信用户搭建所见即所得的企业知识库、产品帮助中心、用户手册、企业博客。 | 怎么找到HelpLook并开始使用 在企业微信的第三方应用就可直接搜索HelpLook&#xff0c;添…
阅读更多...
innovus：generateRCFactor对比第三方spef方法

innovus：generateRCFactor对比第三方spef方法

我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起来吧&#xff1f; 拾陆楼知识星球入口 preroute/postroute以及signoff工具之间rc factor直接影响&#xff0c;各阶段时序与最终signoff工具之间的差别。 以starrcPT为signoff工具&#xff0c;innovus需要用generate…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站