栈

前言

栈在程序中经常使用，比如创建了一个函数，创建的这个函数会压入栈中，然后执行完成后会从栈中弹出。

还有就是在freeRTOS中，我们创建任务的时候，也会将任务压入栈中，然后执行完成后会从栈中弹出。

栈是一个比较重要的一个数据结构，好好学习对我们开发有很大的帮助。

一、逻辑结构

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二、存储结构

我们可以使用顺序表来实现，也可以使用链表来实现，这里两种方式都实现一下。

1.顺序表

1.1 数据结构

这里使用线性表来实现，其实本质上也是创建一个数组来进行存放，然后定义两个变量，一个变量指向栈底，另一个指向栈顶。

typedef struct {
    data_t* data;
    int len;
    int top;
}stackList, *stackLink;

data是栈的存放空间，这里使用一个指针来进行存放，这样可以动态的开辟栈的空间。

len是栈的长度，top是栈顶。

使用这个数据结构创建栈的话需要进行两次开辟空间，第一次是创建栈的头节点，第二次是创建栈中的数组。

1.2 函数实现

需要使用的函数如下：

stackLink Stack_Init(int len);          // 初始化栈
Status Stack_Push(stackLink stack, int value);   // 压入数据
data_t Stack_Pop(stackLink stack);               // 弹出数据
Status Stack_Emple(stackLink stack);             // 判断栈是否为空
Status Stack_Free(stackLink* stack);              // 释放栈
data_t Stack_Get_Top(stackList stack);             // 获取栈顶的值
Status Stack_Pull(stackLink stack);     // 判断栈是否满

相应的一些宏或者数据说明如下：

#define OK 1
#define ERROR (-1)
#define IS_NULL 1
#define NOT_NULL 0
#define IS_FULL 1
#define NOT_FULL 0
typedef int data_t;
typedef int Status;

1.2.1 初始化栈

初始化栈的话，需要进行两次开辟空间，第一次是创建栈的头节点，第二次是创建栈中的数组。

stackLink Stack_Init(int len)          // 初始化栈
{
    stackLink stack = NULL;
    stack = (stackLink)malloc(sizeof(stackList));
    if (stack == NULL)
    {
        return NULL;
    }
    stack->len = len;
    stack->top = -1;
    stack->data = (data_t*)malloc(sizeof(data_t) * stack->len);
    if (stack->data == NULL)
    {
        return NULL;
    }
    return stack;
}

这里开辟队列的空间长度使用的是参数传递进来的，这样可以实现动态开辟空间。

然后top指针的值为-1的主要目的是表明这个栈为空，当然你也可以让它为0。

1.2.2 压入数据

压入数据的话，需要判断栈是否满，如果满的话就不能压入数据了。

对于新直接的数据要先对top指针进行自增，自增完成后把需要压入栈的数据放入到top指向的位置。

Status Stack_Push(stackLink stack, int value)   // 压入数据
{
    if (stack->top >= stack->len)
    {
        return ERROR;
    }
    stack->top++;
    stack->data[stack->top] = value;

    return OK;
}

判断栈顶的大小是否大于等于栈的长度，如果大于等于的话就说明栈满了，不能压入数据了。

1.2.3 弹出数据

弹出数据的话，需要判断栈是否为空，如果为空的话就不能弹出数据了。

在读取完数据后需要将top指针进行自减，这样就指向下一个元素的位置。

data_t Stack_Pop(stackLink stack)               // 弹出数据
{
    if (stack->top == -1)
    {
        return -1;
    }
    return stack->data[stack->top];
    stack->top--;
}

如果前面的初始化是从0开始，并且top指针是先存放然后再自增的话，那这里的顺序就得改变一下，需要先对指针进行自减到需要弹出数据的位置，然后再返回数据：

data_t Stack_Pop(stackLink stack)               // 弹出数据
{
    if (stack->top == 0)
    {
        return -1;
    }
    stack->top--;
    return stack->data[stack->top];
}

1.2.4 判断栈是否为空

判断栈是否为空的话，只需要判断top指针的值是否为-1，如果为-1的话就说明栈为空。

Status Stack_Emple(stackLink stack)             // 判断栈是否为空
{
    if (stack == NULL || stack->data == NULL)
    {
        return ERROR;
    }
    return (stack->top == -1 ? 1 : 0);
}

1.2.5 释放栈

释放栈的话，需要释放栈中的数组和栈的头节点。

需要释放两次，先释放数组，再释放头节点。

Status Stack_Free(stackLink* stack)              // 释放栈
{
    if ((*stack)->data != NULL)
    {
        free((*stack)->data);
    }
    free((*stack));
    (*stack) = NULL;
    return OK;
}

1.2.6 获取栈顶的值

获取栈顶的值的话，只需要返回top指针指向的位置的值即可。

data_t Stack_Get_Top(stackList stack)
{
    return stack.data[stack.top];
}

1.2.7 判断栈是否满

判断栈是否满的话，只需要判断top指针的值是否等于栈的长度，如果等于的话就说明栈满了。

Status Stack_Pull(stackLink stack)
{
    return stack->top == stack->len - 1 ? IS_FULL : NOT_FULL;
}

这样就将顺序栈实现了，下面就是使用链式栈，但链式栈不是很实用，因为链式栈的入栈和出栈都需要遍历一遍栈才可以，当然可以通过双向链表来实现，操作起来比较麻烦。

2.链式栈

这里使用的是双向链表，上面我们了解到栈的实现，其实就是先进后出，前面的顺序栈很简单，通过下标就可以操作，但是对于链式的结构来说，你没办法通过下标来查找出栈的下一个元素，所以这里使用的是双向链表，当前面那个元素出栈后可以通过出栈的那个元素找到它的上一个结点。

可以看到下图就是个双向链表的示意图：

head是作为头节点使用的，head的next指向的是栈顶元素，head的prev指向的是栈底元素。

2.1 数据结构

这里使用的是双向链表来实现，通过上图的解释可以知道，这个结点有两个指针和一个数据域。

typedef struct node {
    data_t data;
    struct node* next;
    struct node* prev; 
}node, *stackLink;

data是数据域，next是指向下一个结点的指针，prev是指向上一个结点的指针。

使用这个数据结构创建栈的话需要进行一次开辟空间，开辟空间的大小就是栈的大小。

2.2 函数实现

需要使用的函数如下：

stackLink Stack_Init();          // 初始化栈
Status Stack_Push(stackLink stack, data_t value);   // 压入数据
data_t Stack_Pop(stackLink stack);               // 弹出数据
Status Stack_Emple(stackLink stack);             // 判断栈是否为空
Status Stack_Free(stackLink* stack);              // 释放栈
data_t Stack_Get_Top(stackList stack);             // 获取栈顶的值

2.2.1 初始化栈

初始化栈的话，需要创建两个结点，第一个结点是栈头，第二个结点相当于是待入栈的结点。

stackLink Stack_Init()
{
    stackLink stack = NULL;
    stackLink next = NULL;
    stack = (stackLink)malloc(sizeof(node));
    if (stack == NULL)
    {
        return NULL;
    }
    stack->data = -1;
    next = (stackLink)malloc(sizeof(node));
    if (next == NULL)
    {
        return NULL;
    }
    next->data = -1;
    next->next = NULL;
    next->prev = NULL;
    stack->next = next;
    stack->prev = next;
    return stack;
}

2.2.2 压入数据

压入数据的话，因为前面是创建了一个额外的结点，那这里的话是先将数据放到这个额外的结点上，然后再开辟一块空间。

Status Stack_Push(stackLink stack, data_t value)
{
    stackLink next = NULL;
    next = (stackLink)malloc(sizeof(node));
    if (next == NULL)
    {
        return ERROR;
    }
    stack->next->data = value;
    next->next = NULL;
    next->prev = stack->next;
    next->data = -1;
    stack->next = next;
    return OK;
}

2.2.3 弹出数据

弹出数据实现需要先释放头结点的next指向的结点，然后往前移动一个结点，再读取出这个结点的data。

data_t Stack_Pop(stackLink stack)
{
    stackLink temp = NULL;
    data_t data = -1;
    if (stack->next == stack->prev)
    {
        // 空栈
        return -1;
    }
    temp = stack->next;
    stack->next = temp->prev;
    stack->next->next = NULL;
    free(temp);
    data = stack->next->data;
    return data;
}

2.2.4 判断栈是否为空

判断栈是否为空的话，只需要判断头结点的next和prev是否相等，如果相等的话就说明栈为空。

Status Stack_Emple(stackLink stack)
{
    return stack->next == stack->prev? IS_NULL : NOT_NULL;
}

2.2.5 释放栈

释放栈的话，需要释放头结点和头结点的next指向的结点。

Status Stack_Free(stackLink* stack)
{
    stackLink temp = NULL;
    temp = (*stack)->next;
    free((*stack)); 
}

2.2.6 获取栈顶的值

获取栈顶的值的话，只需要返回头结点的next指向的结点的数据即可。

data_t Stack_Get_Top(stackLink stack)
{
    return stack->next->data;
}

三、总结

栈的实现比较简单，但是栈的应用比较广泛，比如在函数调用的时候，函数的返回地址、参数、局部变量等都需要压入栈中，在函数返回的时候需要从栈中弹出。

栈的应用还有很多，比如在编译器中，编译器会将中缀表达式转换为后缀表达式，然后再进行计算。

对于链式栈的使用比较少，一般都是使用顺序栈，所以链式栈作为一个提高内容就可以了。