栈（stack）

基本定义

栈（stack）又名堆栈，是一种只允许在同一端进行数据插入和删除操作的特殊线性表。

栈的相关概念

  • 栈顶（top）：表尾，栈中允许进行数据插入和删除的一端。

  • 栈底（bottom）：表头，栈中不允许进行数据操作的一端。

  • 入栈或进栈（push）：将数据插入栈顶。

  • 出栈或退栈（pop）：将数据取出栈顶并删除。

  • 栈上溢（full）：栈内空间已满时，仍进行入栈操作，是一种空间不足的出错状态。

  • 栈下溢（empty）：栈内无数据时，仍进行出栈操作，是一种数据不足的出错状态。

  • 空栈：元素个数为零的栈。

栈的常用操作

头文件

1
#include <stack>

构造stack容器

基本语法：stack <Type> s 

1
stack <int> s;  //声明存储int类型数据的栈

返回栈顶元素

基本语法：s.top() 

1
s.top();  //返回栈顶元素

返回栈的大小

基本语法：s.size() 

1
s.size();  //返回栈的大小

判断栈是否为空

基本语法：s.empty() 

1
s.empty();  //如果栈为空返回true，否则返回false

入栈操作

基本语法：s.push(elem) 

1
s.push(1);  //向栈顶插入元素1

出栈操作

基本语法：s.pop() 

1
s,pop();  //取出栈顶元素并将其删除

队列（queue）

基本定义

队列是一种特殊的线性表，是一种先进先出的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

栈的常用操作

头文件

1
#include <queue>

构造queue容器

基本语法：queue <Type> q

1
queue <int> q;  //声明存储int类型数据的队列

返回队首元素

基本语法：q.front()

1
q.front();  //返回队首元素

返回队尾元素

基本语法：q.back()

1
q.back();  //返回队尾元素

返回队列的大小

基本语法：q.size()

1
q.size();  //返回队列的大小

判断队列是否为空

基本语法：q.empty()

1
q.empty();  //如果队列为空返回true，否则返回false

入队操作

基本语法：s.push(elem)

1
s.push(1);  //向队尾添加元素1

出队操作

基本语法：s.pop()

1
s,pop();  //从队尾移除第一个元素

pair

基本定义

pair可以将两个元素绑定在一起作为一个合成元素，可以节省编码时间。

栈的常用操作

头文件

1
#include <utility>

由于map的内部实现中设计pair，就不需要额外再去添加utility头文件了。 

1
#include <map>

构造pair容器

基本语法：pair <Typename1,Typename2> p 

1
2
3
pair <int,float> p;
//pair有两个参数，分别对应first和second的数据类型，它们可以是任意基本数据类型或应用
//该代码定义了一个新的变量p，其两个参数分别为int和float类型

初始化

基本语法：pair <Typename1,Typename2> p(Value1,Value2) 

1
2
pair <int,float> p(100,3.14);
//用pair定义一个变量p，其两个参数分别是int和float类型，初始值为100和3.14

元素访问

可以把pair定义过的东西看作一个二元结构体，该结构体中的两个元素分别是first和second，基本语法：p.first p.first 

1
2
pair <int, float> p(100, 3.14);
cout << p.first << " " << p.second << endl;  //输出结果为100 3.14

对变量进行赋值

如果使用pair定义了一个变量，对其赋值需要使用make_pair函数（利用结构体的写法分别对其first和second赋值也是可以的），基本语法：make_pair(Value1,Value2)

1
2
3
pair <int, float> p;  //定义p
p = make_pair(100, 3.14);  //使用make_pair函数进行赋值
cout << p.first << " " << p.second << endl;  //输出结果为100 3.14

比较大小

两个pair类型之间可以进行大小比较，比较规则是先以first的大小作为标准，只有当first相等时才会判别second大小。