堆栈有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#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; }
结果如下图：
二、动态数组堆栈
头文件还是用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; }
结果如下图：
三、链式堆栈
由于只有堆栈顶部元素才可以被访问，因此适用单链表可以很好实现链式堆栈，而且无长度限制。把一个元素压入堆栈是通过在链表头部添加一个元素实现。弹出一个元素是通过删除链表头部第一个元素实现。由于没有长度限制，故不需要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视频教程》
