技术标签: C++ c++ stack std 栈 数据结构
栈是一种线性的数据结构,其是一种运算受限(限定仅在表尾进行插入和删除的线性表)的线性表。栈的结构类似下图的容器:
如上图所示,栈的结构就像一个端封闭,另一端开口的容器,往容器放入小球(对应栈中的元素),先放入的小球就越靠近容器的底部,最早进入的小球对应的位置就是栈底(bottom),最后放入的小球对应的位置就是栈顶(top),放入小球的动作就叫做入栈(push);取出小球的时候,只能按照放入顺序相反的顺序来取,即先取后放入的,再去先放入的,每次取小球的动作就叫做出栈(pop)。由于栈的单端口进出的限制,决定了栈中的元素只能先进后出(FILO, First In Last Out)。栈的数据结构可以使用数组来实现,也可以用链表来实现,具体如下图所示:
入栈就是把元素存放入栈中,由于栈的结构只允许从一次存放元素,所以新元素的存入后所在的位置就是该栈新的栈顶,我们以栈的数组实现为例,入栈的过程如下图所示:
出栈就是把元素从栈中弹出,同样的由于栈结构单端进出的限制,出栈时候的元素就是栈顶对应的元素,取出元素后,出栈元素前面的那个元素对应的位置将变成新的栈顶。出栈的过程如下:
由于栈的后进先出的特性,使得入栈和出栈只会影响到栈中最后一个元素,不会涉及到其他元素的移动,因此入栈和出栈的时间复杂都为 O ( 1 ) O(1) O(1)。同样的,栈的先入后出的特性,也使得栈不能拥有遍历、随机访问和随机插入的功能。
由于栈的特殊结构,栈常用于以下场景:
逆序输出:由于栈先入后出的特性,使用栈结构可以轻松实现逆序输出的操作。
语法检测:对于一些成对出现的符号,如"[]“、”()"等,凡是遇到符号的前半部分,即入栈(push)该符号,凡是遇到括号后半部分的,就与栈顶元素进行匹配,如果匹配成功,则出栈(pop),否则就是匹配失败,语法错误。
数字进制转换:顺序计算,继续结果逆序输出。
栈的应用场景还有很多,这里就不一一举例,实际上栈的应用都是基于栈的先入后出的特性。
stack类是C++标准库提供的一个容器适配器,它给使用者提供了栈的功能,实现的栈的先进后出(FILO)的数据结构,并提供了特定的函数集合,其定义如下所示:
template<
class T,
class Container = std::deque<T>
> class stack;
该类模板在头文件<stack>中定义。
访问栈顶元素使用top()函数,该函数的定义如下:
reference top();
const_reference top() const;
该函返回栈中栈顶元素的引用。实际上调用的就是底层容器的back()。
size():返回底层容器中的元素数 。实际上调用的就是底层容器的size()。
empty():检查底层容器是否为空,如果为空返回true,否则false。实际上调用的就是底层容器的empty()。
push:向栈中推入元素。其函数声明如下:
void push( const value_type& value );
void push( value_type&& value ); //C++11 起
emplace:推入新元素到栈中,与push不同的是该函数是原位构造元素(直接在容器内构造对象,不用拷贝一个复制品再使用),既不进行也不进行复制操作。其函数声明如下:
template< class... Args >
void emplace( Args&&... args ); //C++11 起 C++17 前
template< class... Args >
decltype(auto) emplace( Args&&... args ); //C++17 起
其中args为转发给元素构造函数的参数。也正是由于emplace的原位构造元素,省去了拷贝构造的过程,使得emplace的效率高于push。
pop:从栈中移除站定元素。实际上调用的就是底层元素的pop_back()。
swap:交换栈与另一个栈中的内容,其函数声明如下:
void swap( stack& other ) noexcept(/* see below */); //C++11 起
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// push()
s.push(1);
s.push(2);
s.push(3);
cout << "按顺push元素1、2、3后" << endl;
cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
if (!s.empty())
cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
else
cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;
s.pop(); // 弹出栈顶元素
cout << "\n弹出栈顶元素3, 即pop()后" << endl;
cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
if (!s.empty())
cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
else
cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;
s.pop();
cout << "\n弹出栈顶元素2, 即pop()后" << endl;
cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
if (!s.empty())
cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
else
cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;
s.pop();
cout << "\n弹出栈顶元素1, 即pop()后" << endl;
cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
if (!s.empty())
cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
else
cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;
// swap()操作
s.emplace(1);
s.emplace(2);
s.emplace(3);
stack<int> s1;
cout << "\n-----------栈s和s1交换前----------" << endl;
cout << "\ns的状态: " << endl;
cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
if (!s.empty())
cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
else
cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;
cout << "\ns1的状态: " << endl;
cout << "栈s1中元素的数量, 即s1.size() = " << s1.size() << endl;
cout << "此时, 栈s1是否为空,即s1.empty() = " << s1.empty() << endl;
if (!s1.empty())
cout << "此时, 栈s1非空, 栈顶元素,即s1.top() = " << s1.top() << endl;
else
cout << "此时, 栈s1为空, 不能使用top访问栈顶元素" << endl;
s1.swap(s); // s和s1进行交换
cout << "\n-----------栈s和s1交换后----------" << endl;
cout << "\ns的状态: " << endl;
cout << "栈s中元素的数量, 即s.size() = " << s.size() << endl;
cout << "此时, 栈s是否为空,即s.empty() = " << s.empty() << endl;
if (!s.empty())
cout << "此时, 栈s非空, 栈顶元素,即s.top() = " << s.top() << endl;
else
cout << "此时, 栈s为空, 不能使用top访问栈顶元素" << endl;
cout << "\ns1的状态: " << endl;
cout << "栈s1中元素的数量, 即s1.size() = " << s1.size() << endl;
cout << "此时, 栈s1是否为空,即s1.empty() = " << s1.empty() << endl;
if (!s1.empty())
cout << "此时, 栈s1非空, 栈顶元素,即s1.top() = " << s1.top() << endl;
else
cout << "此时, 栈s1为空, 不能使用top访问栈顶元素" << endl;
return 0;
}
输出结果:
按顺push元素1、2、3后
栈s中元素的数量, 即s.size() = 3
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 3
弹出栈顶元素3, 即pop()后
栈s中元素的数量, 即s.size() = 2
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 2
弹出栈顶元素2, 即pop()后
栈s中元素的数量, 即s.size() = 1
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 1
弹出栈顶元素1, 即pop()后
栈s中元素的数量, 即s.size() = 0
此时, 栈s是否为空,即s.empty() = 1
此时, 栈s为空, 不能使用top访问栈顶元素
-----------栈s和s1交换前----------
s的状态:
栈s中元素的数量, 即s.size() = 3
此时, 栈s是否为空,即s.empty() = 0
此时, 栈s非空, 栈顶元素,即s.top() = 3
s1的状态:
栈s1中元素的数量, 即s1.size() = 0
此时, 栈s1是否为空,即s1.empty() = 1
此时, 栈s1为空, 不能使用top访问栈顶元素
-----------栈s和s1交换后----------
s的状态:
栈s中元素的数量, 即s.size() = 0
此时, 栈s是否为空,即s.empty() = 1
此时, 栈s为空, 不能使用top访问栈顶元素
s1的状态:
栈s1中元素的数量, 即s1.size() = 3
此时, 栈s1是否为空,即s1.empty() = 0
此时, 栈s1非空, 栈顶元素,即s1.top() = 3
文章首发公众号:iDoitnow如果喜欢话,可以关注一下
文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的,浏览器出于安全考虑是禁止的。警告信息如下:不过jQuery对跨域问题也有解决方案,使用jsonp的方式解决,方法如下:$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr
文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry,也就是我们所说的 使用空间SQL 的方法,官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下,主要就分为以下几个步骤。..._extproc
文章浏览阅读1.5w次。linux下没有上面的两个函数,需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数,转换过程中受到系统编码类型的影响,需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8
文章浏览阅读750次。今天准备从生产库向测试库进行数据导入,结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误,google一下,发现可能有如下原因导致imp的数据太大,没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件,向高版本imp导出的dmp文件出错传输dmp文件时,文件损坏解决办法:imp时指定..._imp-00009导出文件异常结束
文章浏览阅读143次。当下是一个大数据的时代,各个行业都离不开数据的支持。因此,网络爬虫就应运而生。网络爬虫当下最为火热的是Python,Python开发爬虫相对简单,而且功能库相当完善,力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页,按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息,通过分析请求信息可以了解请..._初级python程序员能力要求
文章浏览阅读7.6k次,点赞2次,收藏6次。@Service标注的bean,类名:ABDemoService查看源码后发现,原来是经过一个特殊处理:当类的名字是以两个或以上的大写字母开头的话,bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname
文章浏览阅读6.9w次,点赞73次,收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立
文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能,如果文件名出现中文,便会以乱码视之。 解决方法: fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码
文章浏览阅读2.1k次,点赞4次,收藏23次。第一次实验 词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别,找出文件中所有的合法的单词,并给出一定的信息作为最后的结果,用于后续语法分析程序的使用;本实验针对 PL/0 语言 的文法、词汇表编写一个词法分析程序,对于每个单词根据词汇表输出: (单词种类, 单词的值) 二元对。词汇表:种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词
文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限
文章浏览阅读6.8k次,点赞12次,收藏125次。1. 单目相机标定引言相机标定已经研究多年,标定的算法可以分为基于摄影测量的标定和自标定。其中,应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统,在标定过程中,相机拍摄多个角度下(至少两个角度,推荐10~20个角度)的标定板图像(相机和标定板都可以移动),即可对相机的内外参数进行标定。下面介绍张氏标定法(以下也这么称呼)的原理。原理相机模型和单应矩阵相机标定,就是对相机的内外参数进行计算的过程,从而得到物体到图像的投影_相机-投影仪标定
文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的 硬件支持简 述: 翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构;一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。 内核是从一个输入设备中获取一个事件,并通过 evdev 输入_wayland