当前位置:首页 > C++知识 > 正文内容

【数据结构】栈(Stack)的介绍

亿万年的星光4年前 (2021-02-19)C++知识2075

栈是只能在某一端插入和删除的特殊线性表。栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一端称栈底。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为后进先出表(LIFO表)。


一、栈的定义



二、分类

  • 静态栈:使用数组

  • 动态栈:链表

  • 标准库STL中的stack


三、算法

  • 入栈:push

  • 出栈:pop

  • 判断栈空:empty

  • 栈大小:size

  • 访问栈顶:top


  1. 进栈(PUSH)算法

    ①若top >= n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则进行②)

    ②top++ (栈指针加1,指向进栈地址)

    ③s[top]=x,结束(x为新进栈的元素)

  2. 退栈(POP)算法

    ①若top<=0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈,空则下溢;不空则进行②)

    ②x=s[top],(退栈后的元素赋给x)

    ③top--,结束(栈指针减1,指向栈顶)


四、应用

  • 函数中调用其他函数

  • 中断

  • 表达式求值

  • 内存分配

  • 缓冲处理

  • 迷宫



扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【算法】前缀和与差分(3)二维数组前缀和

【算法】前缀和与差分(3)二维数组前缀和

0.前言前面的一篇文章,介绍了一维数组的前缀和,这篇文章中,介绍一下二维数组的前缀和1.定义二维数组的前缀和就是按照二维数组求和。公式如下:那二维前缀和中一个f[i][j]表示的意思就是以(1,1)为...

C++ 如何隐藏光标

在C++控制台做小游戏的时候,光标一直在闪,影响体验效果,我们可以通过下面的函数隐藏光标位置。void HideCursor(){ CONSOLE_CURSOR_INFO cu...

【贪心】区间选点

【贪心】区间选点

【题目描述】数轴上有n个闭区间[ai, bi],取尽量少的点,使得每个区间内都至少有一个点。(不同区间内含的点可以是同一个,1<=n<=10000,1<=ai<=bi<=...

【C++图形化编程】鼠标函数及鼠标画板

【C++图形化编程】鼠标函数及鼠标画板

0.前言这篇文章简单介绍一下利用鼠标画图的程序#include<graphics.h> #include<conio.h> int main(){ initg...

STL入门——容器2:set

一、简单介绍    set是STL中一个很有用的容器,用来存储同一种数据类型的数据结构(可以称之为K的模型),基本功能与数组相似。set与数组不同的是,在set...

树的遍历

在应用树结构解决问题时,往往要求按照某种此项获得树中全部结点的信息,这种操作叫做树的遍历。遍历的方法有很多种。常用的有:A. 先序遍历:先访问根结点,再从左到右按照先序思想遍历各子树。B. 后序遍历:...