最后的城堡 下载:C程序中如何使用堆栈

最简单实用的写法

例：
int stack[100+1];
int top = -1;

进栈 stack[++top] = value;
出栈 value = stack[top--];
if(top<0) 栈为空
if(top==100) 栈满

学数据结构， 学的是思想
实现起来可以各种各样， 只要你写的熟练了， 就会觉得很简单， 关键还是明白原理是什么， 为什么这种数据结构适合这种问题， 为什么它的时间复杂度更好

而且到后来， 数据结构根本不用你自己去写， 写STL（标准模板库）的人， 写了十几年甚至几十年的数据结构， 他们不比咱写的好？

举个例子， 自己写个红黑树要150行都不一定写得好。 用STL， 就像用int一样简单， 直接声明、 调用函数。 所以你要知道的就是红黑树是什么， 为什么好使。

数据结构很重要， 但不难， 慢慢来， 掌握好学习方法:)

先从大家比较熟悉的栈说起，它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。这就如同要取出放在箱子里面底下的东西（放入的比较早的物体），首先要移开压在它上面的物体（放入的比较晚的物体）。而堆就不同了，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同在图书馆的书架上取书，虽然书的摆放是有顺序的，但是想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，可以直接取出想要的书。
下面就说说C语言程序内存分配中的堆和栈，这里有必要把内存分配也提一下，一般情况下程序存放在Rom或Flash中，运行时需要拷到内存中执行，内存会分别存储不同的信息。
内存中的栈区处于相对较高的地址以地址的增长方向为上的话，栈地址是向下增长的，栈中分配局部变量空间，堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量，全局变量空间的；只读区是分配常量和程序代码空间的；以及其他一些分区。来看一个网上很流行的经典例子：
main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[] = "abc"; 栈
char *p2; 栈
char *p3 = "123456"; 123456\0在常量区，p3在栈上。
static int c =0； 全局（静态）初始化区
p1 = (char *)malloc(10); 堆
p2 = (char *)malloc(20); 堆
}
堆和栈的第一个区别就是申请方式不同：栈（英文名称是stack）是系统自动分配空间的，例如定义一个 char a；系统会自动在栈上为其开辟空间。而堆（英文名称是heap）则是程序员根据需要自己申请的空间，例如malloc（10）；开辟十个字节的空间。由于栈上的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。

堆栈是一种执行“后进先出”算法的数据结构。

设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球，小球的直径比竹筒的直径略小。现在把不同编号的小球放到竹筒里面，可以发现一种规律：先放进去的小球只能后拿出来，反之，后放进去的小球能够先拿出来。所以“先进后出”就是这种结构的特点。

堆栈就是这样一种数据结构。它是在内存中开辟一个存储区域，数据一个一个顺序地存入（也就是“压入——push”）这个区域之中。有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元，存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫做“栈底”。数据一个一个地存入，这个过程叫做“压栈”。在压栈的过程中，每有一个数据压入堆栈，就放在和前一个单元相连的后面一个单元中，堆栈指示器中的地址自动加1。读取这些数据时，按照堆栈指示器中的地址读取数据，堆栈指示器中的地址数自动减 1。这个过程叫做“弹出pop”。如此就实现了后进先出的原则。

堆栈是计算机中最常用的一种数据结构，比如函数的调用在计算机中是用堆栈实现的。
堆栈可以用数组存储，也可以用以后会介绍的链表存储。
下面是一个堆栈的结构体定义，包括一个栈顶指针，一个数据项数组。栈顶指针最开始指向-1,然后存入数据时，栈顶指针加1，取出数据后，栈顶指针减1。

#define MAX_SIZE 100
typedef int DATA_TYPE;
struct stack
{
DATA_TYPE data[MAX_SIZE];
int top;
};

堆栈采用先进后出的策略
基本操作是存和取
习惯称
push（压入）
pop（弹出）

//先要确定开辟内存区的大小
＃define Max ???
//用于指向开辟的内存空间
int *p
//指向堆顶
int *tos
//指向堆底
int *bos
//添加一个数据到堆顶
void push(int i)
{
if(p>bos)
{
printf("堆栈已满\n");
return;
}
*p=i;
p++;
}
//从堆栈取出一个数据
int pop(void)
{
p--;
if(p<tos)
{
printf("堆栈下溢\n");
return 0;
}
return *p;
}

...
...

是的，同意楼上的，数据结构学的是编程思想，解决问题的方法，而非只在于课本上提供的那些代码！
我当时学的时候一看数据结构课本上怎么会有这么多的实例代码，查点不学这一门了，后来在听课中才知道，这些实例是没有用的，只要你学懂了，课本上的东西一下全在你脑子里，根本就是不需要课本的了，然而我觉得课本上的实例实在是对自学者（或喜欢看实例的人）有一个阻碍使用！当然你要明白数据结构这一门知识应该学的是什么，目的明确了才能学好它！