数据结构与算法 -- 栈 ADT

这两天翻了下数据结构与算法分析、严蔚敏的数据结构、C和指针、C Primer Plus这些本书，受益很多。不过大多的示例不够完整，需要自己动手编写程序。又看了遍培训时的笔记，虽然很糙但是精华的部分还是可以借鉴的。还有看到了不错的博文，参看：数据结构与算法分析 学习笔记 对于数据结构与算法，尽量做到多方面的参考。多的不说了，下面就开始总结！！

一、首先讲一些基本的概念

1、数据结构的基本概念

在计算机学科中数据结构表示数据在计算机中的存储和组织形式。主要描述数据元素之间和位置关系等。一般来说，选择适当的数据结构可以提高计算机程序的运行效率（时间复杂度）和存储效率（空间复杂度）。

2、数据结构的三种层次

（1）逻辑结构--抽象层

主要描述的是数据元素之间的逻辑关系

（2）物理结构--结构层

主要描述的是数据元素之间的位置关系

（3）运算结构--实现层

主要描述的是如何实现数据结构

3、逻辑结构的分类 (抽象数据类型 ADT)

（1）集合结构（集）

主要描述所有的元素都属于一个总体，除了同属于一个集合外没有其他关系。集合结构不强调元素之间的任何关联性。

（2）线性结构（表）

主要描述元素之间具有一对一的前后关系。结构中必须存在唯一的首元素和唯一的尾元素。除了首元素之外结构中的每一个元素有且仅有一个前趋元素，除了尾元素之外结构中的每一个元素有且仅有一个后继元素。

（3）树形结构（树）

主要描述元素之间存在一对一个关系。树形结构中必须存在唯一跟关系，顶端的元素叫做叶元素。除了根元素之外，结构中每一个元素有且仅有一个前趋元素，除了叶元素之外，结构中每一个元素拥有一个到多个后继元素。如：树，家谱。

（4）网状结构（图）
主要描述数据元素之间存在多对多的交叉映射关系，也叫做图形结构。结构中的每个元素都可以拥有多个任意数量，前驱和后继元素，结构中的任意两个元素都可以建立关联。如：蜘蛛网 网球拍。

4、物理结构的分类

（1）顺序结构

顺序结构就是使用一组连续的存储单元依次存储逻辑上相邻的各个元素，顺序结构可以借助计算机程序设计语言（如C/C++）提供的数组类型加以描述。

优点：

只需要申请存放数据本身的内存空间即可，不需要额外的内存来表达数据元素之间的逻辑关系。

支持下标访问，也可以实现随机访问。

缺点：

连续的存储空间导致内存空间的利用率比较低。

向顺序存储结构中插入/删除元素时，可能需要移动大量元素，效率比较低。

（2）链式结构

表示在计算机中使用一组任意的存储单元来存储所有的元素（这组存储单元可以是连续的，也可以是不连续的）。不要求逻辑上相邻的元素在物理位置上也相邻。

链式存储结构不使用连续的存储空间存放结构的元素，而是为每一个元素构造一个节点。节点中除了存放数据本身以外，还需要存放指向下一个节点的指针。绝大多数程序设计语言（如C/C++）都没有提供用于描述链式结构的数据类型，需要编写额外的代码去实现。
优点：
不采用连续的存储空间导致内存空间利用率比较高，克服顺序存储结构中预知元素个数的缺点
插入或删除元素时，不需要移动大量的元素，比较当便。
缺点：
除了申请存放数据本身的内存空间外，还需要额外的空间来表达数据之间的逻辑关系
不支持下标访问和随机访问。

5、逻辑结构和物理结构的关系

每种逻辑结构采用何种物理结构来实现，并没有具体的规定。通过根据实现的难易程度，以及在时间复杂程度和空间复杂程度方面的要求，来选择合适的物理结构。

6、运算结构

（1）分配资源，建立结构，释放资源

如：int arr[5]； ->栈区，系统自动分配内存和回收内存。

（2）插入和删除

增加和减少元素

（3）获取和遍历

查看具体的元素值，以及遍历结构中所有的元素值

（4）修改和排序

修改元素的值，采用排序算法进行排序

二、栈 ADT

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶（top）。它是后进先出（LIFO）的。对栈的基本操作只有push（进栈）和pop（出栈）两种，前者相当于插入，后者相当于删除最后的元素。上篇文章讲递归的有讲到，程序在运行时，如果调用一个函数，则将该函数压栈（push），调用完一个函数则出栈（pop）。递归过程中，不断的压栈(因为该函数并没有执行完毕，因为还没有执行到函数的最后一个大括号 } )。因为内存是有限的，因此会造成栈溢出。 由于栈在本质上是一种受限制的表，所以可以使用任何一种表的形式来实现它，我们最常用的一般有两种： （1）顺序栈：数组 （2）链式栈：链表 它们在复杂度上的优缺点对比如下： 1、新增和删除元素时的时间复杂度 链表：在动态申请内存（new或者malloc）上的花销非常昂贵。 数组：几乎没有花销，以常数 O(1) 时间运行，在带有自增和自减寻址功能的寄存器上操作时，编译器会把整数的 push 和 pop 操作编译成一条机器指令。 2、空间复杂度 链表：由于空间是动态申请、释放的，因此不会浪费空间，而且只要物理存储器允许，理论上能够满足最大范围未知的情况。 数组：必须在初始化时执行栈的大小，有可能会浪费空间，也有可能不够空间用。 结论： （1）如果对运动时的效率要求非常高，并且能够在初始化时预知栈的大小，那么应该首选数组形式，否则应该选用链表形式。 （2）由于对栈的操作永远都是针对栈顶（top）进行的，因此数组的随机存取的优点就没有了，而且数组必须预先分配空间，空间大小也受到限制，所以一般情况下（对运行时效的要求不是太高）链表应该是首选。

三、顺序栈

其中又分为静态数组和动态数组两类。
静态数组：特点是要求结构的长度固定，而且长度在编译时候就得确定。其优点是结构简单，实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制，适用于知道明确长度的场合。
动态数组：特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活，缺点是由此会增加程序的复杂性。

1、静态数组

在静态数组堆栈中，栈的长度以一个 #define 定义的形式出现，在模块被编译之间用户必须对数组长度进行设置。变量top_element 保存栈顶元素的下标值。它的初始值为 -1，提示栈为空。push 函数在存储新元素前先增加这个变量的值，这样 top_elelment 始终包含栈顶元素的下标志。如果把它的初始值设为 0，top_element 将指向数组的下一个可用位置。这种方法当然也可以，但它的效率稍差一些，因为它需要执行一次减法运算才能访问栈顶元素。执行 pop 函数，top_element  在元素被复制出数组之后才减 1，这和 push 相反，后者是在被元素复制到数组之前先加 1。pop 函数不需要从数组中删除元素，只需减少栈顶指针的值就足矣，因为用户此时已不能再访问这个旧值了。 参看：C语言再学习-- assert 断言宏 使用断言，相对来说比较简单。但是也会有困扰就是入栈出栈时检测到栈为满或栈为空 程序会终止。但如果用户希望确保程序不会终止，那么程序压栈一个新值之前必须检测堆栈是否仍有空间。因此，断言必须只能够对那些用户自己也能进行检查的内容进行检查。后面会再写一个例子，讲到这种情况。travel (); pop (); 输出结果： 这个栈为空 栈为空 a.out: a_stack.c:73: pop: Assertion `!is_empty ()' failed. 已放弃 (核心已转储) 再有注意：所有不属于外部接口的内容都被声明为 static，这可以防止用户预定义接口之外的任何方式访问堆栈中的值。
代码实现说明： 很简单，一句话使用数组下标
#include <stdio.h> #include <assert.h> #include <stdlib.h> #define STACK_TYPE int /* 堆栈所存储的值的数据类型 */ #define STACK_SIZE 100 /* 堆栈最大容纳元素数量 */ /* 存储堆栈中的数组和一个指向堆栈顶部元素的指针 */ static STACK_TYPE stack[STACK_SIZE]; static int top_element = -1; /* 将一个新值压入堆栈中，参数是被压入的值。*/ void push (STACK_TYPE value); /* 弹出堆栈中栈顶的一个值，并丢弃。*/ void pop (void); /* 返回堆栈顶部元素的值，但不改变堆栈结构。*/ STACK_TYPE top (void); /* 如果堆栈为空，返回TRUE,否则返回FALSE。*/ int is_empty (void); /* 如果堆栈为满，返回TRUE,否则返回FALSE。*/ int is_full (void); /* 自定义函数实现遍历操作 */ void travel (void); /* 计算栈中元素的个数 */ int size (void); int main (void) { travel (); pop (); printf("%s\n", is_empty() ? "栈为空" : "栈未空"); int i = 0; for (i = 0; i <= 9; i++) { push (i); } puts ("push 压栈后的数值为: "); travel (); printf ("此时栈顶元素为：%d\n", top ()); printf ("此时栈元素个数为：%d\n", size ()); pop (); pop (); puts ("经过pop弹出几个元素后的栈元素： "); travel (); printf("%s\n", is_full() ? "栈为满" : "栈未满"); printf("%s\n", is_empty() ? "栈为空" : "栈未空"); printf ("此时栈顶元素为：%d\n", top ()); printf ("此时栈元素个数为：%d\n", size ()); return 0; } void push (STACK_TYPE value) { //assert (!is_full ()); /* 压入堆栈之前先判断是否堆栈已满*/ if (is_full ()){printf ("栈已满，入栈失败\n"); return ;}top_element += 1; stack[top_element] = value; } void pop (void) { //assert (!is_empty ()); /* 弹出堆栈之前先判断是否堆栈已空 */ if (is_empty ()) { printf ("栈已空，出栈失败\n"); return ; } top_element -= 1; } STACK_TYPE top (void) { //assert (!is_empty ()); if (is_empty ()) { printf ("栈已空，出栈失败\n"); return ; } return stack[top_element]; } int is_empty (void) { return top_element == -1; } int is_full (void) { return top_element == STACK_SIZE -1; } void travel (void) { int i = 0; if (top_element == -1) printf ("这个栈为空"); for (i = 0; i <= top_element; i++) printf ("%d ", stack[i]); printf ("\n"); } int size (void) { return top_element + 1; } 输出结果： 这个栈为空 栈已空，出栈失败 栈为空 push 压栈后的数值为: 0 1 2 3 4 5 6 7 8 9 此时栈顶元素为：9 此时栈元素个数为：10 经过pop弹出几个元素后的栈元素： 0 1 2 3 4 5 6 7 栈未满 栈未空 此时栈顶元素为：7 此时栈元素个数为：8

2、动态数组

和静态数组主要区别在于在接口中定义了两个新函数：创建堆栈、销毁堆栈。 参看：C语言再学习 -- 再论数组和指针  其实不是数组，而是指针以下标形式访问。 create_stack 函数首先检查堆栈是否已经创建。然后分配所需要数量的内存并检查分配是否成功。 destroy_stack 函数在释放内存之后把长度设置为 0、指针变量重新设置为 NULL，这样它们可以用于创建另一个堆栈。 在is_full he  is_empty 函数中都增加了一条断言。这条断言可以防止任何堆栈函数在堆栈被创建前就被调用。其余的堆栈函数并不需要这条断言，因为它们都调用了这两个函数之一。 警告：在内存有限的环境中，使用 assert 检查内存分配是否成功并不合适，因为它很可能导致程序终止。这未必是你希望的结果。
代码实现说明： 也很简单，一句话动态分配内存，使用数组下标 /* 堆栈的长度在创建堆栈的函数被调用时给出，该函数必须在任何其他操作堆栈的函数被调用之前调用 */ #include <stdio.h> #include <assert.h> #include <stdlib.h> #define STACK_TYPE int /* 堆栈所存储的值的数据类型 */ /* 用于存储堆栈元素的数组和指向堆栈顶部元素的指针 */ static STACK_TYPE *stack; static int stack_size; static int top_element = -1; /* 创建对栈，参数指定对栈可以保存多少个元素 注意：此函数只适用于动态分配数组形式的堆栈。 */ void create_stack (size_t size); /* 销毁一个堆栈，释放堆栈所适用的内存 注意，此函数只适用于动态分配数组和链表结构的堆栈。 */ void destroy_stack (void); /* 将一个新值压入堆栈中，参数是被压入的值。*/ void push (STACK_TYPE value); /* 弹出堆栈中栈顶的一个值，并丢弃。*/ void pop (void); /* 返回堆栈顶部元素的值，但不改变堆栈结构。*/ STACK_TYPE top (void); /* 如果堆栈为空，返回TRUE,否则返回FALSE。*/ int is_empty (void); /* 如果堆栈为满，返回TRUE,否则返回FALSE。*/ int is_full (void); /* 自定义函数实现遍历操作 */ void travel (void); /* 计算栈中元素的个数 */ int size (void); int main (void) { create_stack (50); travel (); pop (); printf("%s\n", is_empty() ? "栈为空" : "栈未空"); int i = 0; for (i = 0; i <= 9; i++) { push (i); } puts ("push 压栈后的数值为: "); travel (); printf ("此时栈顶元素为：%d\n", top ()); printf ("此时栈元素个数为：%d\n", size ()); pop (); pop (); puts ("经过pop弹出几个元素后的栈元素： "); travel (); printf("%s\n", is_full() ? "栈为满" : "栈未满"); printf("%s\n", is_empty() ? "栈为空" : "栈未空"); printf ("此时栈顶元素为：%d\n", top ()); printf ("此时栈元素个数为：%d\n", size ()); destroy_stack (); printf ("此时栈元素个数为：%d\n", size ()); return 0; } void create_stack (size_t size) { //assert (stack_size == 0); if (size < stack_size) { printf ("栈元素个数太少\n"); return ; } stack_size = size; stack = (STACK_TYPE *)malloc (stack_size * sizeof (STACK_TYPE)); if (NULL == stack) perror ("malloc分配失败"), exit (1); } void destroy_stack (void) { //assert (stack_size > 0); if (stack != NULL) { printf ("销毁堆栈\n");stack_size = 0; free (stack); stack = NULL; top_element = -1; } } void push (STACK_TYPE value) { //assert (!is_full ()); if (is_full ()) { printf ("栈已满，入栈失败\n"); return ; } top_element += 1; stack[top_element] = value; } void pop (void) { //assert (!is_empty ()); if (is_empty ()) { printf ("栈已空，出栈失败\n"); return ; } top_element -= 1; } STACK_TYPE top (void) { //assert (!is_empty ()); if (is_empty ()) { printf ("栈已空，出栈失败\n"); return ; } return stack[top_element]; } int is_empty (void) { //assert (stack_size > 0); if (stack != NULL) { return top_element == -1; } } int is_full (void) { //assert (stack_size > 0); if (stack != NULL) { return top_element == stack_size - 1; } } void travel (void) { int i = 0; if (top_element == -1) printf ("这个栈为空"); for (i = 0; i <= top_element; i++) printf ("%d ", stack[i]); printf ("\n"); } int size (void) { return top_element + 1; } 输出结果： 这个栈为空 栈已空，出栈失败 栈为空 push 压栈后的数值为: 0 1 2 3 4 5 6 7 8 9 此时栈顶元素为：9 此时栈元素个数为：10 经过pop弹出几个元素后的栈元素： 0 1 2 3 4 5 6 7 栈未满 栈未空 此时栈顶元素为：7 此时栈元素个数为：8 销毁堆栈 此时栈元素个数为：0

3、自写顺序栈

在压栈和出栈的时，使用 if 语句来判断栈是否为满或是否为空。如此，可以避免程序不必要的终止。 需要注意：if 语句最后使用的是 return ;而非 exit (1); 这方面参看：C语言再学习 -- 关键字return和exit ()函数 //使用顺序存储结构实现栈的基本操作 #include <stdio.h> #include <stdlib.h> #define SIZE 5 //给数据类型起别名，支持其他的数据类型 int arr[SIZE]; //存储具体的元素值 int pos; //记录数据的下表 //自定义函数实现入栈操作 //入栈==赋值 void push (int data); //自定义函数实现遍历操作 // 遍历==打印 void travel (void); //自定义函数实现出栈操作 int pop (void); //查看栈顶元素 int top (void); //判断栈是否为满 int full (void); //判断栈是否为空 int empty (void); //计算栈中元素的个数 int size (void); int main (void) { printf ("出栈的元素是：%d\n", pop ()); printf ("栈顶元素是：%d\n", top ()); int i = 0; for (i = 0; i <= 6; i++) push (i); travel (); printf ("出栈的元素是：%d\n", pop ()); travel (); printf ("栈顶元素是：%d\n", top ()); printf ("%s\n", full () ? "栈为满" : "栈未满"); printf ("%s\n", empty () ? "栈为空" : "栈未空"); printf ("栈元素个数为：%d\n", size ()); return 0; } void push (int data) { //判断为不为满 ，避免可能编译报错 if (full ()) { printf ("栈已满，入栈失败\n"); return ; } arr[pos++] = data; } void travel (void) { printf ("栈中元素有："); int i = 0; for (i = 0; i <= pos - 1; i++) printf ("%d ", arr[i]); printf ("\n"); } int pop (void) { //判断栈是否为空 if (!pos) { printf ("栈已空，出栈失败\n"); return ; } return arr[--pos]; } int top (void) { //判断栈是否为空 if (!pos) { printf ("栈已空， 查看栈元素失败\n"); return ; } return arr[pos - 1]; } int full (void) { return SIZE == pos; } int empty (void) { return 0 == pos; } int size (void) { return pos; } 输出结果： 栈已空，出栈失败 出栈的元素是：25 栈已空， 查看栈元素失败 栈顶元素是：35 栈已满，入栈失败 栈已满，入栈失败 栈中元素有：0 1 2 3 4 出栈的元素是：4 栈中元素有：0 1 2 3 栈顶元素是：3 栈未满 栈未空 栈元素个数为：4

4、顺序栈总结

（1）预分配空间 由用户指定堆栈最多能容纳得元素个数，即堆栈容量，分配足量的内存，几下堆栈容量，并将栈顶指针初始化为 0  （2）压入弹出 被压入的元素放在栈顶指针处，同时栈顶指针上移，被弹出的元素从栈顶指针的下面获得，同时栈顶指针下移。 （3）判空判满 栈顶指针为 0 表示堆栈已空，此时不可再弹出，栈顶指针大于等于堆栈容量比哦啊好似堆栈已满，此时不可再压入。

四、链式栈

由于只有堆栈顶部元素才可以被访问，因此使用单链表可以很好实现链式堆栈，而且无长度限制。把一个新元素压入堆栈是通过在链表的起始位置添加一个元素实现的。从堆栈中弹出一个元素是通过从链表中移除第 1 个元素实现的。位与链表头部的元素总是很容易被访问。由于没有长度限制，故不需要create_stack函数，但可以实现destroy_stack函数用于清空堆栈。由于用于存储元素的内存是动态分配的，它必须予以释放以避免内存泄漏。
代码实现说明： 主要讲下压栈和出栈。压栈：新建一个节点，让它后面的节点指向原来的栈顶节点，它成为新的栈顶节点。出栈：为栈顶节点找个替身，然后将栈顶节点指向栈顶后面的节点。

1、链式栈

/* 单链表实现堆栈，没有长度限制 */ #include <stdio.h> #include <stdlib.h> #include <assert.h>#define STACK_TYPE int /* 堆栈所存储的值的数据类型 */ #define FALSE 0/* 定义一个结构以存储堆栈元素。 */ typedef struct STACK_NODE {STACK_TYPE value;struct STACK_NODE *next; }StackNode; /* 指向堆栈中第一个节点的指针 */ static StackNode *stack; /*栈元素个数*/ static int cnt;/* 创建对栈，参数指定对栈可以保存多少个元素 注意：此函数只适用于动态分配数组形式的堆栈。*/ void create_stack (size_t size);/*销毁一个堆栈，释放堆栈所适用的内存注意，此函数只适用于动态分配数组和链表结构的堆栈。*/ void destroy_stack (void);/* 将一个新值压入堆栈中，参数是被压入的值。*/ void push (STACK_TYPE value);/* 弹出堆栈中栈顶的一个值，并丢弃。*/ void pop (void);/* 返回堆栈顶部元素的值，但不改变堆栈结构。*/ STACK_TYPE top (void);/* 如果堆栈为空，返回TRUE,否则返回FALSE。*/ int is_empty (void);/* 如果堆栈为满，返回TRUE,否则返回FALSE。*/ int is_full (void);/* 自定义函数实现遍历操作 */ void travel (void);/* 计算栈中元素的个数 */ int size (void);int main (void) {travel (); pop (); printf("%s\n", is_empty() ? "栈为空" : "栈未空"); int i = 0; for (i = 0; i <= 9; i++) { push (i); } puts ("push 压栈后的数值为: "); travel (); printf ("此时栈顶元素为：%d\n", top ()); printf ("此时栈元素个数为：%d\n", size ()); pop (); pop (); puts ("经过pop弹出几个元素后的栈元素： "); travel (); printf("%s\n", is_full() ? "栈为满" : "栈未满"); printf("%s\n", is_empty() ? "栈为空" : "栈未空"); printf ("此时栈顶元素为：%d\n", top ()); printf ("此时栈元素个数为：%d\n", size ()); destroy_stack ();printf ("此时栈元素个数为：%d\n", size ()); return 0; } /* 不再需要create_stack 函数 */ void create_stack (size_t size) {}void destroy_stack (void) {printf ("销毁堆栈\n");while (!is_empty ())pop (); /* 逐个弹出元素，逐个释放节点内存 */ }void push (STACK_TYPE value) {StackNode *new_node;new_node = (StackNode *)malloc (sizeof (StackNode));if (NULL == new_node)perror ("malloc fail");new_node->value = value; new_node->next = stack; /* 新元素插入链表头部 */ stack = new_node; /* stack 重新指向链表头部 */ cnt++; }void pop (void) {StackNode *first_node;//assert (!is_empty ());if (is_empty ()) { printf ("栈已空，出栈失败\n"); return ; } first_node = stack;stack = first_node->next;free (first_node);first_node = NULL;cnt--; }STACK_TYPE top (void) {//assert (!is_empty ());if (is_empty ()) { printf ("栈已空，出栈失败\n"); return ; } return stack->value; }int is_empty (void) {return stack == NULL; }int is_full (void) {return FALSE; }void travel (void) {StackNode *p_node;p_node = stack;printf ("打印出链式堆栈里面的值：");if (NULL == p_node)printf ("堆栈为空\n");while (p_node != NULL){printf ("%d ", p_node->value);p_node = p_node->next;}printf ("\n"); }int size (void) {return cnt; } 输出结果： 打印出链式堆栈里面的值：堆栈为空栈已空，出栈失败 栈为空 push 压栈后的数值为: 打印出链式堆栈里面的值：9 8 7 6 5 4 3 2 1 0 此时栈顶元素为：9 此时栈元素个数为：10 经过pop弹出几个元素后的栈元素： 打印出链式堆栈里面的值：7 6 5 4 3 2 1 0 栈未满 栈未空 此时栈顶元素为：7 此时栈元素个数为：8 销毁堆栈 此时栈元素个数为：0

2、自写链式栈

//基于链式存储结构的堆栈实现 #include <stdio.h> #include <stdlib.h>typedef struct Node {int data; //存放的具体元素struct Node *next; //存放下一个节点地址 }Node;typedef struct {int cnt;Node *head; }Stack;//入栈操作 void push (Stack *ps, int data);//遍历操作 void travel (Stack *ps);//出栈操作 int pop (Stack *ps);//查看栈顶元素 int top (Stack *ps);//判断堆栈是否为空 int empty (Stack *ps);//判断堆栈是否为满 int full (Stack *ps);//查看堆栈元素个数 int size (Stack *ps);int main (void) {Stack stack;stack.head = 0;stack.cnt = 0;printf ("%s\n", empty (&stack)? "堆栈为空" : "堆栈未空");printf ("出栈元素是：%d\n", pop (&stack));printf ("堆栈中元素的个数为：%d\n", size (&stack));printf ("--------------------------\n");push (&stack, 11); //11push (&stack, 22); //22 11push (&stack, 33); //33 22 11push (&stack, 44); //44 33 22 11travel (&stack); //44 33 22 11printf ("出栈元素是：%d\n", pop (&stack));travel (&stack); //33 22 11printf ("--------------------------\n");printf ("栈顶元素为：%d\n", top (&stack));printf ("%s\n", full (&stack) ? "堆栈为满" : "堆栈未满");printf ("%s\n", empty (&stack)? "堆栈为空" : "堆栈未空");printf ("堆栈中元素的个数为：%d\n", size (&stack));return 0; }void push (Stack *ps, int data) {//创建新节点并初始化Node *pn = (Node *)malloc (sizeof (Node));pn->data = data;pn->next = NULL;//插入新节点pn->next = ps->head;ps->head = pn;ps->cnt++; }void travel (Stack *ps) {printf ("堆栈中的元素有：\n");Node *p = ps->head;//判断堆栈为不为空while (p != NULL){printf ("%d ", p->data);//指向下一个节点p = p->next;}printf ("\n"); }int pop (Stack *ps) {//判断为不为空if (NULL == ps->head)return ;//保存要删除的节点地址Node *p = ps->head;//头指针指向下一个节点ps->head = ps->head->next;ps->cnt--;//存储要删除的节点元素值int tmp = p->data; //释放内存完毕后就没有元素值了free (p); //释放内存p = NULL; //置为空指针return tmp; }int top (Stack *ps) {//判断堆栈是否为空if (empty (ps))return ;return ps->head->data; }int empty (Stack *ps) {return NULL == ps->head; }int full (Stack *ps) {return 0; }int size (Stack *ps) {return ps->cnt; } 输出结果： 堆栈为空 出栈元素是：0 堆栈中元素的个数为：0 -------------------------- 堆栈中的元素有： 44 33 22 11 出栈元素是：44 堆栈中的元素有： 33 22 11 -------------------------- 栈顶元素为：33 堆栈未满 堆栈未空 堆栈中元素的个数为：3

3、链式栈总结

（1）无需预分配 不需要预分配存储空间，不需要记住堆栈容量，也不需要判断堆栈是否满，随压入随分配，随弹出随释放，提升内存空间利用率 （2）压入弹出 被压入的元素放在新建节点中，令其后指针指向栈顶节点，并令其成为新的栈顶节点，被弹出的元素由栈顶节点获得，释放栈顶节点，并令其后节点成为新的栈顶节点。 （3）判满判空 栈顶指针为空表示堆栈已空，此时不可再弹出。

五、栈实现计算器

参看：栈实现计算器 1、自左向右扫描表达式，凡是遇到操作数一律进操作数栈。
2、当遇到运算符时，如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之，取出栈顶运算符和操作数栈顶 的两个连续操作数运算，并将结果存入操作数栈，然后继续比较该运算符与栈顶的运算符的优先级。 3、左括号一律进运算符栈，右括号一律不进运算符栈，取出栈顶运算符和操作数栈顶的两个连续操作数运算，并将 结果存入操作数栈，直到取出左括号为止。 #include <stdio.h> #include <stdlib.h>#define MAX_SIZE 1024int operand[MAX_SIZE]; int top_num = -1;char oper[MAX_SIZE]; int top_oper = -1;//输入数据，将数据压入数据栈 void insert_operand (int value) {if (top_num == MAX_SIZE - 1)return ;top_num += 1;operand[top_num] = value; }//输入操作符，将操作符压入符号栈 void insert_oper (char ch) {if (top_oper == MAX_SIZE - 1)return ;top_oper += 1;oper[top_oper] = ch; }//比较操作符优先级 int compare (char ch) {//判断当前优先级是否比栈顶操作符优先级高if ((oper[top_oper] == '-' || oper[top_oper] == '+') && (ch == '*' || ch == '/'))return 0; //判断操作符是否为空，栈顶操作符是否为'(' else if (top_oper == -1 || ch == '(' || (oper[top_oper] == '(' && ch != ')'))return 0; //判断括号内的表达式是否计算完毕 else if (oper[top_oper] == '(' && ch == ')'){top_oper--;return 1;}elsereturn -1; }//进行数据运算 void deal_date (void) {//取出数据栈中两个数据int num1 = operand[top_num];int num2 = operand[top_num - 1];int value = 0;//进行加减乘除操作if (oper[top_oper] == '+')value = num1 + num2;else if (oper[top_oper] == '-')value = num2 -num1;else if (oper[top_oper] == '*')value = num1 * num2;else if (oper[top_oper] == '/')value = num2 / num1;//将数据栈顶下移一位，然后将得到的值压入数据栈，将操作符栈顶下移一位top_num--;operand[top_num] = value;top_oper--; }int main (void) {char ch;int i = 0;int num = 0;char *temp;char dest[MAX_SIZE];char *str = (char*)malloc (sizeof (char) * MAX_SIZE);scanf ("%s", str);while (*str != '\0') {temp = dest;while (*str >= '0' && *str <= '9') //判断是否为数据，遇到符号退出*(temp++) = *(str++);if (*str != '(' && *(temp - 1) != '\0') //判断是否为符号'('{*temp = '\0';num = atoi (dest); //将字符串转为数字insert_operand (num); }while (1){i = compare (*str); //判断操作符优先级if (i == 0) //压入操作符{insert_oper (*str);break;}else if (i == 1) //判断括号内表达式是否结束str++;else if (i == -1) //进行数据处理deal_date ();}str++; //指向表达式下一个字符}printf ("num = %d\n", operand[0]);return 0; } 输出结果： 1+2*(1+2)-2+(6/2) num = 8

六、逆波兰式计算器

参看：逆波兰算数表达式
扩展：波兰式、逆波兰式与表达式求值 传统的算术表达式是由操作数（又叫运算对象或运算量）和运算符以及改变运算次序的圆括号链接而成的式子。其运算规则如下： （1）先计算括号内，后计算括号外 （2）在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级 （3）同一优先级运算，从左向右依次进行 在这种表达式的计算过程中，既要考虑括号的作用，又要考虑运算符的优先级，还要考虑运算符出现的先后次序。 波兰科学家卢卡谢维奇(Lukasiewicz)提出了算术表达式的另一种表示，即后缀表示，又称逆波兰式，其定义是把运算符放在两个运算对象的后面。在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成。例如：
3/5+6的逆波兰表达式为3 5 / 6 +
2*(3+4)的逆波兰表达式为2 3 4 + * #include <stdio.h> #include <string.h> int tranfer(char *s) { int k=1,result=0,len = strlen(s); while(len--) { result += (s[len]-'0')*k; k *= 10; } return result; } main( ) { char s[50]; int j=0,num[100]; while((scanf("%s",s))!=EOF) { if(s[0]>='0'&&s[0]<='9') num[j++] = tranfer(s); else { switch(s[0]){ case '+': num[j-2] += num[j-1]; j--; break; case '-': num[j-2] -= num[j-1]; j--; break; case '*': num[j-2] *= num[j-1]; j--; break; case '/': num[j-2] /= num[j-1]; j--; break; } } } printf("%d\n",num[0]); } 输出结果： 2 3 + 5 * （按 CTRL + D 结束） num = 25

总结

以上是生活随笔为你收集整理的数据结构与算法 -- 栈 ADT的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。