首页 > 代码库 > 栈的表示和实现

栈的表示和实现

2024-07-02 00:31:11   227人阅读

　　栈是限定仅在表尾进行插入或者删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶，表头端为栈底。不含元素的空表称为空栈。栈的主要特点就是后进先出(LIFO);

栈的表示和实现

　　顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法以top=0表示空栈。一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不足在进行扩展。

以下是栈的顺序存储表示

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct SqStack
{
    int *base;
    int *top;
    int stacksize;
}SqStack;
int InitStack(SqStack &S)
{
    S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
    if(!S.base)
        exit(0);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return 0;
}
int GetTop(SqStack S,int &e)
{
    if(S.top==S.base)
        return 1;
    e=*(S.top-1);
    return 0;
}
int Push(SqStack &S,int e)
{
    if(S.top-S.base>=S.stacksize)
    {
        S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
        if(!S.base)
            return 1;
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }
    *S.top=e;
    S.top++;
    return 0;
}
int Pop(SqStack &S,int &e)
{
    if(S.top==S.base)
        return 1;
    --S.top;
    e=*S.top;
    return 0;
}
int StackEmpty(SqStack S)
{
    if(S.top==S.base)
        return 1;
    return 0;
}
int DestroyStack(SqStack &S)
{
    free(S.base);
    S.top=NULL;
    S.base=S.top;
    return 0;
}

 


联系
我们