本文共 1996 字，大约阅读时间需要 6 分钟。

随手练下基本的数据结构，基于链表实现一个动态大小的栈和队列，最基本简单的数据结构要注意各种边界场景。基于链表实现，频繁增删调用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);    }}

转载地址：http://vfqli.baihongyu.com/