基于顺序存储/链式存储实现栈结构

栈（Stack）

是限制在表一端进行插入和删除操作的线性表。允许进行插入、删除操作的这一端称为栈顶（Top），另一个固定端称为栈底。例如栈中有三个元素，近栈的顺序是a1、a2、a3，当需要出栈时顺序为a3,a2,a1,所以栈又称“后进先出”或“先进后出”的线性表，简称“LIFO表”或“FILO表”。

栈的存储结构和基本运算

由于栈是运算受限的线性表(各个元素依次存放在一组地址连续的存储单元中)，因此线性表的存储结构对栈也是适用的，只是操作不同而已。

（1）顺序栈

利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的一维数组来实现：datatype data[MAXSIZE]，栈底位置可以设置在数组的任意一个端点，而栈顶随着插入和删除而变化的，用int top来作为栈顶的指针，指明当前栈顶的位置，同样将data和top封装在一个结构中，顺序栈的类型描述如下：

typedef struct{
    int data[MAXSIZE];
    int top;
}Stack;

运算方法很简单，如下：

//初始化顺序存储结构的栈
int initStack(Stack* s){
    s->top = -1;
    return 1;
}
//压栈
int push(Stack *s,int e){
    if (s ->top == MAXSIZE - 1) {
        return 0;
    }
    s->top++;
    s->data[s->top] = e;
    return 1;
}

//出栈
int pop(Stack *s, int *e){
    if (s ->top == -1) {
        return 0;
    }
    *e = s->data[s->top];
    s->top--;
    return 1;
}
//获取栈顶
int getTop(Stack s, int *e){
    if (s.top == -1) {
        return 0;
    }
    *e = s.data[s.top];
    return 1;
}
//判断栈空
int stackEmpty(Stack s){
    if (s.top == -1) {
        return 1;
    }
    return 0;
}
//获取栈长度
int stackLength(Stack s){
   return s.top +1;
}
//清空栈
int clearStack(Stack s){
    s.top = -1;
    return 1;
}
//遍历栈
int traverseStack(Stack s){
    for (int i = 0; i <= s.top; i++) {
        printf("%d ", s.data[i]);
    }
    printf("\n");
    return 1;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    Stack stack;
    initStack(&stack);
    int input;
    printf("请输入要加入的元素\n");
    while (1) {
        scanf("%d", &input);
        if (input == 0) {
            break;
        }
        push(&stack, input);
    }
    
    traverseStack(stack);
    int po;
    pop(&stack, &po);
    printf("取出：%d\n", po);
    traverseStack(stack);
    return 0;
}

（2）链栈

用链式存储结构实现的栈称为链栈。通过链栈用单链表表示，因此其结点结构与单链表的结点结构相同，在此用LinkStack表示：

typedef struct StackNode{
    int data;
    struct StackNode* next;
}StackNode, *LinkStackPtr;

typedef struct{
    LinkStackPtr top;
    int count;
}LinkStack;

一些基本操作如下

//初始化链栈
int initStack(LinkStack *s){
    s = (LinkStack*)malloc(sizeof(LinkStack));
    if (s == NULL) {
        return 0;
    }
    s->top = NULL;
    s->count = 0;
    return 1;
}
//压栈
int push(LinkStack *s, int data){
    StackNode* node = malloc(sizeof(StackNode));
    if (node == NULL) {
        return 0;
    }
    node->next = s -> top;
    node->data = data;
    s->top = node;
    s->count ++;
    return 1;
}
//出栈
int pop(LinkStack *s, int* e){
    *e = s -> top ->data;//返回元素
    LinkStackPtr top = s -> top;
    s -> top = top -> next;
    s -> count --;
    free(top);
    return 1;
}
//获取栈顶元素
int getTop(LinkStack* s, int *e){
    if (s->top == NULL) {//判断链表是否为空
        return 0;
    }
    *e = s->top->data;
    return 1;
}
//遍历栈表
int traverseLinkStack(LinkStack s){
    LinkStackPtr p = s.top;//拿到top指针
    if (p == NULL) {
        printf("空链表");
    }
    while (p) {
        printf("%d ", p -> data);
        p = p ->next;//一层一层往下遍历
    }
    printf("\n");
    return 1;
}
//清空链表
int clearStack(LinkStack* s){
    LinkStackPtr p = s -> top;
    LinkStackPtr temp;
    while (p) {
        temp = p -> next;
        free(p);
        p = temp;
    }
    s->top = NULL;
    s->count = 0;
    return 1;
}
//栈长
int stackLength(LinkStack s){
    return s.count;
}

//判断链表是否为空
int stackEmpty(LinkStack s){
    if (s.top == NULL) {//判断链表是否为空或者 s->count == 0随你自己喜好
        return 1;
    }
    return 0;
}