#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++弄成一个类^_^
程序中,一个函数是一个过程,这个过程可以分为包括传入参数、过程代码、返回三部分构成。由于一个函数过程需要用到内部变量、临时变量等,所以需要在进程空间的栈空间分配一段存储片段来存储函数过程中的这些参数,该内存片段即为栈帧。栈帧的由来:
为一个函数的过程提供一个存储函数局部变量,参数,返回地址和其他临时变量;
栈帧的周期:
进入函数~函数返回,该阶段内栈帧作为
不同的语言具体的实现方式略有不同,但是,总体上,fun(a,b)
局部变量:
包括函数传入的形参和函数内部定义的变量;
返回地址:
指令指针p指向call
fun,那么fun栈帧存储的返回地址为p+1现今的编译器的一个约定是将返回地址存到一个固定的寄存器中,这样比读取栈帧(内存)效率要高。
临时变量:
主要为计算,运算过程中的中间临时变量;
参数传递:
其一:如果fun中调用另一个函数k(a,b...n)那么,传递的参数是形参,按照现代编译规定,前k个形参是通过寄存器传递,后n-k个形参通过栈帧的实参部分(栈帧的尾部)来传递;
其二:主要为在fun中要调用函数g(&a,&b),那么为g()函数传出实参(形参是通过寄存器来传递的)是通过“传出实参”区块进行的,这么做主要是为了保证该实参能够被内层嵌套的函数访问。比如,g函数由调用一个k(a地址)函数,同样需要用到a的地址,所以fun在传递参数时必须为实参(&a)传递申请固定的内存存储空间(而非用寄存器)这样k函数可以通过固定的内存地址(fun的形参列表来获取参数值)。这时的g的栈帧为fun栈帧的下一帧(相邻的空间地址),即调用者和被调用者的栈帧是相连的;
保护的寄存器:
栈帧作为函数过程的一个临时内存存储区块,同时负责函数调用过程中寄存器值的保存和还原。即:假设fun函数目前占用了寄存器ri存储一个临时变量t,而此时调用了函数g(),在g()函数中可能需要用到寄存器ri做运算的临时存储,那么如何确保g()函数调用返回后,ri恢复到fun中t的原来值。这就需要在调用者或者被调用者中选择其一来保存原有ri的值,即caller-save或者callee-save。