堆栈

栈是一种后进先出的线性表。

顺序存储

结构:

typedef struct _s{
    int *Data;    // 数组(动态内存分配的方式实现)
    int MaxSize;    // 栈的大小
    int Top;    // 栈顶
} *Stack;

相关操作:

Stack Create(int MaxSize);    // 创建栈
int IsFull(Stack s);
int IsEmpty(Stack s);    // 判断栈是否为空    
void Push(Stack s, int Data);    // 入栈
int Pop(Stack s);    // 出栈 返回栈顶值

创建栈:

Stack Create(int MaxSize){
    Stack s = (Stack)malloc(sizeof(struct _s));
    s->Data = (int *)malloc(sizeof(MaxSize * sizeof(int)));    // 申请内存空间
    s->MaxSize = MaxSize;
    s->Top = -1;    // -1为空栈
}

入栈:

void Push(Stack s, int Data){
    if(s->Top == s->MaxSize-1){
        printf("入栈失败!\n");
    }else{
        s->Data[++(s->Top)] = Data;
    }
}

出栈:

int Pop(Stack s){
    if(s->Top == -1){
        printf("栈为空!\n");
        return 0;
    }else{
        int temp = s->Data[(s->Top)--];
        return temp;
    }
}

判断是否为空:

int IsEmpty(Stack s){
    return s->Top = -1;
}
int IsFull(Stack s){
    return s->Top == s->MaxSize - 1;
}

链式存储

相关操作:

Stack Create();    // 创建栈
int IsEmpty(Stack s);    // 判断是否为空
void Push(Stack s, int Data);    // 入栈
int Pop(Stack s, int Data);    //出栈 返回栈顶值

结构:

typedef struct _s{
    int Data;
    struct _s *next;
} *Stack;

创建栈:

Stack Create(){
    
    Stack s = (Stack)malloc(sizeof(struct _s));
    s->next = NULL;
    return s;

}

判断是否为空:

int IsEmpty(Stack s){
    
    return s->next == NULL;

}

入栈:

void Push(Stack s, int Data){

    Stack temp = (Stack)malloc(sizeof(struct _s));
    temp->Data = Data;
    temp->next = s->next;
    s->next = temp;
    
}

出栈:

int Pop(Stack s){
    
    Stack p;
    int temp;
    if(s->next == NULL){
        printf("栈为空!\n");
        return 0;
    } 
    p = s->next;
    temp = p->Data;
    s->next = p->next;
    free(p);
    
    return temp;
    
}

参考

浙大版《数据结构》