6.王道考研数据结构-栈

文章目录

• 一、栈的基本操作
• 二、栈的顺序存储结构
• 2.1 栈的初始化
• 2.2 判断栈空
• 2.3 栈的进栈
• 2.4 栈的出栈
• 2.5 读出栈顶元素
• 2.6 共享栈
• 三、栈的链式存储结构

一、栈的基本操作

二、栈的顺序存储结构

#define MaxSize 50
#define ElemType int
typedef struct
{
    ElemType data[MaxSize];//保存数据的数组
    int top;//指向栈顶数组下标（最初为-1）
}SqStack;

2.1 栈的初始化

void InitStack(SqStack *&s){
    s = (SqStack*)malloc(sizeof(SqStack));
    s->top=-1;
}

2.2 判断栈空

bool IsEmpty(SqStack *&s){
    return s->top == -1;
}

2.3 栈的进栈

bool Push(SqStack *&s, ElemType e){
    //判断栈有没有满
    if(s->top == -1)
        return false;
    s->data[++s->top] = e;
    return true;
}

2.4 栈的出栈

bool Pop(SqStack *&s, ElemType &e){
    //如果栈为空，则返回false
    if(s->top == -1)
        return false;
    e = s->data[s->top--];
    return true;
}

2.5 读出栈顶元素

bool GetTop(SqStack *&s, ElemType &e){
    if(s->top==-1)
        return false;
    e = s->data[s->top];
    return true;
}

2.6 共享栈

三、栈的链式存储结构

typedef struct LinkNode
{
    ElemType data;
    struct LinkNode *next;
}LinkStack;