wp建站专业网站优化服务

目录

Stack

一.stack的定义方式

二.stack的使用

Queue

三.queue的定义方式

四.queue的使用

stack和queue的模拟实现

---

Stack

Stack是模拟栈区模式的一个容器，其底层是栈这个数据结构，如果你还不了解栈的话，可以通过此篇文章了解栈的原理：栈的模拟实现

一.stack的定义方式

对于stack而言，我们需要学习的构造函数如下：

• 第一个构造函数：使用默认的适配器定义栈

stack<int> l1;

• 第二个构造函数：使用特定的适配器定义栈

	stack<int, vector<int>> st2;stack<int, list<int>> st3;

注意：如果没有为stack指定特定的底层容器的话，默认情况使用deque（双端队列）。

二.stack的使用

stack常用的成员函数并不多，如下：

tack当中常用的成员函数如下：

成员函数	功能
empty	判断栈是否为空
size	获取栈中有效元素个数
top	获取栈顶元素
push	元素入栈
pop	元素出栈
swap	交换两个栈中的数据

实例：

void test2()
{stack<int, deque<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);cout << st.size() << endl;//4while (!st.empty()){cout << st.top() << ' ';//4 3 2 1st.pop();}cout << endl;
}

Queue

 Stack是模拟FIFO模式的一个容器，其底层是队列这个数据结构，如果你还不了解队列的话，可以通过此篇文章了解队列的原理：队列的模拟实现

队列是一种容器适配器，专门用在具有先进先出的环境中， 他只能在一端插入元素，另一端提取元素。 

三.queue的定义方式

方法1：使用默认的适配器定义队列。

	queue<int> q1;

方法2：使用特定的适配器定义队列。、

	queue<int，vector<int>> q2;queue<int，list<int>> q3;

注意：如果没有为stack指定特定的底层容器的话，默认情况使用deque（双端队列）。

四.queue的使用

queue当中常用的成员函数如下： 

成员函数	功能
empty	判断队列是否为空
size	获取队列中有效元素个数
front	获取队头元素
back	获取队尾元素
push	队尾入队列
pop	队头出队列
swap	交换两个队列中的数据

实例：

void test4()
{queue<int> qu1;queue<int> qu2;qu1.push(1);qu1.push(2);qu1.push(3);qu1.push(4);cout << qu1.size() << endl;//4cout << qu1.front() << endl;//1cout << qu1.back() << endl;//4qu1.swap(qu2);while (!qu2.empty()){cout << qu2.front() << " ";// 1 2 3 4qu2.pop();}
}

stack和queue的模拟实现

对于stack和queue，我们需要注意的一点是，虽然stack和queue中可以存放元素，但是STL中却并没有将其划分在容器的行列内，而是将其称为容器适配器。

这是因为stack和queue只是对其他容器的接口进行了包装，其实他使用的还是别的容器。

在CPP官网中我们可以看到，它的模板参数其实有两个，第一个是stack和queue当中所存储的元素类型，第二个参数是存储这些元素的容器。在我们不指定使用何种容器的情况下，stack和queue会默认使用deque当作默认容器。

因此，我们对stack和queue的模拟实现，其实是去调用别的容器的接口。

我们直接通过调用所指定的各个容器对应的成员函数即可完成stack的接口。 

五.Stack的实现

对于stack的实现，如下：

	template<class T=int(), class Container = deque<T>>class stack{public:stack(const Container& con=Container()):_con(con){}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}size_t size(){return _con.size();}bool empty() const{return _con.empty();}void swap(stack<T,Container>& st){_con.swap(_st._con)}private:Container _con;};

然后，我们实现queue。

六.Queue的实现

对于queue的实现，如下： 

	template<class T,class Container=deque<T>>class queue{public:queue(const Container& con = Container()):_con(con){}void push(const T& x){_con.push_back(x);}void pop(){_con, pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};