这篇文章将为大家详细讲解有关java实现堆栈的方法,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。
在计算机领域,堆栈是一个不容忽视的概念,堆栈是一种数据结构。堆栈都是一种数据项按序排列的数据结构,只能在一端(称为栈顶(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<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; }
结果如下图:
二、静态数组堆栈
在静态数组堆栈中,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; }
结果如下图:
三、链式堆栈
由于只有堆栈顶部元素才可以被访问,因此适用单链表可以很好实现链式堆栈,而且无长度限制。把一个元素压入堆栈是通过在链表头部添加一个元素实现。弹出一个元素是通过删除链表头部第一个元素实现。由于没有长度限制,故不需要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实现堆栈的方法就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。