[STL]stack和queue使用介绍

文章目录

[STL]stack和queue使用介绍
- stack使用介绍
- - stack介绍
  - 构造函数
  - empty函数
  - push函数
  - top函数
  - size函数
  - pop函数
- queue使用介绍
- - queue介绍
  - 构造函数
  - empty函数
  - push函数
  - front函数
  - back函数
  - size函数
  - pop函数
- deque介绍

stack使用介绍

stack介绍

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
- empty：判空操作
- back：获取尾部元素操作
- push_back：尾部插入元素操作
- pop_back：尾部删除元素操作
标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

构造函数

stack只有默认构造函数,构造一个空栈。

stack<int> st;

同样是构造一个空栈，stack还可以指定底层容器进行构造。

stack<int, vector<int>> st;

empty函数

empty函数用于判断stack是否为空。

#include <iostream>
#include <stack>
using namespace std;
int main()
{
	stack<int> st;
	cout << st.empty() << endl; //输出为1
	return 0;
}

push函数

push函数用于往stack中压入数据。

#include <iostream>
#include <stack>
using namespace std;
int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	cout << st.empty() << endl; //输出为0
	return 0;
}

top函数

top函数用于获取stack的顶部数据。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	cout << st.top() << endl; //输出为3
	return 0;
}

size函数

size函数用于获取stack内的数据个数。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	cout << st.size() << endl; //输出为3
	return 0;
}

pop函数

pop函数用于弹出stack顶部的数据。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.pop();
	cout << st.top() << endl; //输出为2
	return 0;
}

queue使用介绍

queue介绍

queue是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
queue作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
- empty：检测队列是否为空
- size：返回队列中有效元素的个数
- front：返回队头元素的引用
- back：返回队尾元素的引用
- push_back：在队列尾部入队列
- pop_front：在队列头部出队列
标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则默认使用标准容器deque。

构造函数

queue只有默认构造函数,构造一个空队列。

queue<int> q;

同样是构造一个空队列，queue还可以指定底层容器进行构造。

queue<int, list<int>> q;

empty函数

empty函数用于判断queue是否为空。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	cout << q.empty() << endl; //输出为1
	return 0;
}

push函数

push函数用于往将数据尾插至队列。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.empty() << endl; //输出为0
	return 0;
}

front函数

front函数用于获取队头的数据。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.front() << endl; //输出为1
	return 0;
}

back函数

back函数用于获取队尾的数据。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.back() << endl; //输出为3
	return 0;
}

size函数

size函数用于获取队列内的数据个数。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.size() << endl; //输出为3
	return 0;
}

pop函数

pop函数用于删除队头的数据。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.pop();
	cout << q.front() << endl; //输出为2
	return 0;
}

deque介绍

STL中stack和list的底层实现都使用的是deque容器。

deque(双端队列)兼容了vector和list的使用接口，使得deque可以在头尾两端进行插入和删除操作，并且还支持数据的随机访问。deque的结构示意图如下:

deque设计了一个中控数组，往中控数组中插入数据需要从中间开始插入，然后从中间开始进行头插和尾插，中控数组中的结点存储着指针，指向一段连续的空间，中控数据空间不够了会进行扩容，并将原有数据拷贝。由于每个结点指向的连续空间内存储的数据个数和容量是已知的，因此要进行随机访问，可以通过计算得到相应的结点和连续空间内的相应位置来实现，当然往deque内中间位置插入数据也是从中间结点指向的空间开始插入，向deque头插(删)或尾插(删)只需要从中控数据的头结点和尾结点寻找数据，在指向的空间内找到对应位置进行操作。

优点: