java实现堆栈的方法

这篇文章将为大家详细讲解有关java实现堆栈的方法，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

目前创新互联已为上1000+的企业提供了网站建设、域名、雅安服务器托管、网站托管运营、企业网站设计、元谋网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

在计算机领域，堆栈是一个不容忽视的概念，堆栈是一种数据结构。堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。

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

一、动态数组堆栈

头文件还是用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  
#include  
#include  
  
/* 
** 用于存储堆栈元素的数组和指向堆栈顶部元素的指针 
*/  
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;  
}

结果如下图：

java实现堆栈的方法

二、静态数组堆栈

在静态数组堆栈中，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  
#include  
  
#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;  
}

结果如下图：

java实现堆栈的方法

三、链式堆栈

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

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

[cpp] view plain copy
/* 
** 单链表实现堆栈，没有长度限制 
*/  
#include"stack.h"  
#include  
#include  
#include  
  
#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;  
}

结果如下图：

java实现堆栈的方法

关于java实现堆栈的方法就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。

当前标题：java实现堆栈的方法
分享地址：http://chengdu.cdxwcx.cn/article/gdjeji.html

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

首页

网站建设

网站制作案例

解决方案

网站设计报价

网站制作动态

关于我们

联系我们

成都网站建设设计将想法与焦点和您一起共享

java实现堆栈的方法

其他资讯

zblog怎么换数据 zblog数据库地址修改

e4a接收php数据 php中post接收传过来数据

vb点虐培训机构 vba培训视频

阿里云服务器监控解析阿里云服务器监控工具

java代码特殊字符校验 java特殊字符正则表达式

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

成都网站建设设计 将想法与焦点和您一起共享

java实现堆栈的方法

其他资讯

zblog怎么换数据 zblog数据库地址修改

e4a接收php数据 php中post接收传过来数据

vb点虐 培训机构 vba培训视频

阿里云服务器监控解析 阿里云服务器监控工具

java代码特殊字符校验 java特殊字符正则表达式

成都网站建设设计将想法与焦点和您一起共享

vb点虐培训机构 vba培训视频

阿里云服务器监控解析阿里云服务器监控工具