栈

栈是一种先进后出的线性数据结构，规定只允许在一端进行插入和删除元素的操作。其中进栈操作又叫做压栈（Push），出栈操作又叫做弹出（Pop）。允许进行操作的一端叫做栈顶（top），另一端叫做栈底（base）。

分类

• 顺序栈：数组实现
• 链式栈：链表实现

代码实现

顺序栈

1.构建栈的结构

#define MAXSIZE 1024        //定义栈的空间大小
typedef struct stack{
  int data[MAXSIZE];    
  int top;
}Stack;

2.初始化

Stack *Init(){
    Stack stack;
    stack = (Stack*)malloc(sizeof(Stack));
    if(!stack){
        printf("Memory allocation failed!");
        return NULL;
    }
    else{
        stack->top = -1;    //C语言数组下标从0开始
        printf("Init successfully!");
        return stack;
    }
}

3.判断栈是否为空

int isEmpty(Stack* stack){
    if(stack->top == -1){
        printf("The stack is empty!");
        return 1;
    }
    return 0;
}

4.判断栈是否满

int isFull(Stack* stack){
    if(stack->top == MAXSIZE-1){
        printf("The satck is full!");
        return 1;
    }
    return 0;
}

5.进栈操作（Push）

void Push(Stack* stack,int item){
    if(isFull(stack)){
        return;
    }
    stack->data[++stack->top] = item;
}

入站操作先移动Top，再压入元素

6.出栈操作（Pop）

int Pop(Stack* stack){
    if(isEmpty(stack)){
        return -99;
    }
    return stack->data[stack->top--];   //返回被弹出的元素
}

7.遍历操作

void Traverse(Stack* satck){
    printf("The items in the stack are:\n");
    for (int i=stack->top;i >= 0;i--){
        printf ("%d\n",stack->data[i]);
    }
}

链式栈

1.构建栈的结构

typedef struct node{
    int data;
    struct node* next;
}Node;

2.初始化栈

Node* Init(){
    Node* s;
    s = (Node*)malloc(sizeof(Node));
    if(!s){
        printf("Memory allocation failed!");
        return NULL;
    }
    else{
        printf("Init successfully!");
        s->next = NULL;
        return s;
    }
}

3.判断栈是否为空

int isEmpty(Node* s){
    return (s->next == NULL);
}

4.进栈操作

void Push(Node* s,int item){
    Node* node;     //为插入的元素构建一个节点
    node = (Node*)malloc(sizeof(Node));
    if(!node){
        printf("Memory allocation failed!");
        return NULL;
    }
    node->data = item;
    node->next = s->next;       //这里写成node->next = NULL应该也可以吧
    s->next = node;
}

5.出栈操作

int Pop(Node* s){
    Node* Top;
    int data;
    if(isEmpty(s)){
        printf("The stack is empty!");
        return -99;
    }
    Top = s->next;
    s->next = Top->next;
    data = Top->data;
    free(Top);
    return data;
}

6.遍历操作

void Traverse(Node* s){
    printf("The items in the stack are:\n");
    Node* p;
    p = s;
    while (p->next != NULL){
        printf("%d\n",p->data);
        p = p->next;
    }
}