时间:2021-05-19
栈定义:仅限在表尾进行插入和删除的线性表
栈的特点:
1)一般来说能在表尾进行进栈和出栈的数据
2)先进后出(last in first out )
3)栈会有栈顶,栈底,通常栈底为高地址,栈顶为高地址,如下图所示
操作系统一般会在内存划出一块,专门用于栈操作,当然这个跟普通的操作有些区别:比如存放数组,地址是增加的;但是在存入数据到栈,地址则是不断减小的
栈的存储结构:
复制代码 代码如下:
typedef struct _SQSTACK
{
SElemType* base;
SElemType* top;
int stacksize;
}
SqStack;
数据定义:
复制代码 代码如下:
//默认的存储空间的大小和空间增长大小
#define STACK_INIT_SIZE100
#define STACK_INCREMENT10
//存储数据的类型定义
#ifndef INT_TYPE
#define INT_TYPE
#endif // INT_TYPE
#ifdef INT_TYPE
typedefintSElemType;
#elif defined FLOAT_TYPE
typedeffloatSElemType;
#elif defined STRING_TYPE
typedefchar*SElemType;
#elif defined STRUCT_TYPE
typedefvoid*SElemType;
#endif
栈的操作,会涉及到初始化栈,销毁栈,进栈(入栈),出栈,还有判断栈空,栈大小,以及清空栈,如下:
栈的初始化:
复制代码 代码如下:
//初始化栈
int InitStack(SqStack *S)
{
S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if (!S->base)
{
return -1;
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return 0;
}
栈才初始化,里面还没有数据,这时候top,base都指向分配空间的基地址,表示栈空
销毁栈:
复制代码 代码如下:
//销毁栈
int DestroyStack(SqStack *S)
{
if (S->base)
{
free(S->base);
S->base = NULL;
S->top = NULL;
S->stacksize = 0;
}
return 0;
}
如果栈存在,就销毁地址空间,将栈尺寸置0
进栈:
复制代码 代码如下:
int Push(SqStack *S, const SElemType data)
{
assert(S->base != NULL);
if (S->top - S->base >= STACK_INIT_SIZE)
{
S->base = (SElemType*)realloc(S->base,
(STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
if (!S->base)
{
return -1;
}
S->top = S->base + S->stacksize;
S->stacksize += STACK_INCREMENT;
}
*S->top++ = data;
return 0;
}
如果栈存在,就销毁地址空间,将栈尺寸置0
进栈:
复制代码 代码如下:
int Push(SqStack *S, const SElemType data)
{
assert(S->base != NULL);
if (S->top - S->base >= STACK_INIT_SIZE)
{
S->base = (SElemType*)realloc(S->base,
(STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
if (!S->base)
{
return -1;
}
S->top = S->base + S->stacksize;
S->stacksize += STACK_INCREMENT;
}
*S->top++ = data;
return 0;
}
如果栈的大小大于已分配长度,重新分配空间,并使栈顶重新指向新的位置,之后就将数据存入当前栈顶指向的位置,然后栈顶+1
出栈:
复制代码 代码如下:
//出栈
int Pop(SqStack *S, SElemType *data)
{
assert(S->base != NULL);
if (S->base == S->top)
{
return -1;
}
*data = *(--S->top);
return 0;
}
首先将栈顶位置-1,然后取得当前位置的值
以下为辅助函数,如下:
复制代码 代码如下:
//栈是否为空
int IsStackEmpty(const SqStack &S)
{
return ((S.base == S.top) ? true:false);
}
复制代码 代码如下:
//得到栈的长度
int GetStackLength(const SqStack &S)
{
assert(S.base != NULL);
return S.stacksize;
}
复制代码 代码如下:
//清空栈
int ClearStack(SqStack *S)
{
assert(S->base != NULL);
if (S->base != S->top)
{
S->top = S->base;
}
S->stacksize = 0;
return 0;
}
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
顺序存储结构有顺序表、栈、队列等,顺序存储方式是指每个存储结点只含一个数据元素,所有存储结点连续存放。 顺序存储结构是存储结构类型中的一种,该结构是把逻辑上相
栈的存储结构是顺序存储结构和链表存储结构。就像一个箱子,后放的在上边,所以后进先出。 栈它是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取
顺序栈:利用一组连续的存储单元依次存放自栈底到栈顶的数据元素;由于栈顶元素是经常变动的,所以附设top指示栈顶元素在顺序表中的位置,同时也需要知道顺序栈存储空间
四大基本存储结构是顺序存储、链接存储、索引存储和散列存储。 存储结构分四类:顺序存储、链接存储、索引存储和散列存储。顺序结构和链接结构适用在内存结构中。索引结
数据的存储结构包括顺序存储和链式存储。 数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构