当前位置: 首页 > article >正文

【数据结构】顺序栈的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 销毁

对于栈的销毁,那么我们就只需要释放动态开辟的空间,将指针置空。并将 capacitytop 两个变量置 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();
}

总结:

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

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

在这里插入图片描述


http://www.kler.cn/a/2160.html

相关文章:

  • 树莓集团是如何链接政、产、企、校四个板块的?
  • 【MySQL 进阶之路】事务隔离级别
  • leetcode 3001. 捕获黑皇后需要的最少移动次数 中等
  • Facebook广告文案流量秘诀
  • 人工智能大模型LLM开源资源汇总(持续更新)
  • 《数据结构》(非408代码题)
  • 刷题记录(2023.3.14 - 2023.3.18)
  • Vue实战【封装一个简单的列表组件,实现增删改查】
  • 栈应用——逆波兰算法
  • 华为MetaERP最佳的免费开源平替方案:Odoo生产制造功能简介
  • 【Java进阶篇】——反射机制
  • 蓝桥杯刷题第十三天
  • ChatGPT和百度文心一言写用例,谁更强?
  • 移除元素(双指针)
  • 《剑指Offer》笔记题解思路技巧优化——精心编写(1)
  • “你要多弄弄算法”
  • 南京邮电大学数据库第三次课后作业
  • 什么是推挽输出,开漏输出?
  • 【嵌入式硬件芯片开发笔记】HART协议调制解调芯片AD5700配置流程
  • Qt优秀开源项目之十七:QtPromise
  • PostgreSQL学习总结(12)—— PostgreSQL 内置函数汇总
  • 第十七天 JavaScript、Vue详细总结
  • 队列实现及leetcode相关OJ题
  • Redis 如何实现库存扣减操作和防止被超卖?
  • 【业务安全-02】业务逻辑漏洞之越权操作
  • 测试老鸟都在用的接口抓包常用工具以及接口测试工具都有哪些?