栈

栈是一种先进后出的线性数据结构，规定只允许在一端进行插入和删除元素的操作。其中进栈操作又叫做压栈（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;
  }
}