链表在memcached、redis中作为核心数据结构出现。相比数组，链表能动态增减容量，就比数组要灵活，并且hash表结构一般都使用链表进行数据存储

完整案例代码已上传github: https://github.com/neatlife-learn/mydatastructure

队列

元素结构

对应代码如下

typedef struct _element {
    struct _element *previous;
    struct _element *next;
    void *value;
} element;

队列结构

一个队列中包含多个元素，为了能够方便的得到这个队列头和尾，以及队列里的元素个数，使用这个queue结构来存放这些信息

对应代码如下

typedef struct _queue {
    element *head;
    element *end;
    size_t size;
} queue;

新建队列

queue* new_queue(void *value)
{
    element *item = (element *) malloc(sizeof(element));
    item->value = value;
    item->previous = NULL;
    item->next = NULL;
    
    queue *a_queue = (queue *) malloc(sizeof(queue));
    a_queue->head = item;
    a_queue->end = item;
    a_queue->size = 1;
    return a_queue;
}

1. 为元素分配内存空间，并得到指向这个元素内存空间的指针
2. 为队列分配内存空间，并把队列头、尾指针指向上面创建的元素，因为这个队列里初始化的时候只有这一个元素
3. 把队列大小设置为1

进队列

void push(queue *a_queue, void *value)
{
    element *item = (element *) malloc(sizeof(element));
    item->value = value;
    
    item->previous = a_queue->end;
    item->next = NULL;
    
    a_queue->end->next = item;
    a_queue->end = item;
    a_queue->size = a_queue->size + 1;
}

队列的特性是先进先出，一般出的时候都是拿链表的最后一个元素，进的时候就把新元素加到链表尾

1. 创建新元素，并把这个元素的next置为NULL
2. 把新元素挂到链表尾
3. 队列中的元素数量+1

出队列

element* pop(queue *a_queue)
{
    element *item = a_queue->end;
    
    a_queue->end = a_queue->end->previous;
    item->previous = NULL;
    a_queue->end->next = NULL;
    
    a_queue->size = a_queue->size - 1;
    
    return item;
}

1. 取出队列的最后一个元素
2. 队列的最后一个元素变成了倒数第二个元素
3. 短掉取出的元素和队列的关系
4. 队列中的元素数量-1

获取队列状态

void stats(queue *a_queue)
{
    cout << "current queue size: " << a_queue->size << endl;
    
    cout << "current queue content: " << endl;
    element *item = a_queue->head;
    while (item) {
        cout << (size_t) item->value << endl;
        item = item->next;
    }
}

测试脚本

queue* a_queue = new_queue((size_t *) 1)
push(a_queue, (size_t *) 2);

stats(a_queue);
element *item = pop(a_queue);
stats(a_queue);
cout << (size_t)item->value << endl;

效果如下：

可以看到出队列是从队列尾部出的

异常处理

出队列时可对a_queue->size进行判断，如果size等于0了，表示队列中已经没有数据了，就不能再执行出队列操作了

当出队列出到a_queue->size等于0时，需要清空队列的end、previous指针

栈

栈和队列除了出栈操作不一样，其它部分完全一致，队列出队列的时候从尾部出，栈出栈的时候从头部出，核心代码如下

element* pop(stack *a_stack)
{
    element *item = a_stack->head;
    
    a_stack->head = a_stack->head->next;
    item->next = NULL;
    a_stack->head->previous = NULL;
    
    a_stack->size = a_stack->size - 1;
    
    return item;
}

时间复杂度

出栈、入栈都是只需操作链表的头和尾指针，时间复杂度为1

一些注意的点

cpp指针初始化需要明确设置为NULL

参考资料

1. https://www.zhihu.com/question/24773728