数据结构--顺序栈

news/2024/12/14 12:17:00/

一.相关概念:

1.栈和队列是操作受限的线性表,是限定性的数据结构;
2.栈分为顺序栈和链式栈
3.栈只能在一端进行操作(插入,删除);
4.栈是限定仅在表尾进行插入或删除操作的线性表.因此,对栈来说,表尾端有其特殊含义,称为栈顶(top),相应地,表头端称为栈底(bottom).
5.不含元素地空表称为空栈.

二.顺序栈的结构:

typedef struct Stack{
int* base;//指向动态内存;
int top;//栈顶指针,实际上是下标,其实就是可以放数据的下标
int stacksize;//栈的总大小
}Stack,*PStack;

三.顺序栈的实现

//初始化
//输出参数
bool  GetTop(PStack ps,int *rtval)
{assert(ps != NULL);if (ps == NULL){return false;}if (IsEmpty(ps)){return   false;}*rtval=ps->base[ps->top - 1];return true;	
}//获取栈顶元素的值,但是删除
bool   Pop(PStack ps,int *rtval)
{assert(ps != NULL);if (ps == NULL){return false;}if (IsEmpty(ps)){return   false;}//*rtval = ps->base[ps->top - 1];//OK//ps->top--;//OK*rtval = ps->base[--ps->top];return true;
}//判空
bool IsEmpty(PStack ps)
{return ps->top == 0;
}//获取栈中有效元素的个数
int  GetLength(PStack ps)
{assert(ps != NULL);if (ps == NULL)return  -1;return ps->top;//top为有效数据的个数
}//清空所有的数据
void Clear(PStack ps)
{assert(ps != NULL);if (ps == NULL)return;ps->top = 0;
}//销毁
void Destroy(PStack ps)
{assert(ps != NULL);if (ps == NULL)return;free(ps->base);ps->base = NULL;ps->top = 0;ps->stacksize = 0;
}