链表、二叉树、栈、队列的实现

目录

• 1.链表

链表

1. 链表定义

struct ListNode{
    int val;
    struct ListNode *next;
};
typedef struct ListNode node;

2.创建链表（尾插法）

int n = 4;

ListNode* head = new ListNode();
ListNode* t = head;

for (int i=0; i<n; i++) {
    int a = 0;
    cin>>a;
    ListNode* p = new ListNode(a);
    t->next = p;
    t = p;
}
head = head->next;

二叉树

typedef struct{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode;

栈

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

Stack* createStack(){
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->top = -1;
    return s;
}
bool isEmpty(Stack* s){
    return s->top == -1;
}
void push(Stack *s, int item){
    s->data[++(s->top)] = item;
}
int pop(Stack *s){
    if (isEmpty(s)) {
        return INT_MIN;
    }
    return s->data[(s->top)--];
}

队列

typedef struct{
    int data[MaxSize];
    int front;
    int rear;
    int size;
    int capacity;
} Queue;

Queue* createQueue(){
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->size = 0;
    q->capacity = MaxSize;
    q->front = 0; // 指向队头
    q->rear = q->capacity-1 ; // 指向队尾
    
    return q;
}
bool isEmpty(Queue* q){
    return q->size==0;
}

void enqueue(Queue* q, int val){
    q->rear = (q->rear + 1) % q->capacity;
    q->data[q->rear] = val;
    q->size++;
}
int dequeue(Queue* q){
    if (isEmpty(q)) {
        return INT_MIN;
    }
    int val = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return val;
}