付费节点推荐
免费节点
节点使用教程
前言：
栈和队列是两种十分重要的数据结构，从数据结构的角度看，它们也同样是线性表，但是它们与一般的线性表又有区别，因为我们对于栈和队列的操作是受到限制的，由于栈和队列的重要性与特殊性，所以书中也特别用了一章的篇幅来介绍，那么接下来，就让我们先从最基本的顺序栈开始吧。
注：
顺序栈
栈是限定尽在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶(top)，表头端称为栈底(bottom)。不含元素的空表称为空栈。
栈又称为后进先出(LIFO)的线性表。
1.存储结构
根据栈的定义，我们要明确栈顶和栈底的指针，然后我们还要记录此时栈的最大容量
[cc lang="c"]
typedef struct
{
SElemType *base; //栈底指针，在栈构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
} SqStack; //顺序栈
[/cc]
2.空栈构造
首先当然还是分配内存，然后让栈顶和栈底指针指向同一位置，最后将容量分配给stacksize
[cc lang="c"]
Status InitStack(SqStack *S)
{
//操作结果：构造一个空栈S
(*S).base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base) exit(OVERFLOW); //存储分配失败
(*S).top = (*S).base;
(*S).stacksize = STACK_INIT_SIZE;
return OK;
}
[/cc]
3.插入删除
栈的插入与删除都只能在栈顶进行，在插入的过程中要注意判断是否已经超过了分配的容量，一旦超过就要增加新的容量。删除也必须注意此时栈是否为空，如果为空则不能进行删除。
[cc lang="c" escaped="true"]
tatus Push(SqStack *S,SElemType e)
{
//操作结果：插入元素e为新的栈顶元素
if((*S).top-(*S).base>=(*S).stacksize) //栈满，追加存储空间
{
(*S).base = (SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base) exit(OVERFLOW); //存储分配失败
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top++) = e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{
//操作结果：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if((*S).top==(*S).base) return ERROR;
*e = (*(--(*S).top));
return OK;
}
[/cc]
4.其他操作
[cc lang="c" escaped="true"]
Status DestroyStack(SqStack *S)
{
//操作结果：销毁栈S，S不再存在
free((*S).base);
(*S).base = NULL;
(*S).top = NULL;
(*S).stacksize = 0;
return OK;
}
Status ClearStack(SqStack *S)
{
//操作结果：把S置为空栈
(*S).top = (*S).base;
return OK;
}
Status StackEmpty(SqStack S)
{
//操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE
return S.top == S.base;
}
int StackLength(SqStack S)
{
//操作结果：返回S的元素个数，即栈的长度
return S.top-S.base;
}
Status GetTop(SqStack S,SElemType *e)
{
//操作结果：若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top>S.base)
{
*e = *(S.top-1);
return OK;
}
return ERROR;
}
Status StackTraverse(SqStack S,Status(*visit)(SElemType))
{
//操作结果：从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败
while(S.top>S.base)
visit(*S.base++);
printf("\n");
return OK;
}
[/cc]
5.具体测试
[cc lang="c" escaped="true"]
#include "my.h" //包含所有必须的头文件
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int SElemType; //存储空间初始分配量
typedef int Status; //存储空间分配增量
typedef struct
{
SElemType *base; //栈底指针，在栈构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
} SqStack; //顺序栈
Status InitStack(SqStack *S)
{
//操作结果：构造一个空栈S
(*S).base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base) exit(OVERFLOW); //存储分配失败
(*S).top = (*S).base;
(*S).stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack *S)
{
//操作结果：销毁栈S，S不再存在
free((*S).base);
(*S).base = NULL;
(*S).top = NULL;
(*S).stacksize = 0;
return OK;
}
Status ClearStack(SqStack *S)
{
//操作结果：把S置为空栈
(*S).top = (*S).base;
return OK;
}
Status StackEmpty(SqStack S)
{
//操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE
return S.top == S.base;
}
int StackLength(SqStack S)
{
//操作结果：返回S的元素个数，即栈的长度
return S.top-S.base;
}
Status GetTop(SqStack S,SElemType *e)
{
//操作结果：若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top>S.base)
{
*e = *(S.top-1);
return OK;
}
return ERROR;
}
Status Push(SqStack *S,SElemType e)
{
//操作结果：插入元素e为新的栈顶元素
if((*S).top-(*S).base>=(*S).stacksize) //栈满，追加存储空间
{
(*S).base = (SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base) exit(OVERFLOW); //存储分配失败
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top++) = e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{
//操作结果：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if((*S).top==(*S).base) return ERROR;
*e = (*(--(*S).top));
return OK;
}
Status StackTraverse(SqStack S,Status(*visit)(SElemType))
{
//操作结果：从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败
while(S.top>S.base)
visit(*S.base++);
printf("\n");
return OK;
}
Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}
int main()
{
int j;
SqStack s;
SElemType e;
if(InitStack(&s)==OK)
for(j=1; j<=12; j++)
Push(&s,j);
printf("栈中元素依次为：");
StackTraverse(s,visit);
Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
DestroyStack(&s);
printf("销毁栈后，s.top=%u s.base=%u s.stacksize=%d\n",s.top,s.base, s.stacksize);
return 0;
}
[/cc]
总结：
栈是很有用的一种数据结构，深入的理解并学会使用栈对于以后也是很有帮助。
评论前必须登录！
登陆 注册