数据结构与算法篇-栈

01

—

顺序栈

栈是一种后进先出的数据结构，栈的实现方式主要有2种，顺序栈和链栈。顺序栈则是栈的元素虚拟内存地址是连续的，链栈则是栈元素虚拟地址非连续的。在C语言里数组的元素虚拟地址是连续的但是数组大小必须在编译的时候确定，用于实现栈不够灵活。而在C语言里调用malloc申请到的一块内存虚拟地址是连续的，而且大小在运行期间确定，比较符合我们灵活的实现顺序栈的需求。先来看一下顺序栈的定义和函数声明。

#define NAN (0xFFFFFFFE)

typedef struct stack{
    int size;
    int cap;
    int front;
    int *arr;
}_stack_t;

extern void stack_init(_stack_t *s, int capacity); //初始化栈
extern void stack_push(_stack_t *s, int data); //入栈
extern int stack_pop(_stack_t *s); //出栈
extern int stack_size(_stack_t *s); //获取栈大小
extern bool stack_is_empty(_stack_t *s); //判断栈是否为空
extern bool stack_is_full(_stack_t *s); //判断栈是否满
extern void stack_destroy(_stack_t *s); //销毁栈

这里我们自定义了一个_stack_t类型，size是栈大小，cap是栈容量，front是栈顶，arr指针指向一块存储数据的内存，我们还通过宏定义了一个NAN值表示非法值。

• 栈初始化
  

函数实现如下：

void stack_init(_stack_t *s, int capacity){
    if(s == NULL || capacity <= 0){
        return;
    }

    s->arr = (int *)malloc(capacity * sizeof(int));
    s->front = 0;
    s->size = 0;
    s->cap = capacity;
}

这里我们申请了一块内存用于存储数据，并保存栈容量大小。

• 入栈
  

函数实现如下：

void stack_push(_stack_t *s, int data){
    if(s == NULL){
        return;
    }
    if(stack_is_full(s)){
        return;
    }
    s->size ; //栈使用大小增1
    s->arr[s->front ] = data; //保存数据后栈顶指针往后移
}

由于栈容量有限，每次将数据压入栈之前先判断一下栈是否满，栈未满才能继续往里压入数据。

• 出栈
  

每次出栈是后面入栈的数据先出，前面入栈的数据后出。函数实现如下：

int stack_pop(_stack_t *s){
    if(s == NULL){
        return NAN;
    }
    //判断栈是否空
    if(stack_is_empty(s)){
        return NAN;
    }
    s->size--; //栈使用量减1
    return s->arr[--s->front]; //先递减栈顶指针，获取栈顶数据
}

栈为空时说明栈里没有数据则返回一个非法值，否则获取栈顶数据并返回。

• 获取栈大小

函数实现如下：

int stack_size(_stack_t *s){
    if(s == NULL){
        return 0;
    }
    return s->size;
}

• 判断栈是否为空
  

函数实现如下：

bool stack_is_empty(_stack_t *s){
    if(s == NULL){
        return true;
    }
    return s->size > 0 ? false : true;
}

• 判断栈是否满
  

函数实现如下：

bool stack_is_full(_stack_t *s){
    if(s == NULL){
        return false;
    }
    return s->size == s->cap ? true : false;
}

• 销毁栈

函数实现如下：

void stack_destroy(_stack_t *s){
    if(s == NULL){
        return;
    }
    if(s->arr){
        free(s->arr);
    }
    s->arr = NULL;
    s->cap = 0;
    s->size = 0;
    s->front = 0;
}

销毁栈操作主要是释放内存，并初始化成员变量。

02—

链栈

在前面的文章中我们讲解了单链表，在文中我们采用头插法插入结点到链表，由于头插法每次将最新的数据插入到链表头，如果依次遍历链表获取链表结点的数据，就是标准的栈弹出数据的操作。现在我们用前面文章实现的单链表实现一个链栈，顾名思义链栈就是用链式数据结构实现栈。我们自定义一个栈数据类型并声明一些操作函数。

typedef list_t stack_linked_t; //自定义栈数据类型

extern stack_linked_t *new_stack_linked_node(int data); //新建一个栈结点
extern void stack_linked_push(stack_linked_t **s, int data); //入栈
extern int stack_linked_pop(stack_linked_t **s); //出栈
extern int stack_linked_size(stack_linked_t *s); //获取栈大小
extern bool stack_linked_is_empty(stack_linked_t *s); //判断栈是否为空
extern void stack_linked_destroy(stack_linked_t **s); //销毁栈

这里我们将list_t自定义成stack_linked_t，看似多此一举，实际上更直观了，我们虽然使用链表实现栈，但是如果将数据类型声明为list_t反而更迷惑。由于链栈是链式结构不存在栈是否满的情况，除非已经无法申请到内存。

• 新建栈结点
  

函数实现如下：
stack_linked_t *new_stack_linked_node(int data){
    return new_list_node(data);
}

这里我们直接对新建链表结点函数进行封装，后面我们也会大量用到链表操作函数，差不多都是类似的封装。

• 入栈
  
  

函数实现如下：
void stack_linked_push(stack_linked_t **s, int data){
    //这里一定要注意分开两个if，因为或运算符的特性
    if(s == NULL){
        return;
    }
    if(*s == NULL){
        return;
    }
    //采用头插法插入链表
    *s = list_add(*s, data);
}

这里重点注意由于我们传入的是一个二级指针if(s == NULL)和if(*s == NULL)一定要分开处理，不能使用||运算进行处理，因为||运算符会执行第二个判断，如果s == NULL成立那么在执行第二个判断时由于使用了空指针程序会奔溃。

• 出栈
  

为了获取链表头结点，我们定义了一个获取链表头结点函数，函数实现如下：
list_t *get_list_head(list_t **list){
    if(list == NULL){
        return NULL;
    }
    if(*list == NULL){
        return NULL;
    }

    list_t *head = *list;
    //链表只有一个结点
    if((*list)->next == NULL){
        *list = NULL;
        return head;
    }

    //链表长度大于1则保存头结点，新头结点是原头结点的下一个结点
    *list = (*list)->next;
    head->next = NULL; //原头结点一定要将next指针置为NULL
    return head;
}

出栈函数实现如下：
int stack_linked_pop(stack_linked_t **s){
    //这里一定要注意分开两个if，因为或运算符的特性
    if(s == NULL){
        return NAN;
    }
    if(*s == NULL){
        return NAN;
    }

    stack_linked_t *stack_node = get_list_head(s);
    int data = stack_node->data;
    free(stack_node);
    return data;
}

获取链表头结点数据并释放内存。

• 获取栈大小
  

获取栈大小其实就是获取链表长度，因此我们定义了一个获取链表长度函数，函数实现如下：

//获取链表长度
int list_length(list_t *list){
    if(list == NULL){
        return 0;
    }

    int length = 0;
    while(list != NULL){
        length ;
        list = list->next;
    }
    return length;
}

获取栈大小实现函数如下：

int stack_linked_size(stack_linked_t *s){
    if(s == NULL){
        return 0;
    }

    return list_length(s);
}

• 判断栈是否为空

函数实现如下：

bool stack_linked_is_empty(stack_linked_t *s){
    if(s == NULL){
        return true;
    }

    return list_length(s) > 0 ? false : true;
}

链表长度为0则链表为空，非0则有数据。

• 销毁栈

函数实现如下：
void stack_linked_destroy(stack_linked_t **s){
    if(s == NULL){
        return;
    }
    if(*s == NULL){
        return;
    }

    list_destroy(*s);
    *s = NULL;
}

03

—

验证测试

最后我们写一个小程序验证一下我们实现的栈是否正确，代码如下：

#include 
#include "stack.h"

int main() {
    _stack_t my_stack;
    int i = 0;

    stack_init(