技术标签: 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如果喜欢话,可以关注一下
文章浏览阅读3.8k次,点赞9次,收藏28次。直接上一个工作中碰到的问题,另外一个系统开启多线程调用我这边的接口,然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法,放到线上后发现确实是可以正常取到结果,但是一旦调用,CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了,类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99
文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效
文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别,这些API绝大多数都被包装到了一个具名和核心模块中了,例如文件操作的 fs 核心模块 ,http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是
文章浏览阅读10w+次,点赞435次,收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件
文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢?1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件
文章浏览阅读867次,点赞2次,收藏2次。docker安装elasticsearch,elasticsearch-head,kibana,ik分词器安装方式基本有两种,一种是pull的方式,一种是Dockerfile的方式,由于pull的方式pull下来后还需配置许多东西且不便于复用,个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码
文章浏览阅读1.3w次,点赞57次,收藏92次。整理 | 郑丽媛出品 | CSDN(ID:CSDNnews)近年来,随着机器学习的兴起,有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块,内置..._beeware
文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年 飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停
文章浏览阅读986次,点赞2次,收藏2次。1.硬性等待让当前线程暂停执行,应用场景:代码执行速度太快了,但是UI元素没有立马加载出来,造成两者不同步,这时候就可以让代码等待一下,再去执行找元素的动作线程休眠,强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待
文章浏览阅读3k次,点赞4次,收藏14次。Java软件工程师职位分析_java岗位分析
文章浏览阅读2k次。Java:Unreachable code的解决方法_java unreachable code
文章浏览阅读1w次。1、html中设置标签data-*的值 标题 11111 222222、点击获取当前标签的data-url的值$('dd').on('click', function() { var urlVal = $(this).data('ur_如何根据data-*属性获取对应的标签对象