详解堆栈的几种实现方法 基本的抽象数据类型(ADT)是编写C程序必要的过程,这类ADT有链表、堆栈、队列和树等,本文主要讲解下堆栈的几种实现方法以及他们的优缺点。 堆栈(stack)的显著特点是后进先出(Last-In First-Out, LIFO),其实现的方法有三种可选方案:静态数组、动态分配的数组、动态分配的链式结构。 静态数组:特点是要求结构的长度固定,而且长度在编译时候就得确定。其优点是结构简单,实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制,适用于知道明确长度的场合。 动态数组:特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活,缺点是由此会增加程序的复杂性。 链式结构:特点是无长度上线,需要的时候再申请分配内存空间,可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存,在链式结构中访问一个特定元素的效率不如数组。 首先先确定一个堆栈接口的头文件,里面包含了各个方案下的函数原型,放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。 堆栈接口stack.h文件代码: [cpp] view plain copy 1 /* ** 堆栈模块的接口 stack.h #include
#define STACK_TYPE int /* 堆栈所存储的值的数据类型 */ /* ** 函数原型:create_stack
** 创建堆栈,参数指定堆栈可以保存多少个元素。 ** 注意:此函数只适用于动态分配数组形式的堆栈。 */ void create_stack(size_t size);
/*** 函数原型:destroy_stack
** 销毁一个堆栈,释放堆栈所适用的内存。
** 注意:此函数只适用于动态分配数组和链式结构的堆栈。 */ void destroy_stack(void); /* ** 函数原型:push
** 将一个新值压入堆栈中,参数是被压入的值。 */ void push(STACK_TYPE value); /* ** 函数原型:pop
** 弹出堆栈中栈顶的一个值,并丢弃。 */ void pop(void); /* ** 函数原型:top
** 返回堆栈顶部元素的值,但不改变堆栈结构。 */ STACK_TYPE top(void); /* ** 函数原型:is_empty
** 如果堆栈为空,返回TRUE,否则返回FALSE。 */ int is_empty(void); /* ** 函数原型:is_full
** 如果堆栈为满,返回TRUE,否则返回FALSE。 */ int is_full(void);
一、静态数组堆栈
在静态数组堆栈中,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\ #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) {
1. 2.
assert(!is_empty()); /* 弹出堆栈之前先判断是否堆栈已空 */
3. 4.
top_element -= 1;
5. 6.
}
7. 8.
9. 10.
/* top */
11. 12.
STACK_TYPE top(void)
13. 14.
{
15. 16.
assert(!is_empty());
17. 18.
return stack[top_element];
19. 20.
}
21. 22.
23.
24.
/* is_empty */
25. 26.
int is_empty(void)
27. 28.
{
29. 30.
return top_element == -1;
31. 32.
}
33. 34.
35. 36.
/* is_full */
37. 38.
int is_full(void)
39. 40.
{
41. 42.
return top_element == STACK_SIZE - 1;
详解堆栈的几种实现方法
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)