栈

栈结构：只允许从一端进行插入和删除数据的线性存储结构，成为栈结构。

数据插入和删除的这端成为栈顶，另一端成为栈底；
数据的插入称为入栈/压栈， 数据的删除称为出栈/弹栈。

特点：先进后出（FILO）

栈的应用：
解决回溯问题
撤销功能、网页撤销功能缓存
判断回文字符串，判断成对出现的符号有没有丢失

顺序栈：

满增栈、空增栈、满减栈、空减栈

满栈、空栈：根据所在位置是否存有元素确定
栈顶所在位置一直存有元素称为满栈。
栈顶所在位置一直没有元素称为空栈。

增栈、减栈：根据栈的生长方向确定。
入栈数据时，栈顶向内存高地址移动，称为增栈，
入栈数据时，栈顶向内存低地址移动，称为减栈

**链式栈：

API：

1. 创建栈
2. 入栈
3. 出栈
4. 判栈空
5. 获取栈顶元素
6. 清空栈（删除栈中的所有结点）
7. 销毁栈

stack.h中定义：

typedef int Data_t;

typedef struct node
{
    Data_t data;
    struct node *pnext;
}Node_t;


typedef struct stack
{
    Node_t *ptop;
    int clen;
}Stack_t;

创建链式栈：

Stack_t *create_stack()
{
    Stack_t *pstack = malloc(sizeof(Stack_t));
    if (NULL == pstack)
    {
        printf("malloc error\n");
        return NULL;
    }
    pstack->ptop = NULL;
    pstack->clen = 0;
	return pstack;
}

入栈：

int push_stack(Stack_t *pstack, Data_t data)
{
    Node_t *pnode = malloc(sizeof(Node_t));
    if (NULL == pnode)
    {
        printf("malloc error\n");
        return -1;
    }
    pnode->data = data;
    pnode->pnext = NULL;

pnode->pnext = pstack->ptop;
pstack->ptop = pnode;

pstack->clen++;

return 0;
}

出栈：

int pop_stack(Stack_t *pstack, Data_t *pdata)
{
    if (is_empty_stack(pstack))
    {
        return -1;
    }

Node_t *pfree = pstack->ptop;
pstack->ptop = pfree->pnext;
if (pdata != NULL)
{
    *pdata = pfree->data;
}
free(pfree);
pstack->clen--;

return 0;
}

判空：

int is_empty_stack(Stack_t *pstack)
{
    return NULL == pstack->ptop;
}
void clear_stack(Stack_t *pstack)
{
    while (!is_empty_stack(pstack))
    {
        pop_stack(pstack, NULL);
    }
}

打印：

void show_stack(Stack_t *pstack)
{
    Node_t *ptmp = pstack->ptop;
    while (ptmp)
    {
        printf("%d ", ptmp->data);
        ptmp = ptmp->pnext;
    }
    printf("\n");
}

获取栈顶元素：

int get_stack_top(Stack_t *pstack, Data_t *pdata)
{
    if (is_empty_stack(pstack))
    {
        return -1;
    }
    if (pdata != NULL)
    {
        *pdata = pstack->ptop->data;
        return 0;
    }
    return -1;
}

销毁：

void destroy_stack(Stack_t *pstack)
{
    clear_stack(pstack);
    free(pstack);
}

高频重难点 & 易错点

1. 栈只能在一端操作！不能随意访问中间元素

2. 顺序栈 top 初始值两种写法：
   top=-1（指向有效元素）【最常用】
   top=0（指向空闲位置），代码不要混用

3. 链式栈推荐头作栈顶，不要用尾部，否则遍历找到尾部开销大

4. 出栈和获取栈顶区别：

   pop：取出元素 + 删除栈顶
   gettop：只读取，不删除元素

5. 栈不支持随机访问，不能直接查找中间元素

6. 递归本质就是操作系统栈，递归深度过大 → 栈溢出

7.栈和队列核心区别

栈：LIFO 后进先出，同一端增删
队列：FIFO 先进先出，一端入、一端出