C++中【stack-queue】的使用介绍及模拟实现

一，stack的介绍及使用

1，stack的介绍

栈stack是一种特殊对的数据结构，也是一种容器适配器。主要特点是：后进先出

所谓 容器适配器，是一种设计模式（设计模式是一套被反复使用的，多数人知晓的，经过分类编目的，代码设计经验的总结），该模式是将一个类的接口转化成客户希望的另一个类的接口。

从上图可以看出，栈stack实现时用到的容器，这里为缺省参数，缺省结构为 双端队列—deque

（双端队列—deque会在下方介绍）

首先栈stack这个容器需要实现的操作：pop出栈，也就是删除尾部元素；push入栈，也就是尾部插入元素；还有判空。

而vector,list,deque这些容器都可以实现上面的操作，默认情况下，如果没有指定容器，使用deque作为底层容器。

2，stack的使用

1.push 入栈

在栈顶插入一个元素，成为新的栈顶。  

代码示例：

void test1() {     stack<int> s;   //构造一个空栈,底层为deque     //stack<int,vector<int>> s;   //构造一个空栈,底层为vector     s.push(1);     s.push(2);     //向栈中插入元素[1,2,3,4]     s.push(3);     s.push(4); }

 2.top 返回栈顶数据

代码示例：

3.pop 出栈 

删除栈顶元素。

代码示例:

void test3() {     stack<int> st;       st.push(1);     st.push(2);     st.push(3);     // 向 栈 中插入 元素 [1，2，3，4，5]     st.push(4);     st.push(5);     cout << st.top() << endl; // 返回栈的 顶部元素  -- [5]     st.pop();                 // 删除栈顶元素 -- [5]     cout << st.top() << endl; // 返回栈的 顶部元素  -- [4] }

4，empty 判空

栈为空，返回true;否则返回false  

void test4() {     stack<int> st;     st.push(1);     st.push(2);     st.push(3);          st.push(4);     st.push(5);     cout << st.empty() << endl;   //栈不为空，值为0 }

 5，size

返回栈中元素个数

void test4() {     stack<int> st;     st.push(1);     st.push(2);     st.push(3);          st.push(4);     st.push(5);     cout << st.size() << endl;  //结果为5 }

6，swap

交换两个栈的元素数据

代码示例：

void test5() {     stack<int> s1;     s1.push(1);     s1.push(2);     s1.push(3);     stack<int> s2;     s2.push(5);     s2.push(6);     s2.push(7);     //交换前 s1 [1,2,3]   s2  [5,6,7]     s1.swap(s2);       //遍历两个栈     while (!s1.empty())  //s1不为空     {         cout << s1.top() << " ";     //结果  7 6 5         s1.pop();     }     cout << endl;     while (!s2.empty())  //s2不为空     {         cout << s2.top() << " ";     //结果3 2 1         s2.pop();     } }

二，queue的介绍及使用

1，queue的介绍

1，队列queue遵循先进先出的原则，从容器一段插入元素，另一端提取元素。元素从队尾入队列，从队头处队列。 2，队列queue作为适配器实现，和栈一样，底层用的也是 双端队列—deque。 3，底层容器可以是标准模板容器之一，比如vector,list,deque等，要求是这些容器可以是实现一下操作： empty:判断容器是否为空 size：容器的元素个数 front:返回对头元素 back：返回队尾元素 push_back:在队尾插入元素 pop_front:在队头出元素，也就是删除队列中的头部元素

 2，queue的使用

1.push

在队尾插入一个元素

代码示例:

void test6() {     queue<int> q;     q.push(1);     q.push(2);     q.push(3);     q.push(4);  //队尾插入  [1,2,3,4] }

2,size

返回元素个数 

void test6() {     queue<int> q;     q.push(1);     q.push(2);     q.push(3);     q.push(4);  //队尾插入  [1,2,3,4]     cout << q.size() << endl;    //值为4 } 

3，front

返回队列的头部元素 

4，back

返回队列中最后一个元素，也就是队尾元素 

5，pop

删除队列中的第一个元素，也就是队头元素 

6，empty 判空

7,swap

和stack一样，交换两个队列queue的数据 。

三，双端队列—deque的介绍 

deque可以理解为是list和vector的结合，它结合了list和vector的优缺点。

首先分析一下vector和list:

对于vector： 优点： 1，支持高效的随机下标访问，尾插效率还不错。 2，连续的物理空间，使用高速缓存利用率高。 缺点： 1，空间需要扩容，扩容需要一些消耗。 2，头部和中间插入删除效率低。

对于list：  有点： 1，按需申请释放空间，不需要扩容。 2，任意位置插入删除效率高。 缺点： 不支持下标随机访问

下来了解一下deque的结构：

 deque:是一种双开口的”连续“空间结构，双开口的含义：可以在头尾两端进行插入删除元素，且时间复杂度为O(1),与vector比较，头插效率高，与list比较，空间利用率高。

deque并不是真正的连续空间，而是由一段连续的小空间拼接而成的。实际deque类似于一个动态二维数组。

从上图可以看出， 双端队列底层是一种假象的连续空间，实际是分段连续的，为了维护其”整体连续“和随机访问的假象，就需要通过迭代器来维护。

迭代器：

迭代器包含4个成员，first指向当缓冲区第一个位置，last指向当前缓冲区的最后一个位置， cur指向当前数据的位置，node指向 中控数组中 指向当前缓冲区的位置。

上面是deque的结构，具体实现看下面的例子：

假设有三块空间，begin()和end()两个迭代器所指的位置如图。

当需要在queue的头部或尾部插入或删除元素时，只会涉及到相关缓冲回去的操作，不会影响其他缓冲区。而且这些操作的时间复杂度为常数级别O(1）

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。 

 所以，可以理解deque是结合了vector和list的优缺点形成的。

stack和queue使用deque的原因：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。 2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

四，模拟实现

1，stack的模拟实现

对stack的实现，只需实现它的常用接口，底层结构是deque。实际上是对deque的复用。

namespace xg
{
	// Containerתstack
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		//入栈
		void push(const T& x)
		{
			_con.push_back(x);
		}
		//出栈
		void pop()
		{
			_con.pop_back();
		}
		//栈顶数据
		const T& top() const
		{
			//return _con.func();
			return _con.back();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _con;
	};


}

2，queue的模拟实现

同理，只需实现常用接口，然后复用deque结构

namespace xg
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		//队尾入
		void push(const T& x)
		{
			_con.push_back(x);
		}
		//队头出
		void pop()
		{
			_con.pop_front();
		}
		//队头数据
		const T& front() const
		{
			return _con.front();
		}
		//队尾数据
		const T& back() const
		{
			return _con.back();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}