数据结构–顺序栈的实现

顺序栈的定义

顺序栈的定义代码实现

#define MaxSize 10
typedef struct 
{
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针
} SqStack;

int main()
{
    SqStack S; //声明一个顺序栈(分配空间)
    //... ...
    return 0;
}

一些常见操作

初始化操作

void InitStack(SqStack &S)
{
    S.top = -1; //初始化栈顶指针
}

判断栈空

bool StackEmpty(SqStack S)
{
    return S.top == -1;
}

进栈操作

bool Push(SqStack &S, ElemType x)
{
    if (S.top == MaxSize - 1)   return false; //栈满
    S.data[++S.top] = x;
    return true;
}

出栈操作

bool Pop(SqStack &S, ElemType &x)
{
    if (S.top == -1)    return false;
    x = S.data[S.top--];
    return true;
}

读栈顶元素操作

bool GetTop(SqStack S, ElemType &x)
{
    if (S.top == -1)    return false;
    x = S.data[S.top];
    return true;
}

共享栈

两个栈共享同一片空间

共享栈定义代码实现

typedef struct 
{
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top0; //0号栈栈顶指针
    int top1; //1号栈栈顶指针
} ShqStack;

void InitStack(ShqStack &S)
{
    S.top0 = -1;
    S.top1 = MaxSize;
}

栈满的条件 \color{purple}栈满的条件 栈满的条件:top0+ 1 == top1

知识点回顾与重要考点