备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】C语言实现顺序栈(附完整运行代码)

2024-03-30 37
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】C语言实现顺序栈(附完整运行代码)

一.了解项目功能

在本次项目中我们的目标是实现一个顺序栈:

该顺序栈使用动态内存分配空间,可以用来存储任意数量的同类型数据.

顺序栈结构体需要包含三个要素:存放数据的数组arr,栈顶元素下标top,栈容量capacity.

顺序栈程序提供的功能有:

  1. 顺序栈的初始化
  2. 顺序栈的销毁
  3. 顺序栈的入栈
  4. 顺序栈的出栈
  5. 顺序栈的长度
  6. 顺序栈判空
  7. 顺序栈取栈顶元素

二.项目功能演示

要编写一个顺序栈项目，首先要明确我们想要达到的效果是什么样，下面我将用vs2022编译器来为大家演示一下顺序栈程序运行时的样子：

三.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍，我们已经对顺序栈的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！

！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。

1.实现顺序栈程序菜单

菜单部分的逻辑比较简单，就是利用C语言printf函数打印出这个菜单界面即可。但要注意菜单的标序要和后续switch...case语句的分支相应,以免导致后续执行语句错乱的问题.基础问题就不过多赘述了，代码如下：

该部分功能实现代码如下: 

void STMenu()
{
  printf("**********************************\n");
  printf("******请选择要进行的操作    ******\n");
  printf("******1.顺序栈入栈          ******\n");
  printf("******2.顺序栈出栈          ******\n");
  printf("******3.取栈顶元素          ******\n");
  printf("******4.判断栈空            ******\n");
  printf("******5.查询当前栈长        ******\n");
  printf("******6.清空顺序栈          ******\n");
  printf("******7.销毁顺序栈          ******\n");
  printf("******0.退出顺序栈程序      ******\n");
  printf("**********************************\n");
  printf("请选择:>");
 
}

2.实现顺序栈程序功能可循环使用

由于我们要实现顺序栈的功能可以反复使用的逻辑，且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.

该部分功能实现代码如下:

int main()
{
  ST st;
  STInit(&st);
    int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
    do          //使用do...while实现
    {
        STMenu();
        scanf("%d", &swi);
 
        switch (swi)
        {
        case 0:
            STDestroy(&st);
            printf("您已退出程序:>\n");
            // 释放链表内存
            break;
 
        case 1:
            printf("请输入要入栈的数据:>");
            STDataType pushback_data = 0;
            scanf("%d", &pushback_data);
 
            STPush(&st, pushback_data);
 
            printf("已成功入栈:>\n");
            break;
 
        case 2:
            printf("栈顶元素%d已成功出栈\n", STTop(&st));
            STPop(&st);
 
            break;
 
        case 3:
            printf("栈顶元素为:");
            STDataType sttop = STTop(&st);
 
            printf("%d\n", sttop);
 
            break;
 
        case 4:
            if (!STEmpty(&st))
            {
                printf("当前栈不为空\n");
            }
            else
            {
                printf("当前栈为空栈\n");
            }
 
            break;
 
        case 5:
            printf("当前栈长为:");
            int stsize = STSize(&st);
            printf("%d\n", stsize);
            break;
 
        case 6:
            STDestroy(&st);
            STInit(&st);
            printf("顺序栈已清空:>\n");
 
            break;
 
        case 7:
            STDestroy(&st);
            printf("顺序栈已销毁:>\n");
 
            break;
 
        default:
            printf("输入错误,请重新输入\n");
            break;
        }
    } while (swi);
 
 
  return 0;
}

3.创建顺序栈

创建顺序栈成员的结构体应该包括:存放数据的数组arr,栈顶元素下标top,栈容量capacity.

因此我们创建Stack结构体类型时应由一个数组及两个整型组成.

这里的第9行使用的typedef类定义的作用是方便我们后续在使用顺序栈时对存储的数据类型做更改,比如后续我们不想存储int类型数据了,就可以很方便的在这里对数组类型做更改.比如改成char类型,或者double类型,甚至改成任意自己构造的结构类型.

综上,该部分代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
 
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int STDataType;
 
typedef struct Stack
{
  int *arr;
  int top;
  int capacity;
}ST;

4.初始化顺序栈

初始化顺序栈的逻辑和初始化顺序表一样,我们在初始化时为栈开辟4个数据类型的数组空间,然后将顺序栈的容量改为4,栈顶置为0即可.

该部分的功能实现代码如下:

void STInit(ST* ps)
{
  assert(ps);
 
  ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->arr == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
  ps->capacity = 4;
  ps->top = 0;   //top表示栈顶元素的下一个
                 //top指向栈顶元素的话,top给-1
  
}

5.顺序栈的入栈

顺序栈在入栈时,需要先判断一下栈内元素是否已满,如果满了则需要给栈扩容.(如下代码5-18行均是在执行顺序栈查满扩容逻辑)

如果没满则将新元素赋值给栈顶指针top,再将top++,使其始终指向栈顶的下一个元素位置.

该部分的功能实现代码如下: 

void STPush(ST* ps, STDataType x)
{
  assert(ps);
 
  if (ps->top == ps->capacity)//扩容
  {
    STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail::\n");
      return;
    }
 
    ps->arr = tmp;
    ps->capacity *= 2;
 
  }
 
  ps->arr[ps->top] = x;
  ps->top++;
 
}

6.顺序栈的出栈

顺序栈的出栈就相当于顺序表的尾删,那么我们同顺序表一样移动栈顶下标位置即可.

顺序表尾删示意图:

该部分的功能实现代码如下: 

void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
  ps->top--;
}

7.顺序栈取栈顶元素

根据我们之前的设定,栈为空时top=0:

那么当栈中进入一个元素时,top++后top=1,而栈顶元素a1的下标等于0,所以我们的top设计其实是指向栈顶元素的下一个位置的:

因此在取栈顶函数中,我们要返回的栈顶数组下标应该是top-1.

该部分的功能实现代码如下: 

STDataType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
  return ps->arr[ps->top - 1];
}

8.顺序栈的长度

因为top指向的是栈顶元素的下一个位置,因此top的大小正好是栈的长度,所以求栈长函数我们对ps断言后可以直接返回top.

该部分的功能实现代码如下:

int STSize(ST* ps)
{
  assert(ps);
 
  return ps->top;
}

9.顺序栈的判空

顺序栈判空的逻辑是:如果栈为空返回true(真),否则返回false(假).

因此我们还是拿top来判断,如果top=0,会return true,意味着栈为空.

否则会return false,意味着栈不为空.

该部分的功能实现代码如下:

bool STEmpty(ST* ps)//判空,为空则真
{
  assert(ps);
 
  return ps->top==0;
}

10.顺序栈的销毁

当我们使用完顺序栈想要退出程序时,就应该将之前动态开辟的内存释放掉,还给操作系统.即销毁顺序栈.

我们使用free()函数释放掉之前动态开辟的数组arr,然后将arr置为空指针,最后将top,capacity的值置为0即可.

该部分的功能实现代码如下:

void STDestroy(ST* ps)
{
  assert(ps);
 
  free(ps->arr);
  ps->arr = NULL;
  ps->top = 0;
  ps->capacity = 0;
 
}

四.项目完整代码

我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:

test.c文件

#include"Stack.h"
 
int main()
{
  ST st;
  STInit(&st);
    int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
    do          //使用do...while实现
    {
        STMenu();
        scanf("%d", &swi);
 
        switch (swi)
        {
        case 0:
            STDestroy(&st);
            printf("您已退出程序:>\n");
            // 释放链表内存
            break;
 
        case 1:
            printf("请输入要入栈的数据:>");
            STDataType pushback_data = 0;
            scanf("%d", &pushback_data);
 
            STPush(&st, pushback_data);
 
            printf("已成功入栈:>\n");
            break;
 
        case 2:
            printf("栈顶元素%d已成功出栈\n", STTop(&st));
            STPop(&st);
 
            break;
 
        case 3:
            printf("栈顶元素为:");
            STDataType sttop = STTop(&st);
 
            printf("%d\n", sttop);
 
            break;
 
        case 4:
            if (!STEmpty(&st))
            {
                printf("当前栈不为空\n");
            }
            else
            {
                printf("当前栈为空栈\n");
            }
 
            break;
 
        case 5:
            printf("当前栈长为:");
            int stsize = STSize(&st);
            printf("%d\n", stsize);
 
            break;
 
        case 6:
            STDestroy(&st);
            STInit(&st);
            printf("顺序栈已清空:>\n");
 
            break;
 
        case 7:
            STDestroy(&st);
            printf("顺序栈已销毁:>\n");
 
            break;
 
        default:
            printf("输入错误,请重新输入\n");
 
            break;
        }
    } while (swi);
 
  return 0;
}

 Stack.c 文件

#include"Stack.h"
 
void STInit(ST* ps)
{
  assert(ps);
 
  ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->arr == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
  ps->capacity = 4;
  ps->top = 0;   //top表示栈顶元素的下一个
                 //top指向栈顶元素的话,top给-1
  
}
 
void STDestroy(ST* ps)
{
  assert(ps);
 
  free(ps->arr);
  ps->arr = NULL;
  ps->top = 0;
  ps->capacity = 0;
 
}
 
void STPush(ST* ps, STDataType x)
{
  assert(ps);
 
  if (ps->top == ps->capacity)//扩容
  {
    STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STDataType)*ps->capacity*2);
    if (tmp == NULL)
    {
      perror("realloc fail::\n");
      return;
    }
 
    ps->arr = tmp;
    ps->capacity *= 2;
 
  }
 
  ps->arr[ps->top] = x;
  ps->top++;
 
}
 
void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
  ps->top--;
}
 
int STSize(ST* ps)
{
  assert(ps);
 
  return ps->top;
}
 
bool STEmpty(ST* ps)//判空,为空则真
{
  assert(ps);
 
  return ps->top==0;
}
 
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
  return ps->arr[ps->top - 1];
}
 
void STMenu()
{
  printf("**********************************\n");
  printf("******请选择要进行的操作    ******\n");
  printf("******1.顺序栈入栈          ******\n");
  printf("******2.顺序栈出栈          ******\n");
  printf("******3.取栈顶元素          ******\n");
  printf("******4.判断栈空            ******\n");
  printf("******5.查询当前栈长        ******\n");
  printf("******6.清空顺序栈          ******\n");
  printf("******7.销毁顺序栈          ******\n");
  printf("******0.退出顺序栈程序      ******\n");
  printf("**********************************\n");
  printf("请选择:>");
}

Stack.h文件

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
 
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int STDataType;
 
typedef struct Stack
{
  int *arr;
  int top;
  int capacity;
}ST;
 
void STInit(ST* ps);
void STDestroy(ST* ps);
 
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
 
int STSize(ST* ps);
 
bool STEmpty(ST* ps);//判空,为空则真
 
STDataType STTop(ST* ps);
 
void STMenu();

结语

希望这篇顺序栈的C语言实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.


学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

数据结构栈与队列篇思维导图:


文章标签：
C语言
存储
编译器
关键词：
数据结构栈
C语言代码
数据结构顺序栈
C语言数据结构
数据结构c语言
修修修也
目录
相关文章
热爱嵌入式的小佳同学
|
6天前
|
存储 NoSQL C语言
数据结构——顺序栈与链式栈的实现-2
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
15 1
数据结构——顺序栈与链式栈的实现-2
热爱嵌入式的小佳同学
|
6天前
|
存储 C语言
数据结构——顺序栈与链式栈的实现-1
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
19 0
数据结构——顺序栈与链式栈的实现-1
天玑y
|
6天前
|
C++
数据结构（顺序栈
数据结构（顺序栈
天玑y
14 2
秦jh
|
6天前
|
搜索推荐 C语言
【C语言/数据结构】排序（归并排序|计数排序|排序算法复杂度）
【C语言/数据结构】排序（归并排序|计数排序|排序算法复杂度）
秦jh
11 0
秦jh
|
6天前
|
C语言
【C语言/数据结构】排序（快速排序及多种优化|递归及非递归版本）
【C语言/数据结构】排序（快速排序及多种优化|递归及非递归版本）
秦jh
11 0
秦jh
|
6天前
|
C语言
【C语言/数据结构】排序（选择排序，推排序，冒泡排序）
【C语言/数据结构】排序（选择排序，推排序，冒泡排序）
秦jh
14 0
颦颦Admin@123
|
6天前
|
C语言
C语言：内存函数（memcpy memmove memset memcmp使用）
C语言：内存函数（memcpy memmove memset memcmp使用）
颦颦Admin@123
20 0
悲伤小伞
|
4天前
|
C语言
C语言—内存函数的实现和模拟实现（内存函数的丝绸之路）
C语言—内存函数的实现和模拟实现（内存函数的丝绸之路）
悲伤小伞
18 0
悲伤小伞
|
4天前
|
C语言
C语言—字符函数与字符串函数（字符问题变简单的关键之技）
C语言—字符函数与字符串函数（字符问题变简单的关键之技）
悲伤小伞
6 0
GR鲸鱼
|
19小时前
|
C语言 C++
C语言进阶⑭(内存函数_以字节操作)momcpy+mommove+memcmp+memset
C语言进阶⑭(内存函数_以字节操作)momcpy+mommove+memcmp+memset
GR鲸鱼
5 0

热门文章

最新文章

  • 1
    C语言实现矩阵转置
  • 2
    C语言C/Ｓ架构PACS影像归档和通信系统源码 医院PACS系统源码
  • 3
    pta浙大版《C语言程序设计（第3版）》 习题6-4 使用函数输出指定范围内的Fibonacci数 (20分)
  • 4
    C语言基础知识：数据在内存中的存储解析（整数，浮点数）
  • 5
    【精通C语言】：分支结构if语句的灵活运用
  • 6
    PTA 浙大版《C语言程序设计（第3版）》题目集 习题8-4 报数 (20分)
  • 7
    PTA 浙大版《C语言程序设计（第3版）》题目集 习题8-6 删除字符 (20分)
  • 8
    浙大版《C语言程序设计（第3版）》题目集 练习8-2 计算两数的和与差 (10分)
  • 9
    C语言中逻辑表达式的深入探讨
  • 10
    C语言中字符串的引用与数组元素操作
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【排序算法】数据结构排序详解
    52
  • 3
    【链式二叉树】数据结构链式二叉树的（万字详解）
    44
  • 4
    【堆】数据结构堆的实现（万字详解）
    57
  • 5
    【树和二叉树】数据结构二叉树和树的概念认识
    27
  • 6
    【双向链表】数据结构双向链表的实现
    22
  • 7
    数据结构——单链表的基本操作
    12
  • 8
    数据结构——排序算法之快速排序
    37
  • 9
    数据结构——二叉树的链式结构
    39
  • 10
    数据结构--单链表OJ题
    20

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考