服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言超详细讲解栈的实现及代码

C语言超详细讲解栈的实现及代码

2022-11-04 13:43三分苦 C/C++

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

前言

栈的概念

  • 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。有点类似于手枪弹夹，后压进去的子弹总是最先打出，除非枪坏了。
  • 压栈：栈的插入操作叫做进栈/压栈/入栈。（入数据在栈顶）
  • 出栈：栈的删除操作叫做出栈。（出数据也在栈顶）

注意：

1、函数调用也有栈，这两个栈有区别吗？

当然有区别。函数调用会调用栈帧，内存里头也有一个栈，程序运行起来时要执行函数，函数里头的局部变量、参数、返回值等等都要存在函数栈帧里头。

C语言超详细讲解栈的实现及代码

这两个栈没有任何关联，一个是数据结构中的栈。另一个是操作系统中内存划分的一个区域，叫做栈，用来函数调用时，建立栈帧。虽然本质上没有任何关联，但都符合后进先出的规则。

2、假设入栈顺序为：1 2 3 4，那么出栈顺序一定为：4 3 2 1 吗？

当然不是。虽说规则上明确后进先出，可这是相对而言的，如果说它每进一个再出一个，然后再继续压栈，那不同样符合后进先出的规则吗。就如同上例，你说它出栈顺序为1 2 3 4 都不足为奇，每进一个出一个再进，同样符合规则。类似的入栈两个再出再进再出也是可以的，好比如2 1 4 3。

栈的结构

C语言超详细讲解栈的实现及代码

栈的实现

创建栈结构

Stack.h 文件：

?
1
2
3
4
5
6
7
8
//创建栈结构
typedef int STDataType;
typedef struct Stack
{
    STDataType* a; //存储数据
    int top; //栈顶的位置
    int capacity; //容量
}ST;

初始化栈

思想：

初始化还是相对比较简单的，学了之前的顺序表，初始化栈就很轻松了

Stack.h 文件：

?
1
2
//初始化栈
void StackInit(ST* ps);

Stack.c 文件：

?
1
2
3
4
5
6
7
8
//初始化栈
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

注意：

​​​这里初始化的时候将top置为0是有意图的。首先，由上文创建栈结构时已经标注了，top是用来记录栈顶的位置，既然是栈顶的位置，那当top初始化为0时，我们可以直接将数据放入栈中，随后top++，但是当top初始化为-1时，top首先要++才能放入数据，因为数据不可能在负数不属于栈的位置上放入。下图演示过程：

C语言超详细讲解栈的实现及代码

 本文以 top = 0 示例

销毁栈

思想：

动态开辟的内存空间一定要释放，free置空即可，并把其余数据置0。

Stack.h 文件：

?
1
2
//销毁栈
void StackDestory(ST* ps);

Stack.c 文件：

?
1
2
3
4
5
6
7
8
//销毁栈
void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

入栈

思路：

前文已经强调了top初始化为0，那么理应直接压入数据，并把top++，不过在这之前，得判断空间是否够，当top=capacity的时候，栈就满了，那么就需要realloc扩容。

Stack.h 文件：

?
1
2
//压栈
void StackPush(ST* ps, STDataType x);

Stack.c 文件：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//压栈
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    //如果栈满了，考虑扩容
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
        ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (ps->a == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->capacity = newcapacity; //更新容量
    }
    ps->a[ps->top] = x;//将数据压进去
    ps->top++;//栈顶上移
}

出栈

思路：

在你出栈之前，要确保top不为空，而top不为空的条件就是top>0，所以还要断言top>0，随后，直接将栈顶位置下移--即可。跟顺序表的思想大同小异。

Stack.h 文件：

?
1
2
//出栈
void StackPop(ST* ps);

Stack.c 文件：

?
1
2
3
4
5
6
7
//出栈
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

获取栈顶元素

思路：

首先要搞清楚谁才是栈顶元素，是top位置还是top-1位置？很显然是top-1的位置才是栈顶元素，因为在前文初始化的时候已经明确指出top为0，当时压栈时直接放入数据的，此时第一个数据下标为0，随后++top再压入其它数据，由此可见，栈顶元素即下标top-1的位置。

Stack.h 文件：

?
1
2
//访问栈顶数据
STDataType StackTop(ST* ps);

Stack.c 文件：

?
1
2
3
4
5
6
7
//访问栈顶数据
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}

获取栈中有效元素个数

思想：

上文讲到下标top-1才是栈顶元素，那么是不是说总共就是top-1个元素呢？当然不是，这里跟数组下标一样的思想，元素个数应该就是top个，直接返回即可。

Stack.h 文件：

?
1
2
//有效元素个数
int StackSize(ST* ps);

Stack.c 文件：

?
1
2
3
4
5
6
//有效元素个数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

检测栈是否为空

思路：

当top的值为0时即为空，return直接返回即可

Stack.h 文件：

?
1
2
//判空
bool StackEmpty(ST* ps);

Stack.c 文件：

?
1
2
3
4
5
6
//判空
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0; //如果top为0，那么就为真，即返回
}

Test.c 文件：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void TestStack()
{
    ST st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    while (!StackEmpty(&st))
    {
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    printf("\n");
    StackDestory(&st);
}

效果如下：

C语言超详细讲解栈的实现及代码

总代码

Stack.h 文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
//创建栈结构
typedef int STDataType;
typedef struct Stack
{
    STDataType* a; //存储数据
    int top; //栈顶的位置
    int capacity; //容量
}ST;
 
//初始化栈
void StackInit(ST* ps);
 
//销毁栈
void StackDestory(ST* ps);
 
//压栈
void StackPush(ST* ps, STDataType x);
 
//出栈
void StackPop(ST* ps);
 
//判空
bool StackEmpty(ST* ps);
 
//访问栈顶数据
STDataType StackTop(ST* ps);
 
//有效元素个数
int StackSize(ST* ps);

Stack.c 文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}
 
//销毁栈
void StackDestory(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)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
        ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (ps->a == NULL)
        {
            printf("realloc 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);
    return ps->top == 0; //如果top为0，那么就为真，即返回
}
 
//访问栈顶数据
STDataType StackTop(ST* ps)
{
    assert(ps);
    return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
 
//有效元素个数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

Test.c 文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
    ST st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    while (!StackEmpty(&st))
    {
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    printf("\n");
    StackDestory(&st);
}
int main()
{
    TestStack();
    return 0;
}

到此这篇关于C语言超详细讲解栈的实现及代码的文章就介绍到这了,更多相关C语言 栈的实现内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/bit_zyx/article/details/123763458

  • C语言
  • 栈

    • 延伸 · 阅读

    精彩推荐
    • C/C++C++验证LeetCode包围区域的DFS方法

      C++验证LeetCode包围区域的DFS方法

      这篇文章主要介绍了C++验证LeetCode包围区域的DFS方法,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

      Grandyang9902021-12-06
    • C/C++C++实现教师管理系统

      C++实现教师管理系统

      这篇文章主要为大家详细介绍了C++实现教师管理系统，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      菜鸟来喽！5962022-10-24
    • C/C++C程序实现整数的素数和分解问题

      C程序实现整数的素数和分解问题

      这篇文章主要介绍了C程序实现整数的素数和分解问题,对于算法的学习有不错的借鉴价值,需要的朋友可以参考下...

      C语言程序设计11272021-02-03
    • C/C++浅谈c++ hook 钩子的使用介绍

      浅谈c++ hook 钩子的使用介绍

      本篇文章主要介绍了浅谈c++ hook 钩子的使用介绍，详细的介绍了c++ hook 钩子的原理和运行机制，有兴趣的可以了解一下...

      DoubleLi10952021-06-09
    • C/C++C语言简单编程速成

      C语言简单编程速成

      我们将所有的 C 语言要素放置到一份易读的备忘录上。C 语言是一种相当简约和直接的语言。除了编程的基础知识之外，并没有很高级的概念，这很大程度...

      Linux中国4312020-10-19
    • C/C++C++从一个文件夹中读出所有txt文件的方法示例

      C++从一个文件夹中读出所有txt文件的方法示例

      这篇文章主要给大家介绍了关于C++从一个文件夹中读出所有txt文件的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考...

      Hahallo6952021-06-22
    • C/C++C++控制台循环链表实现贪吃蛇

      C++控制台循环链表实现贪吃蛇

      这篇文章主要为大家详细介绍了C++控制台循环链表实现贪吃蛇，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      PPPeyton11802021-09-03
    • C/C++C语言中可变参数的使用方法示例

      C语言中可变参数的使用方法示例

      这篇文章主要给大家介绍了关于C语言中可变参数的使用方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的...

      Edver6902021-10-19
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 常量类型 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 C语言程序设计 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图