作者: Vergil_wj | 来源:发表于2021-07-28 08:27 被阅读0次

定义

一种可以实现“先进后出”的存储结构。

分类

  • 静态栈
  • 动态栈

算法

  • 出栈
  • 压栈
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *pNext;
} NODE, *PNODE;

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
} STACT, *PSTACT; //PSTACT 相当于 struct Stack *

void init(PSTACT);
void push(PSTACT, int);
void traverse(PSTACT);
bool pop(PSTACT, int *);

int main(void)
{

    STACT S; //STACT 等价于 struct Stack

    init(&S);    //造出一个空栈
    push(&S, 1); //压栈
    push(&S, 2);
    traverse(&S); //遍历输出

    return 0;
}

void init(PSTACT pS)
{
    pS->pTop = (NODE)malloc(sizeof(NODE));
    if (NULL == pS->pTop)
    {
        printf("动态内存分配失败!\n");
        exit(-1)
    }
    else
    {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL; // pS->pBottom->pNext = NULL
    }
}

//压栈
void push(PSTACT pS, int val)
{
    PNODE pNew = (NODE)malloc(sizeof(NODE));
    pNew->data = val;
    pNew->pNext = pS->pTop;
    pS->pTop = pNew;
    return;
}

//遍历
void traverse(PSTACT pS)
{
    PNODE p = pS->pTop;
    while (p != pS->pBottom)
    {
        printf("%d ", p->data);
        p = pS->pNext;
    }
    printf("\n");
    return;
}

//判断栈是否为空
bool empty(PSTACT pS)
{
    if (pS->pTop == pS->pBottom)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//把 pS 所指向的栈出栈一次,并把出栈的元素存入 pVal 形参所指向的变量中.
//出栈失败返回 false,否则返回 true
bool pop(PSTACT pS, int *pVal)
{
    if (empty(pS) == true)
    {
        return false;
    }
    else
    {
        PNODE r = pS->pTop;
        pS->pTop = r->pNext;
        *pVal = r->data;
        free(r);
        r = NULL;
        return true;
    }
}

//清空
void clear(PSTACT 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;
    }
}

应用

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

相关文章

  • Java实现栈

    数组栈:压栈、出栈、返回栈顶元素 链式栈:压栈、出栈、返回栈顶元素

  • 数据结构之 栈

    栈结构 链式栈 一.栈结构体 1构建空栈 2栈置空 3判断栈空 4获取栈顶 5入栈 6出栈 7便利栈 二.链式栈 ...

  • 栈和队列

    1、栈 栈是一种先进先出的数据结构。栈顶进栈,栈顶出栈。 数据结构 栈的初始化 进栈 出栈 栈的最小值 2、队列 ...

  • 递归累加数组

    入栈 5入栈 4入栈 3入栈 2入栈 1出栈 [1 0]出栈 [2 1 0]出栈 [3 2 1 0]出栈 [4 3...

  • 栈的逻辑结构和存储结构

    main()进栈s(1)进栈s(0)进栈 s(0)出栈s(1)出栈main()出栈 顺序栈 一个数组 + 指向栈顶...

  • 单调栈 2020-06-12(未经允许,禁止转载)

    1.单调栈 指栈内元素保持单调性的栈结构,分为单调增栈(栈底到栈顶元素递增)和单调减栈(栈底到栈顶元素递减) 2....

  • 链栈的操作

    链栈的定义 链栈的操作 初始化 判断栈空 入栈 出栈

  • 函数调用栈平衡

    栈平衡 栈平衡:函数调用前后的栈顶指针指向的位置不变 内平栈 外平栈 内平栈: 指的是在函数调用返回之前使栈保持...

  • 栈的简单Java实现

    栈栈的特点是先进后出,出栈、入栈都是在栈顶操作。

  • 汇编学习-入栈和出栈

    栈有两个基本的操作:入栈和出栈。入栈就是将一个新的元素放到栈顶,出栈就是从栈顶取出一个元素。栈顶的元素总是最后入栈...

网友评论

      本文标题:

      本文链接:https://www.haomeiwen.com/subject/svtcmltx.html