堆栈的顺序存储
#include<stdio.h>
#include<stdlib.h>
#defineFALSE0
#defineTRUE1
typedefintElemType;
typedefintBOOL;
typedefstruct
{
inttop; //栈顶
intmaxSize; //堆栈最大的栈顶下标位置（存储空间）
ElemType*element; //存储堆栈的元素
}Stack;
//创建一个能容纳mSize个单元的空栈
voidCreate(Stack*S,intmSize)
{
S->maxSize =mSize- 1;
S->element = (ElemType*)malloc(sizeof(ElemType)*mSize);
S->top = -1;
}
//销毁一个已存在的堆栈，即释放堆栈占有的数组空间
voidDestroy(Stack*S)
{
S->maxSize = -1;
free(S->element);
S->top=-1;
}
//判断堆栈是否为空栈，若是，则返回TRUE；否则返回FALSE;
BOOLIsEmpty(Stack*S)
{
returnS->top == -1;
}
//判断堆栈是否已满，若是，则返回TRUE,否则返回FALSE
BOOLIsFULL(Stack*S)
{
returnS->top ==S->maxSize;
}
//获取栈顶元素，并通过x返回。若操作成功，则返回TRUE;否则返回FALSE.
BOOLTop(Stack*S,ElemType*x)
{
if(IsEmpty(S)) //空栈处理
returnFALSE;
*x=S->element[S->top];
returnTRUE;
}
//在栈顶位置插入元素x（入栈操作）。若操作成功，则返回TRUE，否则返回FALSE.
BOOLPush(Stack*S,ElemTypex)
{
if(IsFULL(S)) //溢出处理
returnFALSE;
S->top++;
S->element[S->top] =x;
returnTRUE;
}
//删除栈顶元素（出栈操作）。若操作成功，则返回TRUE，否则返回FALSE.
BOOLPop(Stack*S)
{
if(IsEmpty(S)) //空栈处理
returnFALSE;
S->top--;
returnTRUE;
}
//清除堆栈中的全部元素，但并不释放空间。
voidClear(Stack*S)
{
S->top = -1;
}
//输出
intoutput(StackS)
{
intx;
if(IsEmpty(&S))
returnFALSE; //空栈处理
while(!IsEmpty(&S)){
Top(&S, &x); //获取栈顶元素
Pop(&S); //删除栈顶元素
printf("%d", x); //打印栈顶元素
}
returnTRUE;
}
intmain()
{
inti, x;
StackS;
Create(&S, 10); //创建一个能容纳mSize个单元的空栈
for(i = 0; i < 10; i++) //将0到9依次存入栈中
Push(&S, i);
printf("顺序栈中的元素：");
output(S);
Top(&S, &x); //获取栈顶元素
printf("\n顺序栈中栈顶的元素：");
printf("%d", x); //打印栈顶元素
Pop(&S); //删除栈顶元素
printf("\n顺序栈中的元素：");
output(S); //输出删除一个栈顶元素后的顺序栈
Clear(&S); //清除堆栈中的全部元素，但并不释放空间。
output(S);
printf("\n");
}
//堆栈的链接表示（先进后出，后进先出）
#include<stdio.h>
#include<stdlib.h>
#defineERROR0
#defineOK1
#defineOverflow2 //Overflow表示上溢
#defineUnderflow3 //Underflow表示下溢
#defineNotPresent4 //NotPresent表示元素不存在
#defineDuplicate5 //Duplicate表示有重复元素
typedefintElemType;
typedefintBOOL;
typedefstructNode{
ElemTypeelement;
structNode*link;
}Node;
typedefstruct{
intn;
structNode*top;
}Stacklist;
//创建
BOOLCreate(Stacklist*s){
s->top =NULL;
s->n = 0;
returnOK;
}
//销毁
voidDestroy(Stacklist*s){
Node*p;
while(s->top){
p =s->top->link;
free(s->top);
s->top = p;
}
}
//判断是否为空
BOOLIsEmpty(Stacklist*s){
returns->top ==NULL;
}
//获取栈顶元素
BOOLTop(Stacklist*s,ElemType*x){
if(IsEmpty(s))
returnERROR;
*x=s->top->element;
returnOK;
}
//在栈顶位置插入元素x（入栈）
BOOLPush(Stacklist*s,ElemTypex){
Node*p = (Node*)malloc(sizeof(Node)) ;
if(p==NULL)
return0;
p->element =x;
p->link =s->top;
s->top = p;
s->n++;
returnOK;
}
//删除栈顶元素（出栈）
BOOLPop(Stacklist*s){
Node*p;
if(IsEmpty(s)){
return0;
}
p =s->top;
s->top =s->top->link;
free(p);
s->n--;
returnOK;
}
//清除堆栈中的所有元素，但不释放空间
voidClear(Stacklist*s){
s->top =NULL;
}
//输出
BOOLoutput(Stacklists){
intx;
if(IsEmpty(&s))
returnERROR;
while(!IsEmpty(&s)){
Top(&s, &x); //获取
Pop(&s);
printf("%d", x);
}
returnOK;
}
intmain(){
inti;
Stacklists;
Create(&s);
for(i = 0; i < 10; i++)
Push(&s, i);
printf("链接栈中的元素：");
output(s);
Clear(&s);
printf("\n");
}
网友评论