6.数据结构之通用栈（链表实现）

╰+攻爆jí腚メ 2022-08-09 11:55 235阅读 0赞

# 数据结构之通用栈（链表实现） #

## 栈简介 ##

栈是一种特殊的一维线性数据结构，它满足的特点是FILO（先进后出），这样一种操作顺序在日常的生活中比比皆是。比如我们厨房里放置盘子和取盘子，最先放置的盘子一定是放在较底下的地方，要取得其中一个盘子也要先把其上边的盘子拿走先。在计算机中也是满足这样的关系，比如说我们的函数调用就满足着栈的关系。  
![这里写图片描述][20151022161231905]

可以看到主函数调用时，在栈区对主函数main的栈桢进行了圧栈，随后的函数调用func\_1、fun\_2等函数也依次进行了圧栈，等函数运行结束后还会逆序地进行出栈。

所以说栈的调用在计算机和日常生活中非常的常见，我们形象的把满足如下关系的数据结构叫做栈：  
![这里写图片描述][20151022161845844]

## 栈的功能 ##

**栈的功能是什么？**

栈最大的功能就是**记忆**！不管是函数调用的恢复，还是算法里状态的回溯，还是只能手机视图层级的切换，无一不是利用了栈的记忆特性，在后续数据结构二叉树的讲解中，我们也会看到关于栈的大量使用。

## 栈的实现 ##

关于栈的实现我们采用了两种不同的方式，因为栈归根结底是一种一维线性的数据结构，只要给予一维线性数据结构相关操作的约束就可达到目标。我们这里采用对**通用双端链表**和**通用动态数组**两种数据结构的封装，从而实现通用栈。本篇文章首先介绍给大家**如何使用通用双端链表封装通用栈**。

stack实现的文件包含如下：  
![这里写图片描述][20151022163603179]

首先我们给出通用栈的结构设计和接口声明，该内容在stack.h文件中：

//通用栈的结构设计和接口声明
    #ifndef _STACK_H_
    #define _STACK_H_
    
    #include "dlist.h"
    #include "tools.h"
    
    typedef struct Stack{
        Dlist *dlist;    //用双端链表的控制信息去模仿栈的控制信息
    }Stack;
    
    
    //关于栈的接口
    Stack   *init_stack(void)                        ;    //初始化栈
    void    destroy_stack(Stack **stack)             ;    //销毁栈
    Boolean is_stack_empty(Stack *stack)             ;    //判空
    void    push(Stack *stack, void *value)          ;    //入栈
    Boolean pop(Stack *stack)                        ;    //出栈
    Boolean get_top(Stack *stack, void **value)      ;    //得到栈顶元素
    int     get_stack_count(Stack *stack)            ;    //得到栈的个数
    
    #endif

我们虽然定义了栈对数据结构，但是其中只是对通用双端链表的控制信息尽心了简单的封装。剩下的部分就是对于栈的接口声明，后续我们要实现栈的接口:

//栈的接口实现
    #include "stack.h"
    
    //栈的接口实现
    Stack   *init_stack(void)    //初始化栈
    {
        Stack *stack = (Stack *)Malloc(sizeof(Stack));
        stack->dlist = (Dlist *)malloc(sizeof(Dlist));
        if(stack->dlist == NULL){
            free(stack);
            fprintf(stderr, "the memory is full!\n");
            exit(1);
        }
        return stack;
    }
    
    void    destroy_stack(Stack **stack)    //销毁栈
    {
        if(stack == NULL || *stack == NULL){
           return ;
        }
    
        //先释放stack里的dlist，再释放stack
        destroy_dlist(&((*stack)->dlist));
        free(*stack);
        *stack = NULL;
    }
    Boolean is_stack_empty(Stack *stack)    //判空
    {
        return get_stack_count(stack) == ZERO;
    }
    
    void    push(Stack *stack, void *value)    //入栈
    {
        if(stack == NULL || value == NULL){ 
            return ;
        }
        push_front(stack->dlist, value);    //入栈操作封装了双端链表的头部插入
    }
    
    Boolean pop(Stack *stack)    //出栈
    {
        if(stack == NULL || is_stack_empty(stack)){
            return FALSE;
        }
        return pop_front(stack->dlist);
    }
    
    Boolean get_top(Stack *stack, void **value)    //得到栈顶元素
    {
        if(stack == NULL || is_stack_empty(stack)){
            return FALSE;
        }
        if(value != NULL){
            get_front(stack->dlist, value);
        }
        return TRUE;
    }
    
    int     get_stack_count(Stack *stack)    //得到栈的个数
    {
        if(stack == NULL){
            return -1;
        }
        return get_dlist_count(stack->dlist);
    }

因为前边已经是实现了双端链表的各种操作，所以在对于栈的入栈（push）、出栈（pop）等操作可以直接对通用双端链表的操作进行封装即可。这个就体现了代码复用的优势。

接下来我们对栈的操作进行相关的测试:

//通用栈的接口测试
    #include "stack.h"
    
    int main(int argc, char **argv)
    {
        Stack *stack = NULL;
        int array[] = {
       12, 1, 3, 44, 222, 434, 553};
        int arr_len = sizeof(array) / sizeof(array[0]);
        int i = 0;
        int *value = NULL;
    
        stack = init_stack();   //栈的初始化
    
        for(i = 0; i < arr_len; ++i){
            push(stack, &array[i]);
        }
    
        for(i = 0; i < arr_len; ++i){
            get_top(stack, (void **)&value);
            pop(stack);
            printf("%d ", *value);
        }
        printf("\n");
    
        destroy_stack(&stack);    //栈的销毁
    
        return 0;
    }

关于上述使用的双端链表和工具文件分别存放在dlist.c、dlist.h以及tools.c、tools.h文件中。  
依次列出这四个文件的内容（因为前边已经做过相关的介绍，所以这里不再赘述）。  
dlist.h文件内容：

//通用双端链表的结构设计和接口声明
    //防止头文件的内容被重复包含
    #ifndef _DLIST_H_
    #define _DLIST_H_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <strings.h>
    
    #define ZERO (0)
    #define ONLY_ONE (1)
    #define TRUE (1)
    #define FALSE (0)
    
    struct Dlist;
    typedef struct Dlist Dlist;             //双端链表控制信息
    
    struct Dlist_node;
    typedef struct Dlist_node Dlist_node;   //双短链表节点信息
    
    typedef unsigned char Boolean;          //C语言中的布尔值
    
    //链表控制信息
    struct Dlist{   
        struct Dlist_node *head;   //指向双端链表的头节点
        struct Dlist_node *tail;   //指向双端链表的尾节点
        int               count;   //双端链表中的元素个数
    
        //释放链表节点数据域
        void    (*free)(void *ptr);    //void (*)(void *ptr) free;
        //匹配链表节点数据域
        Boolean (*match)(void *val1, void *val2);
        //拷贝链表节点数据域
        void    *(*copy_node)(void *src);
    };
    
    //链表节点信息
    struct Dlist_node{
        struct Dlist_node *prev;    //前一个节点指针
        struct Dlist_node *next;    //后一个节点指针
        void              *data;    //数据（指针）
    };
    
    
    
    typedef void (*Print_func)(void *value);
    //typedef void (*)(void *value) Print_func;
    
    //双端链表的接口(ADT)
    Dlist      *init_dlist(void)                    ;    //链表的初始化
    void       destroy_dlist(Dlist **dlist)         ;    //链表的销毁
    Boolean    push_front(Dlist *dlist, void *value);    //链表头部插入
    Boolean    push_back(Dlist *dlist, void *value) ;    //链表尾部插入
    Boolean    pop_back(Dlist *dlist)               ;    //链表尾部删除
    Boolean    pop_front(Dlist *dlist)              ;    //链表头部删除
    Boolean    insert_prev_node(Dlist *dlist,
                 Dlist_node *node, void *value)     ;    //插入指定节点的前边
    Boolean    insert_next_node(Dlist *dlist,
                 Dlist_node *node, void *value)     ;    //插入指定节点的后边
    Boolean    remove_dlist_node(Dlist *dlist,
                 Dlist_node *node, void **value)             ;    //删除链表中的节点 
    void       print_dlist(Dlist *dlist, Print_func print)   ;    //打印双端链表
    Dlist_node  *get_index_node(Dlist *dlist, int index)     ;    //得到下标为index的链表元素
    Boolean    get_front(Dlist *dlist, void **value)         ;    //得到链表头节点的数据域
    Boolean    get_tail(Dlist *dlist, void **value)          ;    //得到链表尾节点的数据域
    int        get_dlist_count(Dlist *dlist)                 ;    //得到链表元素个数
    
    
    //
    void print_int(void *value);    //打印整形值
    
    #endif

dlist.c文件的内容：

//通用双端链表的接口实现
    #include "dlist.h"
    #include "tools.h"
    
    
    void       destroy_dlist(Dlist **dlist)    //链表的销毁
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || *dlist == NULL){
            return ;
        }
    
        p_node = (*dlist)->head;
    
        while((*dlist)->head != NULL){
            (*dlist)->head = p_node->next;
            if((*dlist)->free != NULL){
                (*dlist)->free(p_node->data);
            }
            free(p_node);
            p_node = (*dlist)->head;
        }
        free(*dlist);
        *dlist = NULL;
    
    }
    
    static Dlist_node *buy_node(void)
    {
        Dlist_node *result = (Dlist_node *)Malloc(sizeof(Dlist_node));
        bzero(result, sizeof(Dlist_node));
    
        return result;
    }
    
    Boolean    push_front(Dlist *dlist, void *value)    //链表头部插入
    {
        Dlist_node *node = NULL;
    
        if(dlist == NULL || value == NULL){
            return FALSE;
        }
    
        node = buy_node();
        node->data = value;
    
        if(dlist->count == ZERO){    //链表没有元素时
            dlist->head = dlist->tail = node;
        }else{
            node->next = dlist->head;
            dlist->head->prev = node;
            dlist->head = node;
        }
        dlist->count++;
        return TRUE;
    }
    
    Boolean    push_back(Dlist *dlist, void *value)    //链表尾部插入
    {
        Dlist_node *node = NULL;
    
        if(dlist == NULL || value == NULL){
            return FALSE;
        }
    
        node = buy_node();
        node->data =value;
    
        if(dlist->count == ZERO){
            dlist->head = dlist->tail = node;
        }else{
            node->prev = dlist->tail;
            dlist->tail->next = node;
            dlist->tail = node;
        }
        dlist->count++;
        return TRUE;
    }
    Boolean    pop_back(Dlist *dlist)    //链表尾部删除
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || dlist->count == ZERO){
            return FALSE;
        }
    
        p_node = dlist->tail;
    
        if(dlist->count == ONLY_ONE){
            dlist->head = dlist->tail = NULL;
        }else{
            dlist->tail = p_node->prev;
            dlist->tail->next = NULL;
        } 
        if(dlist->free != NULL){
            dlist->free(p_node->data);
        }
        free(p_node);
        dlist->count--;
        return TRUE;
    }
    Boolean    pop_front(Dlist *dlist)    //链表头部删除
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || dlist->count == ZERO){
            return FALSE;
        }
    
        p_node = dlist->head;
    
        if(dlist->count == ONLY_ONE){
            dlist->head = dlist->tail = NULL;
        }else{
            dlist->head = p_node->next;
            dlist->head->prev = NULL;
        }
        if(dlist->free != NULL){
            dlist->free(p_node->data);
        }
        free(p_node);
        dlist->count--;
        return TRUE;
    }
    
    Dlist_node *get_index_node(Dlist *dlist, int index)   //得到下标为index的链表节点
    {
        Dlist_node *node = NULL;
        int move_count = 0;
    
        if(dlist == NULL || dlist->count == ZERO
        || index < ZERO || index >= dlist->count){
             return NULL;
        }
    
        node = dlist->head;
        move_count = index;
    
        //找到指定下标元素
        while(move_count--){
            node = node->next;
        }
    
        return node;
    }
    
    Boolean    remove_dlist_node(Dlist *dlist, 
                   Dlist_node *node, void **value)    //删除指定节点
    {
        if(dlist == NULL || node == NULL){
            return FALSE;
        }
    
        if(value != NULL){    //取得被删除节点数据域信息
            *value = node->data;
        }
    
        if(node->next == NULL){    //node在尾部
            pop_back(dlist);
        }else if(node->prev == NULL){
            pop_front(dlist);
        }else{
            node->prev->next = node->next;
            node->next->prev = node->prev;
            if(dlist->free != NULL){
                dlist->free(node->data); 
            }
            free(node);   //Free(node)
            dlist->count--;
    
            /* * * #define Free(node) (node->prev->next = node->next;) \ * (node->next->prev = node->prev;) \ * * * */
        }
        return TRUE;
    }
    
    Boolean    insert_next_node(Dlist *dlist,
                   Dlist_node *node, void *value)    //插入到指定节点的后边
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || node == NULL || value){
            return FALSE;
        }
    
        p_node = buy_node();
        p_node->data = value;
    
        p_node->prev = node;
        p_node->next = node->next;
        if(node->next == NULL){
            dlist->tail = p_node;
        }else{
            node->next->prev = p_node;
        }
        node->next = p_node;
        dlist->count++;
        return TRUE;
    }
    
    Boolean    insert_prev_node(Dlist *dlist,
                   Dlist_node *node, void *value)    //插入到指定节点的前边
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || node == NULL || value == NULL){
            return FALSE;
        }
    
        p_node = buy_node();
        p_node->data = value;
    
        //进行插入操作
        p_node->next = node;
        p_node->prev = node->prev;
        if(node->prev == NULL){    //node为第一个节点
            dlist->head = p_node;
        }else{    //node不是第一个节点
            node->prev->next = p_node;
        }
        node->prev = p_node;
        dlist->count++; 
        return TRUE;
    }
    
    void print_int(void *value)
    {
        printf("%d ", *(int *)value);
    }
    void print_dlist(Dlist *dlist, Print_func print)    //打印链表信息
    {
        Dlist_node *p_node = NULL;
    
        if(dlist == NULL || dlist->count == ZERO){
            return ;
        }
    
        for(p_node = dlist->head; p_node ; p_node = p_node->next){
            print(p_node->data);
        }
        printf("\n");
    }
    
    
    Dlist *init_dlist(void)    //双端链表的初始化
    {
        Dlist *dlist = NULL; 
    
        dlist = (Dlist *)Malloc(sizeof(Dlist));
        bzero(dlist, sizeof(Dlist));   //对dlist进行初始化
    
        return dlist;
    }
    
    Boolean get_front(Dlist *dlist, void **value)
    {
        if(dlist == NULL || dlist->count == ZERO){
            return FALSE;
        }
    
        if(value != NULL){
            *value = dlist->head->data;
        }
        return TRUE;
    }
    
    Boolean get_tail(Dlist *dlist, void **value)
    {
        if(dlist == NULL || dlist->count == ZERO){ 
            return FALSE;
        }
    
        if(value != NULL){
             *value = dlist->tail->data;
        }
        return TRUE;
    }
    
    int get_dlist_count(Dlist *dlist)
    {
        if(dlist == NULL){
            return -1;
        }
        return dlist->count;
    }

tools.h文件内容：

//工具类的接口声明
    #ifndef _TOOLS_H_
    #define _TOOLS_H_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    void *Malloc(size_t size)              ;   //申请堆空间
    void swap(void *a, void *b, int length);   //交换任意两个值
    #endif

tools.c文件内容

//工具类的接口实现
    #include "tools.h"
    
    void *Malloc(size_t size)
    {
        void *result = malloc(size);
        if(result == NULL){ 
            fprintf(stderr, "the memory is full!\n");
            exit(1);
        } 
        return result;
    }
    
    void swap(void *a, void *b, int length)
    {
        void *temp = malloc(length);
        memcpy(temp, a, length);
        memcpy(a, b, length);
        memcpy(b, temp, length);
    
        free(temp);
    }

小结：  
我们使用通用双端链表封装了通用栈，在下面的章节中我们将会采用通用动态数组实现通用栈，敬请期待！

[20151022161231905]: /images/20220731/c7ea37a4983549b1b00072e14a6b72f6.png
[20151022161845844]: /images/20220731/cbdc8fba502643929acf74f8272dda18.png
[20151022163603179]: /images/20220731/c17b3608d981471fa0e5c0da8fe26314.png