【数据结构】顺序栈的C语言实现

​在这里插入图片描述

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

文章目录

  • 栈
    • 1. 栈的概念
      • 1.1 栈的概念选择题：
    • 2. 栈的结构
    • 3. 栈的实现
      • 3.1 结构设计
      • 3.2 接口总览
      • 3.3 初始化
      • 3.4 销毁
      • 3.5 判断栈是否为空
      • 3.6 压栈
      • 3.7 出栈
      • 3.8 取栈顶元素
      • 3.9 计算栈的大小
    • 4. 完整代码
    • Stack.h
    • Stack.c
    • test.c
  • 总结：

栈

1. 栈的概念

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

栈对于数据的管理主要有两种操作：
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，从栈顶进行压栈。
出栈：栈的删除操作叫做 出栈，从栈顶进行出栈。
栈的操作流程：
在这里插入图片描述

1.1 栈的概念选择题：

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

答案：B
首先明确栈的原则：后进先出。
将以上元素依次入栈，那么最入栈的最晚出栈，那么1应该最后一个出栈，直接选出结果：EDCBA54321

若进栈序列为 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

做对这道题目，我们需要知道，栈不是所有数据入栈后才能出栈的，栈可以入栈部分元素，然后出栈，再入栈其他元素。

下面对每个选项进行分析：
A：1 先入栈，然后出栈，栈空；随后 2, 3, 4 依次入栈。然后将元素全部出栈，栈空。得到结果为：1, 4, 3, 2
B：1, 2 先入栈；然后出栈 2，栈中余1；再入栈 3，出栈 3，栈中余1；再入栈 4，出栈 4，栈中余1；最后出栈 1，栈空。得到结果为：2, 3, 4, 1
C：这种序列答案是绝对不可能的。通过 A、B两个选项和这道题的进栈序列我们也可以找出规律：某个元素的两个相邻元素必定有一个相邻元素与该元素差值为1。否则的话就不符合栈的结构。因为如果第一个元素为3的话，那么就是先入栈 1，2，3，然后出栈。那么无论怎么出栈，第二个元素都不可能为1。2, 4 都有可能，可以画图分析。
D：1，2，3，先入栈；然后出栈3，栈中余2，1；再入栈 4，然后出栈 4，栈中余2，1；然后将栈中元素全部出栈。得到结果为：3, 4, 2, 1

2. 栈的结构

栈一般可以使用 数组或链表 实现。分析一下使用这两种方法实现，栈的结构分别是什么样的。在分析之前，我们要明确的一点是，栈只对 栈顶 的元素进行操作。
在这里插入图片描述

1.数组(顺序表)：
对于数组(顺序表)而言，最方便的就是尾插和尾删，所以我们将 顺序表的尾部 当做 栈顶。顺序表的头部 则当做 栈底，因为对于顺序表，头部的删除需要挪动大量数据。
2.链表：
对于链表而言，尤其是 单链表，尾部的插入删除是很麻烦的。但是 单链表 的头插和头删就很方便，所以可以把 单链表的头部 作为栈顶，单链表的尾部 作为 栈底。
3.双向链表：
而言，那么就是随便选了，毕竟双向链表无论哪头插入删除数据都很方便。
在这里插入图片描述

抉择：
那么对于 顺序栈 和 链式栈 ，那个更加好呢？那必定是 顺序栈，因为使用顺序栈的 尾插尾删非常方便， 且 cpu缓存利用率也更高，因为它的物理内存是连续的。而且对于顺序栈实现起来相对简单，所以我们接下来就实现 顺序栈 。

3. 栈的实现

3.1 结构设计

我们既然是实现 顺序栈，那么它的结构肯定就和 顺序表 差不多：

typedef struct Stack
{
	STDatatype* a; // 指向动态开辟的数组
	int capacity; // 栈的容量
	int top; // 标识 栈顶的下一个位置的下标 或 栈顶的下标
}ST;

这里的 top 我们需要好好理解一下。当top的初始值不同时，top可以表示 栈顶的下一个位置的下标 或 栈顶下标。

1.当 top = 0，top 表示栈顶的下一个位置的下标：
在这里插入图片描述

top 初始值为 0，那么第一次 压栈 就是在0下标插入元素。压栈后，top++。那么当 最后一次压栈后，元素被压在栈顶，那么top 最后的位置就是栈顶的下一个元素的下标处。此时，top就是栈中元素的个数。

2.当 top = -1，top 表示栈顶的下标：
在这里插入图片描述

top 初始值为 -1，那么需要先 ++top，再压栈。否则会越界。当 最后一次压栈时，为先 ++top 再压栈，top 最后的位置就是栈顶的下标处。

注意 需要理清楚 top，否则实现判空、计算大小等接口函数的时候会引起错误

3.2 接口总览

由于 栈的结构 和 操作规则，栈的接口相对来说比较少，且比较简单：

void StackInit(ST* ps); // 初始化
void StackDestroy(ST* ps); // 销毁
void StackPush(ST* ps, STDatatype x); // 压栈
void StackPop(ST* ps); // 出栈
STDatatype StackTop(ST* ps); // 取栈顶元素
bool StackEmpty(ST* ps); // 判空
int StackSize(ST* ps); // 计算栈的大小

3.3 初始化

我们实现的是顺序栈，那么就和顺序表一样，需要创建结构体变量，传结构体的地址，进行初始化。在初始化的时候就给栈开上四个单位的空间，并且将起始容量设定为4。

注意我们这里设定的 top = 0，那么表示 top 为栈顶的下一个位置的下标。

void StackInit(ST* ps)
{
	// 结构体一定不为空，所以需要断言
	assert(ps);

	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

3.4 销毁

对于栈的销毁，那么我们就只需要释放动态开辟的空间，将指针置空。并将 capacity 和 top 两个变量置 0 即可。

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

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

3.5 判断栈是否为空

我们起初设定 top = 0，所以判断栈是否为空，那么只需要看 top 是否为0就可以了。如果为0，返回真 ；不为0，返回假。

bool StackEmpty(ST* ps)
{
	assert(ps);
	
    // 如果 ps->top == 0，返回真
    // 如果 ps->top !=0，返回假
	return ps->top == 0;
}

3.6 压栈

在压栈之前，需要保证空间足够，所以需要先检查容量，如果 不够，需要扩容，扩容成功后在考虑压栈的步骤。

我们设定 top 的初始值为 0。那么说明我们入栈的步骤为，先将元素放入，再让 top++。

void StackPush(ST* ps, STDatatype x)
{
	assert(ps);

	// 检查容量
	if (ps->top == ps->capacity)
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	// 插入元素
	// top 为栈顶的下一个元素
	// 先插入再 ++ 
	//ps->a[ps->top++] = x;
	ps->a[ps->top] = x;
	ps->top++;
}

3.7 出栈

如果栈中没有元素则不能出栈。所以我们需要调用 StackEmpty 判断是否为空，如果栈空(!StackEmpty(ps)为假)，则断言报错。

出栈的操作和顺序表的尾删操作步骤相似，直接将top--即可。


```c
void StackPop(ST* ps)
{
	assert(ps);

	// 如果栈空，则不能删除
	assert(!StackEmpty(ps));
	ps->top--;
}

3.8 取栈顶元素

由于我们 top 初值设定为 0，top为栈顶的下一个位置的下标，那么 top - 1 就是栈顶的下标，直接返回即可。

但是请注意：当栈为空时，无法取元素，所以需要判断一下。

STDatatype StackTop(ST* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));

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

3.9 计算栈的大小

如果一开始top = 0，那么栈的大小就直接是最后 top 的值。

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

	return ps->top;
}

4. 完整代码

Stack.h

#pragma once

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

typedef int STDatatype;

typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;  
	// 初始为0，表示栈顶位置下一个位置下标
   	// 初始为-1，表示栈顶位置的下标
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
STDatatype StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

Stack.c

这里将 top = 0 和 top = -1 的方案都写了一遍，注释部分为 top = 0，未注释部分为top = -1：

#define _CRT_SECURE_NO_WARNINGS 1 

#include "Stack.h"

// top 为栈顶的下一个元素

//void StackInit(ST* ps)
//{
//	// 结构体一定不为空
//	assert(ps);
//
//	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
//	if (ps->a == NULL)
//	{
//		perror("malloc fail");
//		exit(-1);
//	}
//	ps->capacity = 4;
//	ps->top = 0;
//}
//
//void StackDestroy(ST* ps)
//{
//	assert(ps);
//
//	free(ps->a);
//	ps->a = NULL;
//	ps->capacity = ps->top = 0;
//}
//
//void StackPush(ST* ps, STDatatype x)
//{
//	assert(ps);
//	
//	// 检查容量
//	if (ps->top == ps->capacity)
//	{
//		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
//		if (tmp == NULL)
//		{
//			perror("realloc fail");
//			exit(-1);
//		}
//		ps->a = tmp;
//		ps->capacity *= 2;
//	}
//	// 插入元素
//	// top 为栈顶的下一个元素
//	// 先插入再 ++ 
//	ps->a[ps->top++] = x;
//}
//
//void StackPop(ST* ps)
//{
//	assert(ps);
//
//	// 如果栈空，则不能删除
//	assert(!StackEmpty(ps));
//	ps->top--;
//}
//
//STDatatype StackTop(ST* ps)
//{
//	assert(ps);
//
//	assert(!StackEmpty(ps));
//
//	return ps->a[ps->top - 1];
//}
//
//bool StackEmpty(ST* ps)
//{
//	assert(ps);
//
//	return ps->top == 0;
//}
//
//int StackSize(ST* ps)
//{
//	assert(ps);
//
//	return ps->top;
//}

// top 为栈顶 初识值为 -1

void StackInit(ST* ps)
{
	// 结构体一定不为空
	assert(ps);

	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = -1;
}

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

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

void StackPush(ST* ps, STDatatype x)
{
	assert(ps);

	// 检查容量
	// 此时 top 一开始为 -1，不能表示栈中元素的数目
	// top + 1 才是正确的

	if (ps->top + 1 == ps->capacity)
	{
		STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	// 插入元素
	// top 为栈顶元素
	// 先 ++ 再插入
	ps->a[++ps->top] = x;
}

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

	// 如果栈空，则不能删除
	assert(!StackEmpty(ps));
	ps->top--;
}

STDatatype StackTop(ST* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));

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

bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == -1;
}

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

	return ps->top + 1;
}

test.c

在这里插入图片描述
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1 

#include "Stack.h"

void TestST1()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);


	printf("%d\n", StackTop(&st));

}

int main()
{
	TestST1();
}

总结：

今天我们认识并学习了顺序栈的相关概念、结构与接口实现，并且针对每个常用的功能接口进行了实现。总体来说，顺序栈的结构相比于之前的数据结构是比较简单的，之后将介绍队列的相关知识。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~

在这里插入图片描述

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

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

相关文章

Java打开CSV文件到JTable展示

Java打开CSV文件到JTable展示

概述主要知识点SwingNode类 &#xff1a;把Java swing组件封装成一个JavaFX的Node&#xff0c;使得Java Swing可以和JavaFX嵌套在一起使用&#xff0c;JavaSwing贼丑&#xff0c;但操作简单&#xff0c;JavaFX的表格组件&#xff08;TableView等&#xff09;有点复杂&#xff0…
阅读更多...
DevOps流水线搭建-PHP版本

DevOps流水线搭建-PHP版本

一、介绍流水线发布代码1、官网https://www.jenkins.io/zh2、kubesphere里的介绍https://kubesphere.io/zh/docs/v3.3/devops-user-guide/how-to-use/pipelines/choose-jenkins-agent/3、git仓库可以自己写点测试代码&#xff0c;提交&#xff0c;待会测试用https://gitee.com/…
阅读更多...
Mybatis（四）：自定义映射resultMap

Mybatis（四）：自定义映射resultMap

自定义映射resultMap前言一、处理字段和属性的映射关系问题&#xff1a;方案一&#xff1a;使用别名方案二&#xff1a;在mybatis-config.xml中设置mapUnderscoreToCamelCase方案三&#xff1a;在映射文件中设置redultMap二、多对一映射处理问题&#xff1a;方案一&#xff1a;…
阅读更多...
如何在 Vue 中使用 防抖 和 节流

如何在 Vue 中使用 防抖 和 节流

大厂面试题分享 面试题库前后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★地址&#xff1a;前端面试题库 https://mp.weixin.qq.com/s?__bizMzU5NzA0NzQyNg&mid2247485824&idx3&sn70cd26a7c0c683de64802f6cb9835003&scene21#wech…
阅读更多...
内存操作函数

内存操作函数

前言 &#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;推荐专栏: &#x1f354;&#x1f35f;&#x1f32f; c语言进阶 &#x1f511;个人信条: &#x1f335;知行合一 &#x1f349;本篇简介:>:介绍c语言中有关指针更深层的知识. 金句分享: ✨未来…
阅读更多...
蓝桥杯Web前端练习-----渐变色背景生成器

蓝桥杯Web前端练习-----渐变色背景生成器

介绍 相信做过前端开发的小伙伴们对渐变色在 UI 设计中的流行度一定不陌生&#xff0c;网页上也时常可以看到各类复杂的渐变色生成工具。使用原生的 CSS 变量加一些 JS 函数就能做出一个简单的渐变色背景生成器。 现在渐变色生成器只完成了颜色选取的功能&#xff0c;需要大家…
阅读更多...
【你不知道的 CSS】你写的 CSS 太过冗余，以至于我对它下手了

【你不知道的 CSS】你写的 CSS 太过冗余，以至于我对它下手了

:is() 你是否曾经写过下方这样冗余的CSS选择器: .active a, .active button, .active label {color: steelblue; }其实上面这段代码可以这样写&#xff1a; .active :is(a, button, label) {color: steelblue; }看~是不是简洁了很多&#xff01; 是的&#xff0c;你可以使用…
阅读更多...
5种最佳像素化图像的方法

5种最佳像素化图像的方法

5种最佳像素化图像的方法1. 什么是像素化&#xff1f;2. 像素化有什么用&#xff1f;3. 如何像素化图像&#xff1f;参考Pixelate 像素化 这篇博客将讨论像素化及如何以五种最佳方式对图像进行像素化。有时希望在在线共享照片时保护照片的隐私。因此在共享图像之前会对图像的某…
阅读更多...
锂电池充电的同时也能放电吗？

锂电池充电的同时也能放电吗？

大家应该都有这样经历&#xff0c;我们的手机在充电的同时也能边使用&#xff0c;有的同学就会说了&#xff0c;这是因为手机电池在充电的同时也在放电。如果这样想我们可能就把锂电池类比了一个蓄水池&#xff0c;以为它在进水的同时也能出水&#xff0c;其实这个比喻是错误的…
阅读更多...
【深度强化学习】(5) DDPG 模型解析，附Pytorch完整代码

【深度强化学习】(5) DDPG 模型解析，附Pytorch完整代码

大家好&#xff0c;今天和各位分享一下深度确定性策略梯度算法 (Deterministic Policy Gradient&#xff0c;DDPG)。并基于 OpenAI 的 gym 环境完成一个小游戏。完整代码在我的 GitHub 中获得&#xff1a; https://github.com/LiSir-HIT/Reinforcement-Learning/tree/main/Mod…
阅读更多...
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（10）

【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（10）

目录 写在前面&#xff1a; 题目&#xff1a;P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; 代…
阅读更多...
【数据结构】顺序表和链表

【数据结构】顺序表和链表

目录.顺序表.链表比较.顺序表 线性表的顺序存储结构&#xff0c;使用一段物理地址连续的存储单元以此存储数据单元的线性结构&#xff08;从头开始连续存储&#xff09; 静态顺序表&#xff1a;使用定长数组存储动态顺序表&#xff1a;使用动态开辟的数组存储&#xff08;常用…
阅读更多...
第十三届蓝桥杯省赛 python B组复盘

第十三届蓝桥杯省赛 python B组复盘

文章目录前言主要内容&#x1f99e;试题 A&#xff1a;排列字母思路代码&#x1f99e;试题 B&#xff1a;寻找整数思路代码&#x1f99e;试题 C&#xff1a;纸张尺寸思路代码&#x1f99e;试题 D&#xff1a;数位排序思路代码&#x1f99e;试题 E&#xff1a;蜂巢思路代码&…
阅读更多...
打印菱形、三角形-课后程序(JavaScript前端开发案例教程-黑马程序员编著-第2章-课后作业)

打印菱形、三角形-课后程序(JavaScript前端开发案例教程-黑马程序员编著-第2章-课后作业)

【案例2-10】打印菱形、三角形 一、案例描述 考核知识点 for双重循环 练习目标 掌握for循环应用。打印出菱形打印出三角形。 需求分析 在本案例中我们将用JavaScript代码在页面中用“*”打印出菱形和三角形。 案例分析 菱形效果如图2-16所示。输入菱形行数6打印菱形 三角形…
阅读更多...
计及光伏波动性的主动配电网有功无功协调优化（Matlab代码实现）

计及光伏波动性的主动配电网有功无功协调优化（Matlab代码实现）

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…
阅读更多...
JVM知识整理

JVM知识整理

JVM知识整理 JVM的主要组成部分 JVM包含两个两个子系统&#xff08;类加载子系统和执行引擎&#xff09;和两个组件&#xff08;运行时数据区与和本地库接口&#xff09; 类加载子系统&#xff1a;根据给定的全限定类名来加载class文件到运行时数据区域中的方法区。执行引擎&a…
阅读更多...
学大数据算跟风吗？

学大数据算跟风吗？

随着互联网、物联网和人工智能等技术的不断发展&#xff0c;大数据技术逐渐进入人们的视野&#xff0c;成为一个备受关注的热点话题。那么&#xff0c;大数据专业好学吗&#xff1f;前景如何&#xff1f;下面我们来一起探讨一下。 一、大数据专业的学习难度 大数据技术是一种综…
阅读更多...
将 XLS 转换为 EXE:xlCompiler Crack

将 XLS 转换为 EXE:xlCompiler Crack

只需单击几下即可将Excel文件转换为应用程序 xl编译器无需编程即可将您的Excel电子表格转换为软件应用程序 将 XLS 转换为 EXE 将Excel文件转换为具有保护选项的应用程序。Excel 到 EXE 转换器为您提供了分发 Excel 模型的竞争优势和灵活性。将 Excel 的功能丰富的环境保存在应…
阅读更多...
一文了解Gralde

一文了解Gralde

&#x1f3e0;个人主页&#xff1a;shark-Gao &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是shark-Gao&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f389;目前状况&#xff1a;23届毕业生&#xff0c;目前在某公司实习&#x1f…
阅读更多...
蓝桥杯·3月份刷题集训Day02

蓝桥杯·3月份刷题集训Day02

本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训&#xff0c;同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白&#xff0c;水平有限&#xff0c;如果文章中有什么错误之处&#xff0c;希望小伙伴们可以在评论区指出来&#xff0c;共勉&#x1f4aa;。 文…
阅读更多...
最新文章

Copyright @ 2022~2023