二、基本算法
1、进栈(PUSH)算法 ①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作②); ②置TOP=TOP+1(栈指针加1,指向进栈地址); ③S(TOP)=X,结束(X为新进栈的元素); 2、退栈(POP)算法 ①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈, 空则下溢;不空则作②); ②X=S(TOP),(退栈后的元素赋给X): ③TOP=TOP-1,结束(栈指针减1,指向栈顶)。
三、栈的实现
栈分顺序栈和链式栈,下面程序介绍了顺序栈的实现。
#include<stdio.h>#include<malloc.h>#define DataType int #define MAXSIZE 1024 typedef struct { DataType data[MAXSIZE]int top}SeqStackSeqStack *Init_SeqStack()//栈初始化 { SeqStack *ss=(SeqStack *)malloc(sizeof(SeqStack))if(!s) { printf("空间不足\n")return NULL} else { s->top=-1return s} } int Empty_SeqStack(SeqStack *s)//判栈空 { if(s->top==-1) return 1else return 0} int Push_SeqStack(SeqStack *s,DataType x)//入栈 { if(s->top==MAXSIZE-1) return 0//栈满不能入栈 else { s->top++s->data[s->top]=xreturn 1} } int Pop_SeqStack(SeqStack *s,DataType *x)//出栈 { if(Empty_SeqStack(s)) return 0//栈空不能出栈 else { *x=s->data[s->top]s->top--return 1}//栈顶元素存入*x,返回 } DataType Top_SeqStack(SeqStack *s)//取栈顶元素 { if(Empty_SeqStack(s)) return 0//栈空 else return s->data[s->top]} int Print_SeqStack(SeqStack *s) { int iprintf("当前栈中的元素:\n") for(i=s->topi>=0i--) printf("%3d",s->data[i])printf("\n")return 0} int main() { SeqStack *Lint n,num,mint iL=Init_SeqStack()printf("初始化完成\n")printf("栈空:%d\n",Empty_SeqStack(L))printf("请输入入栈元素个数:\n")scanf("%d",&n)printf("请输入要入栈的%d个元素:\n",n)for(i=0i<ni++) { scanf("%d",&num)Push_SeqStack(L,num)} Print_SeqStack(L)printf("栈顶元素:%d\n",Top_SeqStack(L))printf("请输入要出栈的元素个数(不能超过%d个):\n",n)scanf("%d",&n)printf("依次出栈的%d个元素:\n",n)for(i=0i<ni++) { Pop_SeqStack(L,&m)printf("%3d",m)} printf("\n")Print_SeqStack(L)printf("栈顶元素:%d\n",Top_SeqStack(L))return 0}
#include#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语言中的堆和栈都是一种数据项按序排列的数据结构。
栈就像装数据的桶或箱子
我们先从大家比较熟悉的栈说起吧,它是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取。
这就如同我们要取出放在箱子里面底下的东西(放入的比较早的物体),我们首先要移开压在它上面的物体(放入的比较晚的物体)。
堆像一棵倒过来的树
而堆就不同了,堆是一种经过排序的树形数据结构,每个结点都有一个值。
通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。
由于堆的这个特性,常用来实现优先队列,堆的存取是随意,这就如同我们在图书馆的书架上取书。
虽然书的摆放是有顺序的,但是我们想取任意一本时不必像栈一样,先取出前面所有的书,书架这种机制不同于箱子,我们可以直接取出我们想要的书。
扩展资料:
关于堆和栈区别的比喻
使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。
参考资料来源:百度百科-堆栈