• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搜讯息吧

堆栈有几种实现方式?_JAVA教程,堆栈,实现方式

JAVA ytg3114 3个月前 (06-27) 146次浏览 0个评论 扫描二维码

值得一读的Java书籍,你读过几本?_JAVA教程

java其实是个很容易入门但很难实际上手的语言,需要不断的学习,温故而知新。在这里,我给大家推荐几本有利于Java学习的书籍。

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

堆栈有几种实现方式?_JAVA教程,堆栈,实现方式

堆栈有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;  
}

  结果如下图:

堆栈有几种实现方式?_JAVA教程,堆栈,实现方式

二、动态数组堆栈

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

java怎么定义数组?_JAVA教程

java数组的定义方法:1、使用【String[] s=new String[6]】定义一个长度为6的字符串数组,并可以进行赋值;2、使用【int[] i=new int[6]】,定义一个长度为6的整型数组。

  create_stack函数首先检查堆栈是否已经创建,然后才分配所需数量的内存并检查分配是否成功。destroy_stack函数首先检查堆栈是否存在,已经释放内存之后把长度和指针变量重新设置为零。is_emptyis_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;  
}

  结果如下图:

堆栈有几种实现方式?_JAVA教程,堆栈,实现方式

三、链式堆栈

  由于只有堆栈顶部元素才可以被访问,因此适用单链表可以很好实现链式堆栈,而且无长度限制。把一个元素压入堆栈是通过在链表头部添加一个元素实现。弹出一个元素是通过删除链表头部第一个元素实现。由于没有长度限制,故不需要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;  
}

  结果如下图:

堆栈有几种实现方式?_JAVA教程,堆栈,实现方式

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

以上就是堆栈有几种实现方式?的详细内容,更多请关注ki4网其它相关文章!

详解java中二叉树的深度优先遍历_JAVA教程

在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。


搜讯息 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:堆栈有几种实现方式?_JAVA教程,堆栈,实现方式
喜欢 (0)
[1353713598@qq.com]
分享 (0)
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址