栈的实现及OJ练习（c语言）

目录

前言

栈

栈的实现（数组栈）

初始化栈

入栈

出栈

获取栈顶元素

获取栈中有效元素个数

检测栈是否为空

销毁栈

最终代码：

选择练习

栈的OJ题

前言

我们在之前已经学习了顺序表和链表的概念，它们有这样的优缺点：

链表的优势：

1、任意位置插入删除都是O（1）

2、按照申请释放、合理利用空间、不存在浪费

链表的劣势：

1、下标随机访问不方便，最坏时间复杂为O（n）

顺序表的优势：

1、支持下标随机访问，最坏时间复杂度为O（1）

顺序表的劣势：

1、头部或中间插入删除效率低，要挪动数据，最坏时间复杂度为O（n）

2、空间不够需要扩容，扩容有一定的消耗，且可能存在一定的空间浪费

3、只适合尾插尾删

        我们之所以要学习各种各样的数据结构，是因为在实际应用中要选取最适合的一种数据结构去实现我们的需求，它们各有各存在的意义，今天我们来学习两种新的数据结构栈：

栈

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

压栈的概念：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶

出栈的概念：栈的删除操作叫做出栈。出数据也在栈顶

栈的实现（数组栈）

概念：使用数组作为底层数据结构实现的栈

优势：

1. 简单高效：数组是一种连续的内存结构，可以直接通过索引访问元素。这使得在数组上进行栈操作（入栈和出栈）非常高效，时间复杂度为O(1)。相比于链表实现的栈，在插入和删除元素时不需要频繁地分配和释放内存。

2. 随机访问：由于数组具有随机访问的特性，我们可以通过索引快速地访问任意位置上的元素。这对于某些应用场景非常重要，例如需要查看或修改特定位置上的数据。

3. 存储连续性：由于数组是一段连续的内存空间，它能够更好地利用计算机硬件缓存系统带来的性能优势。相比之下，链表中每个节点可能分散在不同位置上，并且在遍历时会产生额外开销。

4. 空间效率：使用数组实现栈通常比使用链表实现占用更少的内存空间。链表节点除了保存数据本身外还需要额外空间来保存指向下一个节点地址等信息。

5. 实现简单：相对而言，在编写代码时使用基本类型（如整数、字符等）组成的简单静态数据结构（如数组）要比使用动态数据结构（如链表）更容易理解和实现。

注意事项：插入元素时需要提前确定存储空间的大小，并且如果栈满了，无法再添加新元素。这种情况下可能需要重新分配更大空间的数组并进行数据迁移操作。相比之下，链表可以动态地分配内存来适应不断变化的需求。

初始化栈

// 初始化栈
void StackInit(ST* pst)
{
    //首先要指向一个栈
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;    //令pop表示栈顶元素的下一个元素的下标
}

注意事项：

关于top的初始值有两种情况：        

1、当top=0时，表示下一个要插入元素的位置，top等于多少栈里就有多少个元素

再详细的我也解释不出来了┭┮﹏┭┮

2、当top=-1时，表示栈顶元素的下标，下标等于-1时表示栈中没有有效元素

结论：相比于0，使用-1进行初始化可以更好地反映出该对象尚未包含任何有效数据项，同时还与我们学习的数组下标的概念契合（即下标为0表示数组第一个数字而当top=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->a = tmp;
		pst->capacity = newCapacity;
	}

    //如果栈未满则进行入栈操作（若初始化时pop=-1，则下面两行代码交换执行顺序）
	pst->a[pst->top] = x;    //此时pop表示的是栈顶元素的下一个元素的下标 
	pst->top++;              //top表示的下标数++
}

出栈

//出栈
void STPop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);

    //直接对top执行减减操作以获取实际数组元素下标
    pst->top--;
}

获取栈顶元素

// 获取栈顶元素
STDataType STTop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);
	
    //当初始化top=0时，top的值与实际数组元素下标的值之间的关系是：实际下标 = top-1
    //所以这里要进行减一操作得到实际的数组元素下标后再输出
	return pst->a[pst->top - 1];
}

获取栈中有效元素个数

//获取栈中有效元素个数
int STSize(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
    
    //初始化top=0，则top等于多少栈中就有多少个元素
	return pst->top;
}

检测栈是否为空

//检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* pst)
{
	//首先要指向一个栈
	assert(pst);
	
    //如果pst->top不为空则返回结果为真，为空则返回假
	return pst->top == NULL;
}

销毁栈

// 销毁栈
void STDestroy(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	
    //正常操作不再过多复述
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

最终代码：

Stack.h文件：

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

//支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;	  //表示栈顶位置
	int capacity; //栈的容量
}ST;

// 初始化栈
void STInit(ST* ps);

// 销毁栈
void STDestroy(ST* ps);

// 入栈
void STPush(ST* ps, STDataType data);

// 出栈
void STPop(ST* ps);

// 获取栈顶元素
STDataType STTop(ST* ps);

// 获取栈中有效元素个数
int STSize(ST* ps);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* ps);

Stack.c文件

#include "Stack.h"

// 初始化栈
void STInit(ST* pst)
{
    //首先要指向一个栈
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;    //令pop表示栈顶元素的下一个元素的下标
}

// 销毁栈
void STDestroy(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	
    //正常操作不再过多复述
	free(pst->a);
	pst->a = NULL;
	pst->top = 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->a = tmp;
		pst->capacity = newCapacity;
	}

    //如果栈未满则进行入栈操作（若初始化时pop=-1，则下面两行代码交换执行顺序）
	pst->a[pst->top] = x;    //此时pop表示的是栈顶元素的下一个元素的下标 
	pst->top++;              //top表示的下标数++
}

//出栈
void STPop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);

    //直接对top执行减减操作以获取实际数组元素下标
    pst->top--;
}

// 获取栈顶元素
STDataType STTop(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
	//top<0表示栈为空，top=0表示没有元素入栈，存在这两种情况就不能执行出栈操作（可以提供的图理解）
	assert(pst->top > 0);
	
    //当初始化top=0时，top的值与实际数组元素下标的值之间的关系是：实际下标 = top-1
    //所以这里要进行减一操作得到实际的数组元素下标后再输出
	return pst->a[pst->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* pst)
{
    //首先要指向一个栈
	assert(pst);
    
    //初始化top=0，则top等于多少栈中就有多少个元素
	return pst->top;
}

//检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* pst)
{
	//首先要指向一个栈
	assert(pst);
	
    //如果pst->top不为空则返回结果为真，为空则返回假
	return pst->top == NULL;
}

test.c文件： 

#include "Stack.h"

int main()
{
	ST s;
    //初始化栈
	STInit(&s);
    //入栈
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);

    //出栈
	while (!STEmpty(&s)) //只要栈不为空就一直出栈
	{
		printf("%d ", STTop(&s)); //打印每一个栈顶元素
		STPop(&s); //打印完成后就让该栈顶元素出栈
	}

	printf("\n");
	return 0;
}

选择练习

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

解析：请自行演算🤡

栈的OJ题

20. 有效的括号 - 力扣（LeetCode）

具体解题思路如下图所示：

括号不仅仅是数量匹配，顺序也要匹配 

文字解释： 读取到左括号就放入栈中，读取到右括号就将其对应的左括号，如果转换后得到的的左括号与栈中存放的左括号相同（实际上比较的是ASCII码）则证明有一对儿匹配的内容括号，此时将原来栈中存放的左括号出栈，然后进行下一次的读取操作

字符串中如果第一个是右括号就直接返回假 

//右括号转换为左括号
char pairs(char a) 
{
    if (a == '}') 
    {
        return '{';
    }

    if (a == ']')
    {
         return '[';
    }

    if (a == ')') 
    {
        return '(';
    }
        
    return 0;
}

bool isValid(char* s) 
{
    //获取数组长度
    int n = strlen(s);

    //如果数量不满足成对情况则直接返回flase
    if (n % 2 == 1) 
    {
        return false;
    }

    //stk数组用来表示存储左括号的栈（起始为空栈），top表示下一个要插入元素的位置
    int stk[n + 1], top = 0;

    //逐个读取原字符串中的字符并进行循环匹配
    for (int i = 0; i < n; i++) 
    {
        //读取源自符串中的内容，如果此时的字符为左括号则ch=0，为右括号则ch存储与之相对的左括号
        char ch = pairs(s[i]);
        if (ch) 
        {
            //一旦存在一对不匹配的情况则直接返回flase
            if (top == 0 || stk[top - 1] != ch) 
            {
                return false;
            }
            //如果匹配则将栈顶元素出栈（左括号出栈）
            top--;
        } 
        //如果ch为空证明此时读取的是左括号，将入栈以便下一次的判断
        else
        {
            stk[top++] = s[i];
        }
    }

    //如果源自符串中括号的顺序和数量均匹配，则栈中最后的结果为空，top==0的结果为真
    return top == 0;
}

~未完待续~

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

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

相关文章

4.2 Windows驱动开发：内核中进程线程与模块

4.2 Windows驱动开发：内核中进程线程与模块

内核进程线程和模块是操作系统内核中非常重要的概念。它们是操作系统的核心部分&#xff0c;用于管理系统资源和处理系统请求。在驱动安全开发中&#xff0c;理解内核进程线程和模块的概念对于编写安全的内核驱动程序至关重要。 内核进程是在操作系统内核中运行的程序。每个进…
阅读更多...
键鼠自动化2.0展示

键鼠自动化2.0展示

软件介绍&#xff1a;桌面键鼠自动化工具 Qtc 编写&#xff1a; 本软件采用Qt C编写&#xff0c;旨在提供高效、跨平台的桌面键鼠自动化解决方案。Qt C框架的选择确保了软件的稳定性、可靠性&#xff0c;并通过其图形用户界面实现了用户友好的操作体验。 鼠标移动与点击&#…
阅读更多...
MySQL 的执行原理（一）

MySQL 的执行原理（一）

5.1 单表访问之索引合并 我们前边说过 MySQL 在一般情况下执行一个查询时最多只会用到单个二级 索引&#xff0c;但存在有特殊情况&#xff0c;在这些特殊情况下也可能在一个查询中使用到多个二 级索引&#xff0c;MySQL 中这种使用到多个索引来完成一次查询的执行方法称之为&…
阅读更多...
物联网AI MicroPython学习之语法 SPI串行外设通信

物联网AI MicroPython学习之语法 SPI串行外设通信

学物联网&#xff0c;来万物简单IoT物联网&#xff01;&#xff01; SPI 介绍 模块功能: SPI串行外设驱动 接口说明 SPI - 构建SPI对象 函数原型&#xff1a;SPI(id, baudrate&#xff0c;polarity, phase&#xff0c;sck, mosi, miso)参数说明&#xff1a; 参数类型必选参…
阅读更多...
webAPP基础学习

webAPP基础学习

###视觉基础 part-I ####1.面试中常见的像素问题 >什么是像素? *1.什么是px? px-虚拟像素,css像素的单位 px是一个相对单位,相对于设备像素而言 >相对性 a.相对于同一个设备,css像素的可变的 css像素物理像素>会受到缩放的影响 css像素缩放倍数*单个物理像…
阅读更多...
django理解02 前后端分离中的问题

django理解02 前后端分离中的问题

前后端分离相对于传统方式的问题 前后端数据交换的问题跨域问题 页面js往自身程序&#xff08;django服务&#xff09;发送请求&#xff0c;这是浏览器默认接受响应 而请求其它地方是浏览器认为存在潜在危险。自动隔离请求&#xff01;&#xff01;&#xff01; 跨域问题的解决…
阅读更多...
蓝桥杯 枚举

蓝桥杯 枚举

例题讲解 特别数的和 #include<iostream> using namespace std; bool ifspecial(int n){while(n){if(n%100||n%101||n%102||n%109){return true;} n/10;}return false; } int main(){int n;cin>>n;int sum0;for(int i1;i<n;i){if(ifspecial(i)){sumi;}}cout&l…
阅读更多...
K-Means算法进行分类

K-Means算法进行分类

已知数据集D中有9个数据点&#xff0c;分别是&#xff08;1,2&#xff09;&#xff0c;(2,3), (2,1), (3,1),(2,4),(3,5),(4,3),(1,5),(4,2)。采用K-Means算法进行聚类&#xff0c;k2&#xff0c;设初始中心点为&#xff08;1.1,2.2&#xff09;&#xff0c;&#xff08;2.3,3.…
阅读更多...
LitCTF2023 - Reverse方向 全WP

LitCTF2023 - Reverse方向 全WP

文章目录 [LitCTF 2023]世界上最棒的程序员[LitCTF 2023]ez_XOR[LitCTF 2023]enbase64[LitCTF 2023]snake[LitCTF 2023]程序和人有一个能跑就行了[LitCTF 2023]debase64[LitCTF 2023]For AiurLitCTF{Pylon_OverCharge!!_We_Must_construc7_addition4l_pylons} [LitCTF 2023]世界…
阅读更多...
【giszz笔记】产品设计标准流程【6】

【giszz笔记】产品设计标准流程【6】

目录 六、组织评审 1.评审的类型 2.评审的人员——谁参加评审 3.评审的核心——怎么提问 & 答案谁说了算 4.评审的流程——前中后三部曲 5.评审的标的——漂亮的靶子 6.避免被“烤”问的一些技巧 7.搞几次评审比较好 这个产品设计系列&#xff0c;陆陆续续写了6篇了…
阅读更多...
JavaEE进阶（1）Java EE 简述（Java EE 发展历程、什么是Web开发? Web网站的工作流程、什么是框架？Java EE 框架学习概览）

JavaEE进阶（1）Java EE 简述（Java EE 发展历程、什么是Web开发? Web网站的工作流程、什么是框架？Java EE 框架学习概览）

目录 Java EE 简述 Java EE 发展历程 什么是Web开发? Web网站的工作流程 什么是框架 框架的定义 源于建筑行业的类比 框架的作用 Java EE 框架学习概览 1. Spring 2. Spring Boot 3. Spring MVC 4. Mybatis 框架之间的关系 Java EE 简述 Java EE是Java平台的企…
阅读更多...
C#实现观察者模式

C#实现观察者模式

观察者模式是一种软件设计模式&#xff0c;当一个对象的状态发生变化时&#xff0c;其所有依赖者都会自动得到通知。 观察者模式也被称为“发布-订阅”模式&#xff0c;它定义了对象之间的一对多的依赖性&#xff0c;当一个对象状态改变时&#xff0c;所有依赖于它的对象都会得…
阅读更多...
IO多路转接之select和poll

IO多路转接之select和poll

目录 一. IO多路转接的概念 二. 通过select实现IO多路转接 2.1 select接口 2.2 Select服务器的实现 2.3 select实现IO多路转接的优缺点 三. 通过poll实现IO多路转接 3.1 poll接口 3.2 Poll服务器的实现 3.3 poll实现IO多路转接的优缺点 四. 总结 一. IO多路转接的概念…
阅读更多...
Python uiautomation获取微信内容！聊天记录、聊天列表、全都可获取

Python uiautomation获取微信内容！聊天记录、聊天列表、全都可获取

Python uiautomation 是一个用于自动化 GUI 测试和操作的库&#xff0c;它可以模拟用户操作来执行各种任务。 通过这个库&#xff0c;可以使用Python脚本模拟人工点击&#xff0c;人工操作界面。本文使用 Python uiautomation 进行微信电脑版的操作。 以下是本次实验的版本号。…
阅读更多...
C语言从入门到精通之【其他运算符】

C语言从入门到精通之【其他运算符】

sizeof运算符和size_t sizeof运算符以字节为单位返回运算对象的大小。 例如 &#xff1a;sizeof(int) 打印转换说明&#xff0c;使用C99新增的**%zd转换说明 – 如果编译器不支持%zd&#xff0c;请将其改 成%u或%lu**。 C 语言规定&#xff0c;sizeof 返回 size_t 类型的值…
阅读更多...
安装银河麒麟linux系统docker(docker-compose)环境，注意事项(一定能解决,有环境资源)

安装银河麒麟linux系统docker(docker-compose)环境，注意事项(一定能解决,有环境资源)

1：安装docker环境必须使用麒麟的版本如下 2：使用docker-compse up -d启动容器遇到的文件 故障1：如果运行docker-compose up 报“Cannot create redo log files because data files are corrupt or the database was not shut down cleanly after creating the data files”…
阅读更多...
基于单片机教室人数实时检测系统仿真及源程序

基于单片机教室人数实时检测系统仿真及源程序

一、系统方案 1、本设计采用51单片机作为主控器。 2、红外传感器检测进出人数&#xff0c;液晶1602显示。 3、按键最多容纳人数&#xff0c;烟雾报警。 二、硬件设计 原理图如下&#xff1a; 三、单片机软件设计 1、首先是系统初始化 void lcd_init() { lcd_write_com(0x38…
阅读更多...
为什么选择B+树作为数据库索引结构？

为什么选择B+树作为数据库索引结构？

背景 首先&#xff0c;来谈谈B树。为什么要使用B树&#xff1f;我们需要明白以下两个事实&#xff1a; 【事实1】 不同容量的存储器&#xff0c;访问速度差异悬殊。以磁盘和内存为例&#xff0c;访问磁盘的时间大概是ms级的&#xff0c;访问内存的时间大概是ns级的。有个形象…
阅读更多...
mongodb使用简单文档

mongodb使用简单文档

1、mongodb安装与卸载 1.1、安装 python -m pip install pymongo 或 pip install pymongo如果要安装指定版本&#xff1a; python -m pip install pymongo3.5.1对已有的版本进行升级&#xff1a; python -m pip install --upgrade pymongo1.2、卸载 pip uninstall pymongo…
阅读更多...
性能测试常见问题总结

性能测试常见问题总结

01 硬件上的性能瓶颈 指的是CPU、内存、I/O读写速率&#xff0c;磁盘空间方面的问题。 02 网络上的性能瓶颈 指的网络带宽&#xff0c;网络波动&#xff0c;延时&#xff0c;丢包等。 03 应用程序上的性能瓶颈 指的是开发人员新开发出来的应用程序。 04 数据库的性能瓶颈…
阅读更多...
最新文章

Copyright @ 2022~2023