扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言实现栈的示例详解
  • 823

0
分享到

C语言实现栈的示例详解

2024-04-02 19:04:59 823人浏览 薄情痞子
摘要

目录前言一. 什么是栈二. 使用什么来实现栈三. 栈的实现3.1 头文件3.2 函数实现3.3 完整代码四. 栈的用处前言 前一段时间，我们试着用C语言实现了数据结构中的顺序表，单链

前言

前一段时间，我们试着用C语言实现了数据结构中的顺序表，单链表，双向循环链表。今天我们再用C语言来实现另一种特殊的线性结构：栈

一. 什么是栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

类似于步枪的子弹夹，后进去的子弹先发射出来以后，前面的子弹才可以发射。

二. 使用什么来实现栈

前一段时间，我们学习了两种线性表，一种是顺序表，一种是链表，那么对于栈我们该用哪一个来实现比较好呢

首先我们来对比一下线性表和链表

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问可以直接访问任何元素必须从头节点开始往后寻找
任意位置插入或删除元素要搬移其他的元素，效率低。只需要修改节点的指针指向，效率高
插入动态顺序表，当空间不够时需要扩容无容量概念，需要就申请，不用就释放
应用场景元素高效存储，并且需要频繁访问需要在任意位置插入或者删除频繁

综合以上来看，我认为实现一个栈，使用顺序表比较好。

1.栈是先进后出，使用顺序表，在元素出栈后更容易找到新的栈顶。

2.顺序表CPU高速缓存命中率高，可以减少CPU去内存拿数据的次数，速度快，效率高。

三. 栈的实现

3.1 头文件

1.包含的标准库

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //C语言中的bool类型需要这个头文件
#include <assert.h>

2.定义结构体

typedef int STDateType;//栈中元素的数据类型

typedef struct Stack
{
	STDateType* a; //顺序表
	int top; //栈顶
	int capacity; //栈的容量
}Stack;

3.函数的声明

void StackInti(Stack* ps);
// 栈的初始化
void StackDestory(Stack* ps);
// 栈的销毁
void StackPush(Stack* ps, STDateType x);
// 入栈
void StackPop(Stack* ps);
// 出栈
bool StackEmpty(Stack* ps);
// 判断栈是否为空
STDateType StackTop(Stack* ps);
// 取栈顶元素

3.2 函数实现

1. 栈的初始化

我们用assert（断言），防止ps为空指针。

void StackInti(Stack* ps)
{
    assert(ps);
    
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

2. 栈的销毁

释放顺序表。

void StackDestory(Stack* ps)
{
	assert(ps);

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

3.入栈

void StackPush(Stack* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity) //判断容量是否足够
	{
		int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
		if (ps->a == NULL)
		{
			printf("ralloc error");
			exit(-1);
		}
		ps->capacity = newCapcity;
	}

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

4. 出栈

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0); //空栈不能被删除

	ps->top--;
}

5. 判断栈是否为空

bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top == 0; // 如果为空则返回true，否则返回false
}

6. 取栈顶元素

STDateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);//空栈不能被删除

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

这样我们就实现了一个简单的栈

3.3 完整代码

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

typedef int STDateType;

typedef struct Stack
{
	STDateType* a;
	int top;
	int capacity;
}Stack;

void StackInti(Stack* ps)
{
	assert(ps);
	
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestory(Stack* ps)
{
	assert(ps);

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

void StackPush(Stack* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
		if (ps->a == NULL)
		{
			printf("ralloc error");
			exit(-1);
		}
		ps->capacity = newCapcity;
	}

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

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

STDateType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

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

四. 栈的用处

我们好不容易实现了一个栈，接下来我们来做个题看看栈有什么用吧。

题目描述

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

基础框架

C语言的基础框架如下

bool isValid(char * s){

​​​​​​​}

解题思路

左括号一定要和右括号对齐，非常满足栈的特性

我们可以将所有的左括号存入一个栈中。

然后遇到右括号，就出栈，判断是否匹配。

直到栈为空且字符串中的括号也遍历完了，那么所有括号就正确的匹配了。

代码详解

// 1.因为C语言并没有现成的栈，所以我们需要自己造轮子，先写个栈再说
typedef char STDateType; // 更改数据类型为char

typedef struct Stack
{
	STDateType* a;
	int top;
	int capacity;
}Stack;

void StackInti(Stack* ps)
{
	assert(ps);
	
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestory(Stack* ps)
{
	assert(ps);

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

void StackPush(Stack* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
		if (ps->a == NULL)
		{
			printf("ralloc error");
			exit(-1);
		}
		ps->capacity = newCapcity;
	}

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

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

STDateType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

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

bool isValid(char * s){
    Stack a;
    StackInti(&a);
    while(*s)
    {
        if (*s == '(' || *s == '[' || *s == '{') //入栈
        {
            StackPush(&a, *s);
        } 
        else //出栈
        {
            if(StackEmpty(&a)) //右括号多一个的情况
            {
                return false;
            }

            char tmp = StackTop(&a);
            StackPop(&a);
            if ((*s == ')' && tmp != '(') 
              ||(*s == ']' && tmp != '[')
              ||(*s == '}' && tmp != '{') )
            {
                return false;
            }
        }
        s++;
    }
    return StackEmpty(&a); //防止出现多一个左括号的情况
}

到此这篇关于C语言实现栈的示例详解的文章就介绍到这了,更多相关C语言 栈内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C语言实现栈的示例详解

本文链接: https://lsjlt.com/news/152942.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C语言实现栈的示例详解
    目录前言一. 什么是栈二. 使用什么来实现栈三. 栈的实现3.1 头文件3.2 函数实现3.3 完整代码四. 栈的用处前言 前一段时间，我们试着用C语言实现了数据结构中的顺序表，单链...
    99+
    2024-04-02
  • C语言实现栈的示例代码
    目录一、了解栈的结构特点二、具体实现补充 栈的用处一、了解栈的结构特点 栈是一种特殊的线性表，只允许从一端进出数据，称为后进先出，先进后出。 压栈：栈的插入操作叫做进栈/压...
    99+
    2024-04-02
  • C语言进阶栈帧示例详解教程
    目录正片开始栈有什么用？寄存器main函数创建局部变量创建函数部分形参与实参正片开始 今天来讲讲我对栈帧创建与销毁的拙见。理解什么是栈帧首先知道什么是栈： 在数据结构中, 栈是限定仅...
    99+
    2024-04-02
  • C语言 栈与数组的实现详解
    目录栈的实现栈的定义数组实现静态栈动态栈链栈栈的实现 首先我们思考一个问题，什么是栈？ 栈是数据结构的一种，栈在我们日常编码中遇到的非常多，很多人对栈的接触可能仅仅局限在 递归使用的...
    99+
    2024-04-02
  • C语言实现阶乘的示例详解
    目录前言1.阶乘实现1.1理论步骤1.2实践结果2.连续乘层相加实现2.1理论步骤2.2实践结果前言 在现实中，我们做数学题总会遇到阶乘问题，这在计算机中也不例外。 那我们应该怎么实...
    99+
    2024-04-02
  • C语言实现队列的示例详解
    目录前言一. 什么是队列二. 使用什么来实现栈三. 队列的实现3.1头文件3.2 函数的实现四.完整代码前言 前一段时间，我们试着用C语言实现了数据结构中的顺序表，单链表，双向循环链...
    99+
    2024-04-02
  • C语言超详细讲解栈与队列实现实例
    目录1.思考-12.栈基本操作的实现2.1 初始化栈2.2 入栈2.3 出栈2.4 获取栈顶数据2.5 获取栈中有效元素个数2.6 判断栈是否为空2.7 销毁栈3.测试3.1 测试3...
    99+
    2024-04-02
  • C语言详解如何实现顺序栈
    目录顺序栈的定义顺序栈的理解准备工作具体实现今天说的是关于数据结构顺序栈的一些基本操作c语言实现。 顺序栈的定义 首先，我们先来简单了解一下顺序栈，前面线性表我们知道，根据顺序存储或...
    99+
    2024-04-02
  • C语言之包含min函数的栈实例详解
    目录一、题目描述二、思路分析三、整体代码总结一、题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时...
    99+
    2024-04-02
  • C语言中栈的两种实现方法详解
    目录一、顺序栈二、链式栈总结一、顺序栈 #include<stdio.h> #include<stdlib.h> #define maxsize 64 ...
    99+
    2024-04-02
  • C语言实现单元测试的示例详解
    目录前沿使用前提测试框架如下测试方法编写文件验证前沿 单元测试（unit testing），是指对软件中的最小可测试单元进行检查和验证。对于单元测试中单元的含义，一般来说，要根据实际...
    99+
    2024-04-02
  • C语言栈与队列相互实现详解
    目录一、本章重点二、队列实现栈三、栈实现队列四、解题思路总结一、本章重点 用两个队列实现栈用两个栈实现队列解题思路总结 二、队列实现栈  我们有两个队列：  ...
    99+
    2024-04-02
  • C语言解决堆栈括号匹配问题示例详解
    目录首先构建栈调用匹配函数代码调用1.括号匹配问题就是当遇到{（ [这些左括号的时 将括号字符入栈 2.当遇到右括号时判断栈顶元素是不是与左括号匹配如果匹配就出栈 如果不匹配就直接结...
    99+
    2024-04-02
  • 详解C语言之堆栈
    目录一、何为堆栈？二、思维导图三、代码1、顺序堆栈2、链式堆栈总结 一、何为堆栈？ a.堆栈是一种特殊的线性表 b.堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其不同点...
    99+
    2024-04-02
  • C语言超详细讲解栈的实现及代码
    目录前言栈的概念栈的结构栈的实现创建栈结构初始化栈销毁栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空总代码Stack.h 文件Stack.c 文件Test.c 文件前言 栈...
    99+
    2024-04-02
  • C语言示例代码讲解栈与队列
    目录栈栈的定义顺序栈顺序栈的定义顺序栈的初始化顺序栈的入栈顺序栈的出栈取顺序栈的栈顶元素链栈队列队列的定义队列的顺序表达与实现队列顺序存储结构假溢出循环队列循环队列的初始化循环队列的...
    99+
    2024-04-02
  • C语言函数栈帧详解
    目录前言一.函数栈帧是什么？二、栈帧准备知识1.内存分区2.什么是栈？三、详解栈帧创建与销毁全过程调用函数之前：将传入函数的值放入栈中函数执行：1.保护当前ebp2.创建所需调用函数...
    99+
    2024-04-02
  • C语言实现冒泡排序算法的示例详解
    目录1. 问题描述2. 问题分析3. 算法设计动图演示4. 程序设计设计一设计二结论5. 流程框架6. 代码实现7. 问题拓展1. 问题描述 对N个整数（数据由键盘输入）进行升序排列...
    99+
    2024-04-02
  • C语言实现生成新春福字的示例详解
    目录主要代码字面量以及数据结构定义一个回调函数，刷新福字应用初始化程序主程序效果展示快新年了，支付宝扫福活动又开始了，每次都要百度找福，这次不想找了，自己写一个程序生成各种字体的福字...
    99+
    2024-04-02
  • C语言用栈模拟实现队列问题详解
    目录题目描述题目链接思路分析代码实现题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。 你只能使用标准的栈操作...
    99+
    2024-04-02
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作