栈 Stack

Last in first out。只能从一端插入或者删除

操作 Operation

1. Push(x)：压栈。注意溢出情况
2. Pop()：弹出
3. Top()：返回栈顶元素
4. IsEmpty()：检测栈是否为空

应用场景

• 递归调用

• 文本编辑器中的撤回

• 编译器检查 “{}”

用数组实现栈

#include<stdio.h>
#define MAX_SIZE 101

int A[MAX_SIZE];
int top = -1; //空栈 

void Push(int x){
    //处理溢出情况
    if(top == MAX_SIZE-1){
        printf("Error:stack overflow\n");
        return;
    }
    //top++;
    //A[top] = x;
    //可缩写为：
    A[++top] = x;
}

void Pop(){
    //处理空栈情况
    if(top==-1){
        printf("Error:stack empty\n");
        return;
    }
    top--;
}

int Top(){
    return A[top];
}

int IsEmpty(){
    if(top ==-1){
        return true;
    }else{
        return false;
    }
}

用链表实现栈

显然把头节点作为栈顶更节省时间

#include<stdio.h>
#include<stdlib.h>

struct Node{
    int data;
    struct Node *link;
};
struct Node *top=NULL;

void Push(int x){
    struct Node *temp=(struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->link = top;
    top = temp;
}

void Pop(){
    struct Node *temp;
    //解决空栈的情况
    if(top==NULL) return;
    temp = top;
    top = temp->link;
    free(temp);
}

int Top(){
    return top->data;
}

int IsEmpty(){
    if(top==NULL){
        return true;
    }else{
        return false;
    }
}