栈

  • 后进先出

笔记1_1.png
stack.h 文件

  1. #ifndef __STACK_H
  2. #define __STACK_H
  4. typedef struct {
  5.     int *arr;
  6.     int cap;
  7.     int top;
  8. }stack_t;
  10. extern void stack_init(stack_t *stack, int cap);
  11. extern void stack_destroy(stack_t *stack);
  12. extern int stack_full(stack_t *stack);
  13. extern int stack_empty(stack_t *stack);
  14. extern int stack_push(stack_t *stack, int data);
  16. #endif

stack.c文件

  1. #include <stdlib.h>
  3. #include "stack.h"
  5. typedef struct {
  6.     int *arr;
  7.     int cap;
  8.     int top;
  9. }stack_t;
  11. // stack_init 初始化栈
  12. void stack_init(stack_t *stack, int cap)
  13. {
  14.      stack->arr = (int *)malloc(cap * sizeof(int));
  15.     stack->cap = cap;
  16.     stack->top = 0;
  17. }
  19. // stack_destroy 释放内存
  20. void stack_destroy(stack_t *stack) 
  21. {
  22.      free(stack->arr);   
  23.     stack->cap = 0;
  24.     stack->top = 0;
  25. }
  27. // stack_full 检测栈是否已满 1 已满 0未满
  28. int stack_full(stack_t *stack) 
  29. {
  30.     return stack->top >= stack->cap;
  31. }
  33. // stack_empty 检测栈是否已满
  34. int stack_empty(stack_t *stack)
  35. {
  36.     return !stack->top;
  37. }
  39. // stack_push 压栈, return 压栈成功 0， 失败 1
  40. int stack_push(stack_t *stack, int data)
  41. {
  42.      if (stack_full(stack))
  43.         return 0;
  44.     stack->arr[top++] = data;
  45.     return 1;
  46. }

main.c文件

  1. #include <stdio.h>
  2. #include "stack.h"
  4. // stack_pop 出栈, 出栈成功 err=0 否则 err = 1
  5. int stack_pop(stack_t *stack， int *err)
  6. {
  7.     if(stack_empty(stack)){
  8.         *err = 1;
  9.         return 0;
  10.     }
  11.     *err = 0;
  12.     return stack->arr[--top];
  13. }

队列

  • 先进先出

单链表

  • 内存不lian

image.png

双链表

二叉树

查找算法

排序算法