B站-4.线性结构应用之栈

线性结构的两种常见应用之一：栈、 定义：

一种可以实现“先进后出”的存储结构 栈类似于箱子：放书操作

分类：

静态栈:数组 动态栈:链表

算法：出栈、压栈 应用:

• 函数调用
• 中断
• 表达式求值
• 内存分配
• 缓存处理
• 迷宫

静态内存在栈里分配的 动态内存在堆里分配的

静态栈：数组

```
/*
顺序栈的基本运算的实现
*/
#include <stdio.h>
#include <stdlib.h>
# define MAXSIZE 100

typedef struct node
{
    int data[MAXSIZE];//数据元素
    int top;//栈顶位置
}stack;

stack* init_stack();
int isEmpty_stack(stack * pStack);
int push_stack(stack *pStack, int data);
int top_stack(stack *pStack);
int pop_stack(stack *pStack);

int main(void)
{
    stack *pStack = init_stack();

    printf("将1-50压入栈中\n");

    for (int i = 1; i <= 50; i++)
    {
        push_stack(pStack, i);
    }

    printf("读取栈顶元素：%d\n",top_stack(pStack));
    //移除50
    pop_stack(pStack);
    printf("移除50后读取栈顶元素：%d\n", top_stack(pStack));

    system("pause");
    return 0;
}

/*
初始化一个空栈
*/
stack* init_stack()
{
    //申请存储空间
    stack *pStack = (stack *)malloc(sizeof(stack *));
    //至栈顶标记为-1，表示空栈
    pStack->top = -1;

    return pStack;
}

/*
判断是否栈空，返回1表示是，0表示false
*/
int isEmpty_stack(stack * pStack)
{
    if (pStack->top == -1)
    {
        printf("栈空\n");
        return 1;
    }
    else
    {
        return 0;
    }
}

/*
将数据插入栈顶，成功返回1，失败返回0
*/
int push_stack(stack *pStack, int data)
{
    int top = pStack->top;
    top++;
    if (top == (MAXSIZE - 1))
    {
        printf("表满了\n");
        return 0;
    }
    pStack->data[top] = data;
    pStack->top++;
    return 1;
}

/*
读取栈顶元素
*/
int top_stack(stack *pStack)
{
    if (isEmpty_stack(pStack)!=1)
    {
        return pStack->data[pStack->top];
    }
    return -1;
}

/*
弹出栈顶元素
*/
int pop_stack(stack *pStack)
{
    if (isEmpty_stack(pStack) != -1)
    {
        int topData = pStack->data[pStack->top];
        pStack->top--;
        return topData;
    }
    return -1;
}

```

动态栈:链表

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
typedef struct Node{
    int data;
    struct Node *pNext;
}NODE,*PNODE;

typedef struct Stack{
    PNODE pTop;//顶部
    PNODE pBottom;//底部
//pBottom指向第一个有效元素的下一个元素(无用的头结点)，便于操作
}STACK,*PSTACK;//PSTACK = struct Stack *

void initStack(PSTACK S);//创建栈
void pushStack(PSTACK S,int val);//push数据
void traverse(PSTACK S);//遍历
bool pop(PSTACK S,int *val);//出栈
void clear(PSTACK pS);//清空栈
bool empty(PSTACK pS);//判断栈是否为空

int main()
{
    int val;
    STACK S;//Stack == struct Stack;
    initStack(&S);//初始化
    pushStack(&S,1);//压栈1
    pushStack(&S,2);//压栈2
    pushStack(&S,3);//压栈3
    traverse(&S);//遍历
   if( pop(&S,&val) )//出栈一次
   {
       printf("出栈成功，出栈的元素是%d\n",val);
   }else{
    printf("出栈失败！\n");
   }
    traverse(&S);//遍历
/*  clear(&S);//清空栈
    traverse(&S);//遍历*/
    return 0;
}

//将栈清空
void clear(PSTACK pS){
    if(empty(pS)){
        return;
    }else{
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while(p!=pS->pBottom){
            q = p->pNext;
            free(p);
            p=q;
        }
        pS->pTop = pS->pBottom;
    }
}

bool empty(PSTACK pS){
    if(pS->pTop==pS->pBottom){
        return true;
    }else{
        return false;
    }
}
//pS所指向的栈出栈一次
bool pop(PSTACK pS,int *val){
    if(empty(pS)){
        return false;
    }else{
        PNODE r = pS->pTop;
        pS->pTop = r->pNext;
        *val = r->data;
        free(r);
        r=NULL;
        return true;
    }
}
void traverse(PSTACK pS){
    PNODE p = pS->pTop;
    while(p!=pS->pBottom){
        printf("%d ",p->data);
        p = p->pNext;
    }
    printf("\n");
}
void pushStack(PSTACK pS,int val){
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data=val;
    pNew->pNext = pS->pTop;//必须为pS->pTop
    pS->pTop = pNew;
}
//创建效果pTop与pBottom指向头结点
void initStack(PSTACK pS){
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if(NULL==pS->pTop){
        printf("动态内存分配失败！\n");
    }else{
        pS->pBottom = pS->pTop;
        pS->pTop->pNext=NULL;//使头结点的指针域为空
    }

}
```