搜索
首页Javajava教程堆栈有几种实现方式？

堆栈有几种实现方式？

coldplay.xixi
coldplay.xixi
Jun 28, 2020 am 11:42 AM
堆栈实现方式

堆栈有3种实现方式，实现方式为：1、静态数组堆栈，要求结构的长度固定，而且长度在编译时候就得确定；2、动态数组堆栈，长度可以在运行时候才确定以及可以更改原来数组的长度；3、链式结构堆栈，无长度上线，需要的时候再申请分配内存空间。

堆栈有几种实现方式？

堆栈有3种实现方式，实现方式为：

一、静态数组堆栈

　　在静态数组堆栈中，STACK_SIZE表示堆栈所能存储的元素的最大值，用top_element作为数组下标来表示堆栈里面的元素，当top_element == -1的时候表示堆栈为空；当top_element == STACK_SIZE - 1的时候表示堆栈为满。push的时候top_element加1，top_element == 0时表示第一个堆栈元素；pop的时候top_element减1。

a_stack.c 源代码如下：

[cpp] view plain copy
/* 
**  
** 静态数组实现堆栈程序 a_stack.c ，数组长度由#define确定 
*/  
  
#include"stack.h"  
#include<assert.h>  
#include<stdio.h>  
  
#define STACK_SIZE 100 /* 堆栈最大容纳元素数量 */  
  
/* 
** 存储堆栈中的数组和一个指向堆栈顶部元素的指针 
*/  
static STACK_TYPE stack[STACK_SIZE];  
static int top_element = -1;  
  
/* push */  
void push(STACK_TYPE value)  
{  
    assert(!is_full()); /* 压入堆栈之前先判断是否堆栈已满*/  
    top_element += 1;  
    stack[top_element] = value;  
}  
  
/* pop */  
void pop(void)  
{  
    assert(!is_empty()); /* 弹出堆栈之前先判断是否堆栈已空 */  
    top_element -= 1;  
}  
  
/* top */  
STACK_TYPE top(void)  
{  
    assert(!is_empty());  
    return stack[top_element];  
}  
  
/* is_empty */  
int is_empty(void)  
{  
    return top_element == -1;  
}  
  
/* is_full */  
int is_full(void)  
{  
    return top_element == STACK_SIZE - 1;  
}  
  
/* 
** 定义一个print函数，用来打印堆栈里面的元素。 
*/  
void print(void)  
{  
    int i;  
    i = top_element;  
    printf("打印出静态数组堆栈里面的值: ");  
    if(i == -1)  
        printf("这是个空堆栈\n");  
    while(i!= -1)  
        printf("%d ",stack[i--]);  
    printf("\n");  
}  
int main(void)  
{  
    print();  
    push(10); push(9); push(7); push(6); push(5);  
    push(4);  push(3); push(2); push(1); push(0);  
    printf("push压入数值后：\n");  
    print();  
    printf("\n");  
    pop();  
    pop();  
    printf("经过pop弹出几个元素后的堆栈元素:\n");  
    print();  
    printf("\n");  
    printf("top()调用出来的值: %d\n",top());  
    return 1;  
}

　　结果如下图：

1d97fadfe6cd0be871a9d543d9f6417.png

二、动态数组堆栈

　　头文件还是用stack.h，改动的并不是很多，增加了stack_size变量取代STACK_SIZE来保存堆栈的长度，数组由一个指针来代替，在全局变量下缺省为0。

　　create_stack函数首先检查堆栈是否已经创建，然后才分配所需数量的内存并检查分配是否成功。destroy_stack函数首先检查堆栈是否存在，已经释放内存之后把长度和指针变量重新设置为零。is_empty 和 is_full 函数中添加了一条断言，防止任何堆栈函数在堆栈被创建之前就被调用。

d_stack.c源代码如下：

[cpp] view plain copy
/* 
** 动态分配数组实现的堆栈程序 d_stack.c 
** 堆栈的长度在创建堆栈的函数被调用时候给出，该函数必须在任何其他操作堆栈的函数被调用之前条用。 
*/  
#include"stack.h"  
#include<stdio.h>  
#include<malloc.h>  
#include<assert.h>  
  
/* 
** 用于存储堆栈元素的数组和指向堆栈顶部元素的指针 
*/  
static STACK_TYPE *stack;  
static int        stack_size;  
static int        top_element = -1;  
  
/* create_stack */  
void create_stack(size_t size)  
{  
    assert(stack_size == 0);  
    stack_size = size;  
    stack = (STACK_TYPE *)malloc(stack_size * sizeof(STACK_TYPE));  
    if(stack == NULL)  
        perror("malloc分配失败");  
}  
  
/* destroy */  
void destroy_stack(void)  
{  
    assert(stack_size > 0);  
    stack_size = 0;  
    free(stack);  
    stack = NULL;  
}  
  
/* push */  
void push(STACK_TYPE value)  
{  
    assert(!is_full());  
    top_element += 1;  
    stack[top_element] = value;  
}  
  
/* pop */  
void pop(void)  
{  
    assert(!is_empty());  
    top_element -= 1;  
}  
  
/* top */  
STACK_TYPE top(void)  
{  
    assert(!is_empty());  
    return stack[top_element];  
}  
  
/* is_empty */  
int is_empty(void)  
{  
    assert(stack_size > 0);  
    return top_element == -1;  
}  
  
/* is_full */  
int is_full(void)  
{  
    assert(stack_size > 0);  
    return top_element == stack_size - 1;  
}  
  
  
/* 
** 定义一个print函数，用来打印堆栈里面的元素。 
*/  
void print(void)  
{  
    int i;  
    i = top_element;  
    printf("打印出动态数组堆栈里面的值: ");  
    if(i == -1)  
        printf("这是个空堆栈\n");  
    while(i!= -1)  
        printf("%d ",stack[i--]);  
    printf("\n");  
}  
int main(void)  
{  
    create_stack(50);  
    print();  
    push(10); push(9); push(7); push(6); push(5);  
    push(4);  push(3); push(2); push(1); push(0);  
    printf("push压入数值后：\n");  
    print();  
    printf("\n");  
    pop();  
    pop();  
    printf("经过pop弹出几个元素后的堆栈元素:\n");  
    print();  
    printf("\n");  
    printf("top()调用出来的值: %d\n",top());  
    destroy_stack();  
    return 1;  
}

　　结果如下图：

f5556d236cc70345161cc8683f796bb.png

三、链式堆栈

　　由于只有堆栈顶部元素才可以被访问，因此适用单链表可以很好实现链式堆栈，而且无长度限制。把一个元素压入堆栈是通过在链表头部添加一个元素实现。弹出一个元素是通过删除链表头部第一个元素实现。由于没有长度限制，故不需要create_stack函数，需要destroy_stack进行释放内存以避免内存泄漏。

头文件stack.h不变，l_stack.c源代码如下：

[cpp] view plain copy
/* 
** 单链表实现堆栈，没有长度限制 
*/  
#include"stack.h"  
#include<stdio.h>  
#include<malloc.h>  
#include<assert.h>  
  
#define FALSE 0  
  
/* 
** 定义一个结构以存储堆栈元素。 
*/  
typedef struct STACK_NODE  
{  
    STACK_TYPE value;  
    struct STACK_NODE *next;  
} StackNode;  
  
/* 指向堆栈中第一个节点的指针 */  
static StackNode *stack;  
  
/* create_stack */  
void create_stack(size_t size)  
{}  
  
/* destroy_stack */  
void destroy_stack(void)  
{  
    while(!is_empty())  
        pop();  /* 逐个弹出元素，逐个释放节点内存 */  
}  
  
/* push */  
void push(STACK_TYPE value)  
{  
    StackNode *new_node;  
    new_node = (StackNode *)malloc(sizeof(StackNode));  
    if(new_node == NULL)  
        perror("malloc fail");  
    new_node->value = value;  
    new_node->next = stack;  /* 新元素插入链表头部 */  
    stack = new_node;       /* stack 重新指向链表头部 */  
}  
  
/* pop */  
void pop(void)  
{  
    StackNode *first_node;  
      
    assert(!is_empty());  
    first_node = stack;  
    stack = first_node->next;  
    free(first_node);  
}  
  
/* top */  
STACK_TYPE top(void)  
{  
    assert(!is_empty());  
    return stack->value;  
}  
  
/* is_empty */  
int is_empty(void)  
{  
    return stack == NULL;  
}  
  
/* is_full */  
int is_full(void)  
{  
    return FALSE;  
}  
  
  
/* 
** 定义一个print函数，用来打印堆栈里面的元素。 
*/  
void print(void)  
{  
    StackNode *p_node;  
    p_node = stack;  
    printf("打印出链式堆栈里面的值: ");  
    if(p_node == NULL)  
        printf("堆栈为空\n");  
    while(p_node != NULL)  
    {  
        printf("%d ", p_node->value);  
        p_node = p_node->next;  
    }  
    printf("\n");  
}  
int main(void)  
{  
    print();  
    push(10); push(9); push(7); push(6); push(5);  
    push(4);  push(3); push(2); push(1); push(0);  
    printf("push压入数值后：\n");  
    print();  
    printf("\n");  
    pop();  
    pop();  
    printf("经过pop弹出几个元素后的堆栈元素:\n");  
    print();  
    printf("\n");  
    printf("top()调用出来的值: %d\n",top());  
    destroy_stack();  
    return 1;  
}

　　结果如下图：

2e89d704282581a14fe8c367bdffcb7.png

推荐教程：《java视频教程》

以上是堆栈有几种实现方式？的详细内容。更多信息请关注PHP中文网其他相关文章！

声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
相关文章
如何将Maven或Gradle用于高级Java项目管理，构建自动化和依赖性解决方案？如何将Maven或Gradle用于高级Java项目管理，构建自动化和依赖性解决方案？Mar 17, 2025 pm 05:46 PM

本文讨论了使用Maven和Gradle进行Java项目管理，构建自动化和依赖性解决方案，以比较其方法和优化策略。

如何使用适当的版本控制和依赖项管理创建和使用自定义Java库（JAR文件）？如何使用适当的版本控制和依赖项管理创建和使用自定义Java库（JAR文件）？Mar 17, 2025 pm 05:45 PM

本文使用Maven和Gradle之类的工具讨论了具有适当的版本控制和依赖关系管理的自定义Java库（JAR文件）的创建和使用。

如何使用咖啡因或Guava Cache等库在Java应用程序中实现多层缓存？如何使用咖啡因或Guava Cache等库在Java应用程序中实现多层缓存？Mar 17, 2025 pm 05:44 PM

本文讨论了使用咖啡因和Guava缓存在Java中实施多层缓存以提高应用程序性能。它涵盖设置，集成和绩效优势，以及配置和驱逐政策管理最佳PRA

如何将JPA（Java持久性API）用于具有高级功能（例如缓存和懒惰加载）的对象相关映射？如何将JPA（Java持久性API）用于具有高级功能（例如缓存和懒惰加载）的对象相关映射？Mar 17, 2025 pm 05:43 PM

本文讨论了使用JPA进行对象相关映射，并具有高级功能，例如缓存和懒惰加载。它涵盖了设置，实体映射和优化性能的最佳实践，同时突出潜在的陷阱。[159个字符]

Java的类负载机制如何起作用，包括不同的类载荷及其委托模型？Java的类负载机制如何起作用，包括不同的类载荷及其委托模型？Mar 17, 2025 pm 05:35 PM

Java的类上载涉及使用带有引导，扩展程序和应用程序类负载器的分层系统加载，链接和初始化类。父代授权模型确保首先加载核心类别，从而影响自定义类LOA

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

显示更多

热门文章

R.E.P.O.能量晶体解释及其做什么（黄色晶体）
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
2 周前ByDDD
R.E.P.O.如果您听不到任何人，如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25：如何解锁Myrise中的所有内容
1 个月前By尊渡假赌尊渡假赌尊渡假赌
显示更多

热工具

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境，用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问，并防止学生使用未经授权的资源。

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

mPDF

mPDF

mPDF是一个PHP库，可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件，并处理不同的语言。与原始脚本如HTML2FPDF相比，它的速度较慢，并且在使用Unicode字体时生成的文件较大，但支持CSS样式等，并进行了大量增强。支持几乎所有语言，包括RTL（阿拉伯语和希伯来语）和CJK（中日韩）。支持嵌套的块级元素（如P、DIV），

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序，非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具，帮助Web开发人员更好地理解保护Web应用程序的过程，并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞，难度各不相同。请注意，该软件中

显示更多

热门话题

gmail邮箱登陆入口在哪里
7496
15
CakePHP 教程
1377
52
steam的账户名称是什么格式
77
11
win11激活密钥永久
52
19
NYT连接提示和答案
19
52
显示更多