当前位置： 首页 > news >正文

＜栈和队列及模拟实现＞——《Data Structure in C Train》

news 来源：原创 2024/4/27 7:39:57

目录

详细实现链接：

＜栈（动态版）＞《数据结构(C语言版)》

＜队列（链式）＞《数据结构(C语言版)》

1.分析实现功能、感受栈和队列的实现结构：

1.1栈的实现结构方式：​

1.2 队列的实现方式：

2.完整源码：

2.1栈的模拟实现： 

Stack.h:

Stack.c:

Test.c:

2.2 队列的模拟实现：

Queue.h：

Queue.c:

Test.c:

 3.判断括号匹配程序：

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                       ——By 作者：新晓·故知

详细实现链接：

＜栈（动态版）＞《数据结构(C语言版)》

＜队列（链式）＞《数据结构(C语言版)》

1.分析实现功能、感受栈和队列的实现结构：

1.1栈的实现结构方式：

数组实现栈的结构：

相当于顺序表的尾插、尾删，用尾作栈顶，非常合适！从CPU预加载命中角度分析，数组实现的性能更好一些！

缺点：空间不够时需要增容。

单向链表实现栈的结构：

用头结点作栈底，这样使得入栈和出栈效率都是O(1)。

双向链表实现栈的结构：

用尾作栈顶。

1.2 队列的实现方式：

数组实现队列的结构：

不适合，队头出数据需要挪动数据

单链表实现队列的结构：

无需使用带头结点的单链表即可完成，带头结点是为了减少二级指针的使用。

tail是移动的，方便尾部操作直接找到。head方便头部操作直接找到。

 

数据结构的设计比较灵活，正所谓：“树挪死，人挪活”。在学习中，不要一味地“守死”，而要学会“变活。”

2.完整源码：

2.1栈的模拟实现： 

Stack.h:

#pragma once

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

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;   //通过数组实现栈的结构
	int top;
	int capacity;
}ST;
//初始化
void StackInit(ST* ps);
//释放内存、销毁空间
void StackDestory(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
//取栈顶数据
STDataType StackTop(ST* ps);
//栈的大小
int StackSize(ST* ps);
//判空
bool StackEmpty(ST* ps);

Stack.c:

#include"Stack.h"
//初始化
void StackInit(ST* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0; //这使得top最终指向的是栈顶的后一个位置。若top=-1,则最终指向的是栈顶。
}
//释放内存、销毁空间
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
// 入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	// 满了->增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}

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

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	// 栈空了，再调用Pop，就会直接中止程序报错
	assert(ps->top > 0);

	//ps->a[ps->top - 1] = 0; //置为0只考虑了int型等，若为char、double等就不适用了。
	ps->top--;
}
//取栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	// 栈空了，再调用Top，就会直接中止程序报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
//求栈大小
int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}
//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//判断括号是否匹配算法
bool isValid(char* s) {
	ST st;
	StackInit(&st);
	while (*s != '\0')
	{
		switch (*s)
		{
		case '{':
		case '[':
		case '(':
		{
			StackPush(&st, *s);
			++s;
			break;
		}
		case '}':
		case ']':
		case ')':
		{
			if (StackEmpty(&st))
			{
				StackDestory(&st);
				return false;
			}

			char top = StackTop(&st);
			StackPop(&st);

			// 不匹配
			if ((*s == '}' && top != '{')
				|| (*s == ']' && top != '[')
				|| (*s == ')' && top != '('))
			{
				StackDestory(&st);
				return false;
			}
			else // 匹配
			{
				++s;
			}
			break;
		}
		default:
			break;
		}
	}
	bool ret = StackEmpty(&st);
	StackDestory(&st);
	return ret;
}

Test.c:

#include"Stack.h"

int main()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 9);
	StackPush(&st, 5);
	StackPush(&st, 2);
	StackPush(&st, 7);

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

2.2 队列的模拟实现：

Queue.h：

#pragma once

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

typedef int QDataType;

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

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(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);

Queue.c:

#include"Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
//销毁
void QueueDestory(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(pq->head);

	// 1、一个
	// 2、多个
	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(pq->head);

	return pq->head->data;
}
//取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}
//队列大小
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}

	return size;
}
//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

Test.c:

#include"Queue.h"

void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);

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

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestory(&q);
}

int main()
{
	
	TestQueue();

	return 0;
}

 3.判断括号匹配程序：

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

///
//声明
typedef char STDataType;

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

//
//定义
//初始化
void StackInit(ST* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0;
}
//销毁
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

// 入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	// 满了-》增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}

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

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	// 栈空了，调用Pop，直接中止程序报错
	assert(ps->top > 0);

	//ps->a[ps->top - 1] = 0;
	ps->top--;
}
//去栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	// 栈空了，调用Top，直接中止程序报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
//求栈的的大小
int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}
//判空
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}
//判断括号是否匹配
bool isValid(char* s) {
	ST st;
	StackInit(&st);
	while (*s != '\0')
	{
		switch (*s)
		{
		case '{':
		case '[':
		case '(':
		{
			StackPush(&st, *s);
			++s;
			break;
		}
		case '}':
		case ']':
		case ')':
		{
			if (StackEmpty(&st))
			{
				StackDestory(&st);
				return false;
			}

			char top = StackTop(&st);
			StackPop(&st);

			// 不匹配
			if ((*s == '}' && top != '{')
				|| (*s == ']' && top != '[')
				|| (*s == ')' && top != '('))
			{
				StackDestory(&st);
				return false;
			}
			else // 匹配
			{
				++s;
			}
			break;
		}
		default:
			break;
		}
	}

	bool ret = StackEmpty(&st);
	StackDestory(&st);
	return ret;
}

int main()
{
	//int ret = isValid("[[[");
	//int ret = isValid("[][");
	int ret = isValid("[]");
	if (ret == 0)
	{
		printf("不匹配！\n" );
	}
	else
	{
		printf("匹配！\n");
	}
	return 0;
}

后记：
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                       ——By 作者：新晓·故知

相关文章：

  • 猿创征文｜【Typescript】搭建TS的编译环境
  • 【项目管理】beautyeye
  • Connor学Android - HandlerThread和IntentService
  • Github每日精选（第31期）：macOS 下的亮度和音量调节MonitorControl
  • Vue.js核心技术解析与uni-app跨平台实战开发学习笔记 第7章 Vue.js高级进阶 7.10 路由守卫
  • 金融核心系统云原生转型的三个挑战、六个误区和四个步骤
  • zsh安装以及ROS适配
  • 猿创征文｜FlexManager与阿里云MQTT通讯
  • Linux指令——crontab
  • 程序员的中秋
  • mysql数据库的安装教程
  • 新电脑的正确打开方式——（近万字图文并茂详细分步骤讲解）【包括个性锁屏，磁盘分区……】等你来解锁哦
  • .NET版Word处理控件Aspose.words功能演示：在ASP.NET MVC中创建MS Word编辑器
  • 【毕业设计】基于单片机的手势检测识别系统 - arduino 物联网嵌入式
  • 【Node.js】深度解析常用核心模块-path模块
  • $translatePartialLoader加载失败及解决方式
  • C++11: atomic 头文件
  • Create React App 使用
  • Elasticsearch 参考指南（升级前重新索引）
  • go append函数以及写入
  • JAVA 学习IO流
  • Javascripit类型转换比较那点事儿，双等号（==）
  • Js基础——数据类型之Null和Undefined
  • leetcode46 Permutation 排列组合
  • markdown编辑器简评
  • mysql中InnoDB引擎中页的概念
  • OSS Web直传 （文件图片）
  • PHP那些事儿
  • Python3爬取英雄联盟英雄皮肤大图
  • React的组件模式
  • SpiderData 2019年2月13日 DApp数据排行榜
  • Webpack 4x 之路 （ 四 ）
  • 开发基于以太坊智能合约的DApp
  • 配置 PM2 实现代码自动发布
  • 批量截取pdf文件
  • 如何借助 NoSQL 提高 JPA 应用性能
  • 深入浏览器事件循环的本质
  • 小程序上传图片到七牛云（支持多张上传，预览，删除）
  • 学习HTTP相关知识笔记
  • 译有关态射的一切
  • 正则表达式小结
  • 自动记录MySQL慢查询快照脚本
  • 宾利慕尚创始人典藏版国内首秀，2025年前实现全系车型电动化 | 2019上海车展 ...
  • ​iOS实时查看App运行日志
  • # centos7下FFmpeg环境部署记录
  • # Swust 12th acm 邀请赛# [ E ] 01 String [题解]
  • # 日期待t_最值得等的SUV奥迪Q9：空间比MPV还大，或搭4.0T，香
  • (3)Dubbo启动时qos-server can not bind localhost22222错误解决
  • (42)STM32——LCD显示屏实验笔记
  • (Bean工厂的后处理器入门)学习Spring的第七天
  • (Mirage系列之二)VMware Horizon Mirage的经典用户用例及真实案例分析
  • (层次遍历)104. 二叉树的最大深度
  • （附源码）ssm高校升本考试管理系统 毕业设计 201631
  • （机器学习的矩阵）（向量、矩阵与多元线性回归）
  • .“空心村”成因分析及解决对策122344