栈（C实现）

1. 顺序栈

顺序栈的数据结构就是将一个数组的一端作为栈底，另一端为栈顶：

1. 定义栈的数组；
2. 设置栈的容量；
3. 设置top标记。

压栈：

//元素elem进栈，a为数组，top值为当前栈的栈顶位置
int push(int* a,int top,int elem){
    a[++top]=elem;
    return top;
}

出栈：

//数据元素出栈
int pop(int * a,int top){
    if (top==-1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%d\n",a[top]);
    top--;
    return top;
}

整体调用：

#include <stdio.h>
//元素elem进栈
int push(int* a,int top,int elem){
    a[++top]=elem;
    return top;
}
//数据元素出栈
int pop(int * a,int top){
    if (top==-1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%d\n",a[top]);
    top--;
    return top;
}
int main() {
    int a[100];
    int top=-1;
    top=push(a, top, 1);
    top=push(a, top, 2);
    top=push(a, top, 3);
    top=push(a, top, 4);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    return 0;
}

// 输出
弹栈元素：4
弹栈元素：3
弹栈元素：2
弹栈元素：1
空栈

2. 链栈

链栈就是将链表的头部作为栈顶，尾部作为栈底：

链表中结点结构

typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;

压栈：

//stack为当前的链栈，a表示入栈元素
lineStack* push(lineStack * stack,int a){
    //创建存储新元素的节点
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    //新节点与头节点建立逻辑关系
    line->next=stack;
    //更新头指针的指向
    stack=line;
    return stack;
}

出栈：

//栈顶元素出链栈的实现函数
lineStack * pop(lineStack * stack){
    if (stack) {
        //声明一个新指针指向栈顶节点
        lineStack * p=stack;
        //更新头指针
        stack=stack->next;
        printf("出栈元素：%d ",p->data);
        if (stack) {
            printf("新栈顶元素：%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}

整体调用：

#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,int a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}
lineStack * pop(lineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("弹栈元素：%d ",p->data);
        if (stack) {
            printf("栈顶元素：%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 1);
    stack=push(stack, 2);
    stack=push(stack, 3);
    stack=push(stack, 4);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}

// 输出
弹栈元素：4 栈顶元素：3
弹栈元素：3 栈顶元素：2
弹栈元素：2 栈顶元素：1
弹栈元素：1 栈已空
栈内没有元素