随手练下基本的数据结构，基于链表实现一个动态大小的栈和队列，最基本简单的数据结构要注意各种边界场景。基于链表实现，频繁增删调用mallc会带来一定开销，实际使用要看情况来定。

基于链表的栈

typedef struct _node { int data; struct _node* next; }node; typedef struct _stack { node *top; node *bottom; size_t num; }stack; void init(stack *s) { s->top = NULL; s->bottom = NULL; s->num = 0; } int is_empty(stack *s) { return s->num == 0; } int top(stack *s) { if (!is_empty(s)) { return s->top->data; } else { printf("run top fail, stack is empty!\n"); return 0; } } void pop(stack *s) { node *tmp; if (!is_empty(s)) { tmp = s->top; s->top = tmp->next; free(tmp); s->num--; if (is_empty(s)) { s->bottom = NULL; } } else { printf("run pop fail, stack is empty!\n"); } } void push(stack *s, int data) { node *pdata = (node *)malloc(sizeof(node)); pdata->data = data; if (is_empty(s)) { s->top = pdata; s->bottom = pdata; pdata->next = NULL; } else { pdata->next = s->top; s->top = pdata; } s->num++; } void clear_stack(stack *s) { while (!is_empty(s)) { pop(s); } }

基于链表的队列

typedef struct _node { int data; struct _node* next; }node; typedef struct _queue { node *front; node *rear; size_t num; }queue; int is_empty(queue *q) { return q->num == 0; } void push(queue *q, int val) { node *pnode = (node*)malloc(sizeof(node)); pnode->data = val; pnode->next = NULL; if (q->rear) { q->rear->next = pnode; } else { q->front = pnode; } q->rear = pnode; q->num++; } void pop(queue *q) { if (!is_empty(q)) { node *pnode = q->front; q->front = q->front->next; free(pnode); q->num--; if (is_empty(q)) { q->rear = NULL; } } else { printf("error: pop the empty queue!"); } } void init(queue *q) { q->front = NULL; q->rear = NULL; q->num = 0; } void clear_queue(queue *q) { while (!is_empty(q)) { pop(q); } }