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

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

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

栈是只能在某一端插入和删除的特殊线性表。栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一端称栈底。插入一般称为进栈(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,指向栈顶)


四、应用

  • 函数中调用其他函数

  • 中断

  • 表达式求值

  • 内存分配

  • 缓冲处理

  • 迷宫



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

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

分享给朋友:

相关文章

【高级篇】C++中的sort函数详解

【高级篇】C++中的sort函数详解

0.简介sort函数用于C++中,对给定区间所有元素进行排序,默认为升序,也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n,比冒泡之类的排序算法效率要高,sort函数包含在头文件为#...

编写第一个C++程序

编写第一个C++程序

前面的文章介绍了Dev-C++的下载安装:【入门篇】>>> DEVC++下载、安装、简单使用 - 青少年编程知识记录 (codecoming.com)今天讲一下如何使用Dev-C++...

unsigned

在一些代码中,经常能看到unsigned这种数据类型,比如下面这样的。#include<iostream> using namespace std; int&nbs...

如何估算时间复杂度

首先:  常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n^2)<Ο(n^3)<…<Ο(2^n)<Ο(n!)时间复杂度可以简单理解为最多执...

【C++图形化编程】小游戏——打砖块(1)

【C++图形化编程】小游戏——打砖块(1)

0.前言这篇文章我们尝试创建一个打砖块的小游戏。1.游戏框架根据我们前面做的一些游戏的框架,这个小游戏的框架也可以分为下面这样的框架。int main() { startup();&n...

【数据结构】队列—基本操作

【数据结构】队列—基本操作

一、C++实例分析       C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容...