#include
#define Max 100
typedef char T
typedef struct MyStack
{
T aa[Max]
unsigned int p
} stack
//创建空栈
stack* createEmptyStack()
{
stack* st = (stack *)malloc(sizeof(stack))
int i=0
for(i=0i<Maxi++)
st->aa[i]=0
st->p=0
return st
}
//栈判空
int isEmpty(const stack* st)
{
if(st->p==0) return 1
else return 0
}
//求栈的大小
unsigned int size(const stack* st)
{
return st->p
}
//push操作
void push(stack* st,const T a)
{
st->p=st->p+1
if(st->p==Max)
{
printf("栈满\n")
st->p--
return
}
st->aa[st->p]=a
}
//pop操作
T pop(stack* st)
{
if(isEmpty(st))
{
printf("栈空")
return NULL
}
char t=st->aa[st->p]
st->p=st->p-1
printf("%c ",t)
return t
}
//栈销毁
void destroy(stack* st)
{
free(st)
}
int main()
{
stack* st = createEmptyStack()
if(isEmpty(st)) printf("MyStack is empty\n")
else printf("MyStack is not empty\n")
push(st,'a')
push(st,'b')
push(st,'c')
push(st,'d')
push(st,'e')
printf("%d\n",size(st))
while(!isEmpty(st)) pop(st)
destroy(st)
system("pause")
return 0
}
堆栈就是先入后出的数据结构。如果用c语言来实现的话用个struct
先定义一个栈的节点
struct
node
typedef
strcut
node
*
position
typedef
position
stack
stack
creat()
void
push(int,stack)
int
pop(stack)
int
top()
struct
node
{
int
element
position
next
}
stack
creat()
{
stack
s
s=malloc(sizeof(struct
node))
s->next==NULL
}
void
push(int
a,stack
s)
{
position
temp
temp=malloc(sizeof(struct
node))
temp->element=a
temp->next=s->next:
s->next=temp
}
int
pop(stack
s)
{
int
res=s->next->element
position
temp=s->next
s->next=temp->next
free
temp
}
int
top(stack
s)
{
return
s->next->element
}
好啦,先creat()一个栈,再进行push
pop等。程序中忽略了麻烦的错误检测给出了重点,当然还可以添加其他操作。。对了,头文件也要加上。本人还是习惯用c++弄成一个类^_^
先从大家比较熟悉的栈说起,它是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取。这就如同要取出放在箱子里面底下的东西(放入的比较早的物体),首先要移开压在它上面的物体(放入的比较晚的物体)。而堆就不同了,堆是一种经过排序的树形数据结构,每个结点都有一个值。通常所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。由于堆的这个特性,常用来实现优先队列,堆的存取是随意,这就如同在图书馆的书架上取书,虽然书的摆放是有顺序的,但是想取任意一本时不必像栈一样,先取出前面所有的书,书架这种机制不同于箱子,可以直接取出想要的书。下面就说说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);开辟十个字节的空间。由于栈上的空间是自动分配自动回收的,所以栈上的数据的生存周期只是在函数的运行过程中,运行后就释放掉,不可以再访问。而堆上的数据只要程序员不释放空间,就一直可以访问到,不过缺点是一旦忘记释放会造成内存泄露。