一、简介

1.1 介绍

utstack.h中包含了一组动态stack宏。使用起来非常简单，只需要将utstack.h拷贝到你的项目，并包含进你的源码即可：

#include "utstack.h"

utstack.h宏支持栈的基本的操作：push、pop、count，以及获取顶部元素操作。其内部实现为连接的链表。

1.2 源码获取

utlist.h的源码可以在GitHub上直接获取(src/utstack.h)：

https://github.com/troydhanson/uthash

二、使用方法

2.1 栈头声明

栈头是一个结构体指针，指向你自己定义的结构体，注意必须初始化为NULL：

element *stack = NULL

2.2 栈操作

栈的操作只有O(1)的push，O(1)的pop和O(n)的count方法。

为了保证你代码的可读性，你可以使用STACK_EMPTY(head)替代head == NULL，使用STACK_TOP(head)替代head。

Operations	description
STACK_PUSH(stack,add);	push add onto stack
STACK_POP(stack,elt);	pop stack and save previous top as elt
STACK_COUNT(stack,tmp,count);	store number of elements into count
STACK_TOP(stack)	return stack
STACK_EMPTY(stack)	return stack == NULL

表格中用到的参数说明如下：

• stack：The stack head (a pointer to your element structure).
• add：A pointer to the element structure you are adding to the stack.
• elt：A pointer that will be assigned the address of the popped element. Need not be initialized.
• tmp：A pointer of the same type as elt. Used internally. Need not be initialized.
• count：An integer that will be assigned the size of the stack. Need not be initialized.

2.3 一个简单的实例

下面的实例读取文件内容，然后push每行到stack，然后pop取出数据后打印出来。

/* A stack of names*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "utstack.h"

#define BUFLEN 20

typedef struct el {
    char bname[BUFLEN];
    struct el *next;
} el;

el *head = NULL; /* important- initialize to NULL! */

int main(int argc, char *argv[]) {
    el *elt, *tmp;

    char linebuf[sizeof el->bname];
    int count;
    FILE *file = fopen("test11.dat", "r");
    if (file == NULL) {
        perror("can't open: ");
        exit(-1);
    }

    while (fgets(linebuf, sizeof linebuf, file) != NULL) {
        el *name = malloc(sizeof *name);
        if (name == NULL) exit(-1);
        strcpy(name->bname, linebuf);
        STACK_PUSH(head, name);
    }
    fclose(file);

    STACK_COUNT(head, elt, count);
    printf("%d elements were read into the stack\n", count);

    /* now pop, print, and delete each element */
    while (!STACK_EMPTY(head)) {
        printf("%s\n", STACK_TOP(head)->bname);
        STACK_POP(head, elt);
        free(elt);
    }

    return 0;
}

2.4 其他宏

当你的结构体的next字段命名不是next，那么你可能会用到如下宏：

Operations	description
STACK_PUSH2(stack,add,next);	push add onto stack
STACK_POP2(stack,elt,next);	pop stack and save previous top as elt
STACK_COUNT2(stack,tmp,count,next);	store number of elements into count