栈的顺序存储结构
程序员文章站
2024-01-29 11:53:46
...
栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。
既然栈是线性表的特征,那么栈的顺序存储其实也是线性表顺序存储的简化,我们称为顺序栈。线性表是用数组来实现的,我们定义一个top变量来指示栈顶元素在数组中的位置,栈顶的top可以变大变小,栈顶位置top必须小于存储栈的长度。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1。
栈的结构定义如下:
typedef int SElemType;
typedef struct
{
SElemType data[MAXSIZE];
int top; //用于栈顶指针
}SqStack;
1.进栈操作
对于栈的插入,即进栈操作,如下图所示:
对于进栈操作push,代码如下:
int Push(SqStack *S, SElemType e)
{
if(S->top == MAXSIZE - 1) //栈满
{
return ERROR;
}
S->top++; //栈顶指针增加1
S->data[S->top] = e; //将新插入元素复制给栈顶空间
return OK;
}
2.出栈操作pop,代码如下:
int Pop(SqStack *S, SElemType *e)
{
if(S->top == -1)
{
return ERROR;
}
*e = S->data[S->top]; //将要删除的栈顶元素赋值给e
S->top--; //栈顶指针减一
return OK;
}