AI 助理
备案控制台
开发者社区 云计算 文章 正文

＜栈（动态版）＞《数据结构(C语言版)》

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

目录

《数据结构(C语言版)》实战项目之栈（动态版）的功能实现

                                                                            ——By 作者：新晓·故知

一、完整源码：

               完整源码如下，欢迎复制测试指正！

      栈（动态版）的功能实现（<入栈，出栈>&<顺序，乱序>）测试示例：

      完整源码：

        二、栈的功能实现分析：

1.栈的概念及结构：

2.栈的实现方式：

3.栈的实现步骤：

（1）动态结构定义：

（2）栈的初始化：

（3）压栈（入栈）：

（4）出栈：

（5）判断栈是否为空：

（6）栈顶查找：

（7）查看栈的数据：

（8）栈的销毁：

栈的辨析：

栈顶top的位置：

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                              ——By 作者：新晓·故知

《数据结构(C语言版)》实战项目之栈（动态版）的功能实现

                                                                            ——By 作者：新晓·故知

一、完整源码：

完整源码如下，欢迎复制测试指正！

栈（动态版）的功能实现（<入栈，出栈>&<顺序，乱序>）测试示例：

image.gif编辑

完整源码：

Test.c:

#include "Stack.h"
//栈的测试
//按照顺序压栈、出栈
void TestStack1()
{
  ST st;
  StackInit(&st);
  ////1.一个一个创建数据，可连续也可不连续
  //StackPush(&st, 1);
  //StackPush(&st, 2);
  //StackPush(&st, 3);
  //StackPush(&st, 4);
  //StackPush(&st, 5);
  //2.使用循环压栈创建数据
  for (int i = 0; i < 6; ++i)
  {
    StackPush(&st, i);
  }
  while (!StackEmpty(&st))
  {
    printf("%d ", StackTop(&st));
    StackPop(&st);
  }
  printf("\n");
  StackDestroy(&st);
}
//乱序压栈、出栈
void TestStack2()
{
  ST st;
  StackInit(&st);
  //1.一个一个创建数据，可连续也可不连续
  StackPush(&st, 1);
  StackPush(&st, 2);
  StackPush(&st, 3);
  //1、2、3压栈，3出栈，再进行4、5压栈，再打印整体出栈
  printf("%d ", StackTop(&st));
  StackPop(&st);
  StackPush(&st, 4);
  StackPush(&st, 5);
  while (!StackEmpty(&st))
  {
    printf("%d ", StackTop(&st));
    StackPop(&st);
  }
  printf("\n");
  StackDestroy(&st);
}
int main()
{
  TestStack1();
  TestStack2();
  return 0;
}
image.gif

Stack.c:

#include "Stack.h"
//栈的接口功能函数
//初始化
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 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);
  //需要注意top的位置，取决于如何对top的初始化
  //本程序top的初始化位置为0
  //判断是否栈满，栈满即需要扩容
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    //此处的4是随机合理给定，无特别规定，*2是合理利用空间
    ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    //relloc给的是总的新空间的大小
    if (ps->a == NULL)
    {
      printf("relloc fail\n");
      exit(-1);
    }
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
//出栈
void StackPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  --ps->top;
}
//判断栈是否为空
bool StackEmpty(ST* ps)
{
  assert(ps);
  ////写法1
  //if (ps->top > 0)
  //{
  //  return false;
  //}
  //else
  //{
  //  return true;
  //}
  //写法2
  return ps->top == 0;
}
//栈顶
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(ps->top>0);
  return ps->a[ps->top - 1];
}
//查看栈的数据
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
image.gif

Stack.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//静态(不常用）
//struct Stack
//{
//  int a[N];
//  int top; //栈顶的位置
//};
//动态
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top; //栈顶的位置
  int capacity; //容量
}ST;
//接口功能函数
//初始化
void StackInit(ST* ps);
//销毁
void StackDestroy(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
//栈顶
STDataType StackTop(ST* ps);
//查看栈的数据
int StackSize(ST* ps);
image.gif

二、栈的功能实现分析：

1.栈的概念及结构：

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

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

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

image.gif编辑

image.gif编辑

2.栈的实现方式：

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

image.gif编辑

image.gif编辑

3.栈的实现步骤：

（1）动态结构定义：

//动态
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top; //栈顶的位置
  int capacity; //容量
}ST;
image.gif

（2）栈的初始化：

//栈的接口功能函数
//初始化
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
image.gif

（3）压栈（入栈）：

//压栈
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  //需要注意top的位置，取决于如何对top的初始化
  //本程序top的初始化位置为0
  //判断是否栈满，栈满即需要扩容
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    //此处的4是随机合理给定，无特别规定，*2是合理利用空间
    ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    //relloc给的是总的新空间的大小
    if (ps->a == NULL)
    {
      printf("relloc fail\n");
      exit(-1);
    }
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
image.gif

（4）出栈：

//出栈
void StackPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  --ps->top;
}
image.gif

（5）判断栈是否为空：

//判断栈是否为空
bool StackEmpty(ST* ps)
{
  assert(ps);
  ////写法1
  //if (ps->top > 0)
  //{
  //  return false;
  //}
  //else
  //{
  //  return true;
  //}
  //写法2
  return ps->top == 0;
}
image.gif

（6）栈顶查找：

//栈顶
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(ps->top>0);
  return ps->a[ps->top - 1];
}
image.gif

（7）查看栈的数据：

//查看栈的数据
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
image.gif

（8）栈的销毁：

//销毁
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
image.gif

栈的辨析：

image.gif编辑

栈顶top的位置：

image.gif编辑

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                    ——By 作者：新晓·故知

关键词：
栈数据结构
数据结构c语言
栈C语言
数据结构栈
C语言数据结构
新晓故知
目录
相关文章
ephemerals__
|
5天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
64 9
ephemerals__
|
4天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
43 16
ephemerals__
|
4天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
32 8
html的七十二变
|
2天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
12 2
dufadayang
|
4天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
26 4
ephemerals__
|
7天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
24 0
白子寰
|
26天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
31 3
华章计算机
|
机器学习/深度学习 算法
《数据结构与算法 C语言版》—— 3.2栈的应用举例
华章计算机
1899 0
ephemerals__
|
17天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
31 10
c的前世今生
|
10天前
|
存储 算法 程序员
C语言：库函数
C语言的库函数是预定义的函数，用于执行常见的编程任务，如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作，提高开发效率。C标准库提供了丰富的函数，满足各种需求。
c的前世今生
17 1