栈和队列的模拟实现

一. 回顾栈和队列

回顾一下栈和队列

• 栈：stack：后进先出
  
  _ 队列：queue：先进先出
  
  设计模式有很多种，借鉴设计模式的参考书:设计模式 - 可复用的面向对象软件元素，得知总共有 23 种设计模式。

设计模式是是前辈们对代码开发经验的总结，是解决特定问题的一系列套路，比如适配器模式，迭代器模式

栈和队列是容器适配器，而不是容器。

• 迭代器模式：将迭代器封装之后提供统一的访问方式，优点：不暴露底层细节
• 适配器模式：适配器其实是一种转换，通过已有的东西封装转换出你想要的东西。比如电源适配器（电压电流的转换，家里的电源电压通常是220v，而某个电子产品之许哟啊20v的电压，这个时候就需要用到适配器）

stack的使用

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<stack>
#include<queue>
int main()
{
	std::stack<int> st1;
	st1.push(1);
	st1.push(2);
	st1.push(3);
	st1.push(4);
	std::cout <<"在未删除之前st1的元素个数" << st1.size() << std::endl;
	//栈是后进先出，所以现在想打印的话，打印的是栈顶元素
	while (!st1.empty())
	{
		std::cout << st1.top() << " ";
		//只能将栈顶元素删除，才能打印下一个元素
		st1.pop();
	}
	std::cout << std::endl;
	std::cout << "在删除之后st1的元素个数" << st1.size() << std::endl;

	std::stack<int> st2;
	st2.push(8);
	st2.push(7);
	st2.push(6);
	st2.push(5);
	st2.swap(st1);
	std::cout << "st1和st2交换之后，st1的元素" << std::endl;
	while (!st1.empty())
	{
		std::cout << st1.top() << " ";
		//只能将栈顶元素删除，才能打印下一个元素
		st1.pop();
	}
	std::cout << std::endl;

	return 0;
}

二. stack的模拟实现

stack.h

先在私有部分将类的成员变量写出来，我们需要一个容器。

//Container有可能是vector，也有可能是list
Container _con;

首先要知道stack栈都有什么接口，我们再实现

需要实现判空，返回栈中元素的个数，栈顶元素，尾插和尾删，交换。

用C++的好处就是可以直接使用容器的接口，我们现在想用vector或list来实现stack（在过程中，可以使用vector和list的接口。

从接口可以看出，无论容器是vector还是list，都可以使用尾插尾删，以及back（获取最后一个元素），empty（判空）。

• 所以，模拟实现stack的时候，容器vector和list都可以使用

• 注意点：使用使用vector，要么展开命名空间using namespace std，要么写std::vector

#pragma once
#include<stdio.h>
#include<iostream>
#include<vector>
#include<list>
namespace hou
{
	template<class T,class Container>
	class stack
	{
	public:
		//向容器里插入数据(这里是实现stack，是尾插尾删)
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

stack.cpp

#include"stack_queue.h"
int main()
{
	hou::stack<int,std::vector<int>> mystack1;
	mystack1.push(11);
	mystack1.push(12);
	mystack1.pop();
	std::cout<<mystack1.size()<<std::endl;
	return 0;
}

三. queue的模拟实现

队列queue是先进先出，也就是尾插头删

queue.h

#pragma once
#include<stdio.h>
#include<iostream>
#include<vector>
#include<list>
namespace hou
{
	template<class T,class Container>
	class queue   
	{
	public:
		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();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

test.cpp

int main()
{
	hou::queue<int, std::list<int>> myqueue1;
	myqueue1.push(1);
	myqueue1.push(2);
	myqueue1.push(3);
	while (!myqueue1.empty())
	{
		std::cout << myqueue1.front() << std::endl;
		myqueue1.pop();
	}
	return 0;
}

四. 了解dequeue

查看stack和queue的文档时发现：Container的缺省值不是vector或list，而是deque，deque是一个双端队列（两端都可以插入删除）

queue：template <class T, class Container = deque<T> > class queue;
list：template <class T, class Container = deque<T> > class stack;

vector和list都有各自的缺陷

vector的空间是连续的，而list是一个一个的结点组成的（空间不是连续的）

1. vector的物理地址是连续的，可以使用[]访问元素（vector支持随机访问）。但同时也就导致头插头删非常麻烦，头插有扩容消耗（先查看空间是否足够，再将后面的内容一个一个往后移），头删/中部删的效率低（后面的内容往前移）。

2. list的物理空间是不连续的，它无法通过[]来访问元素（不支持随机访问）。同时也致使CPU高速缓存命中率低。但是list头插头删很容易，改变链接即可。

deque

deque兼具vector和list之长（既可以随机访问，又可以不那么）

底层实现：开一个又一个小的数组buffer，再用一个中控数组将这些buffer管理起来（中控数组它的每个元素是指针，是每个buffer的地址），所以每个buffer不用想着下一个buffer是谁，这个由中控数组在管理。

deque并不是真正连续的空间，而是由一段一段的(名字为buffer)的小空间拼接而成，再由中控数组来控制。

• 如果中控数组满了呢？那就需要异地扩容，但也不复杂，将地址复制过来就OK。
• 在deque中，不是将第一个buffer放在最前面，而是将中控数组的前几个位置空出来，为了之后需要头插做准备，如果前面有位置的话，就不用挪动数据了。

deque虽然有queue和list的优点，但也有不足的地方，无法取代它俩。

1. deque在随机访问的时候，需要知道某个数据在哪个buffer里？又是在这个buffer的第几个元素？（第几个buffer：用数据所在的位置/10。buffer的第几个元素：用数据所在的位置%10)。下标的随机访问有一定的消耗，没有vector的随机访问快。

2. 若是想在某个buffer里插入数据或删除buffer里的某个数据，怎么做呢？
   （1）挪动这个数据后面的数据--------->效率低
   （2）只挪动当前buffer的数据----------->效率还可以，(删除某个buffer的数据且只挪动当前buffer的元素)但是会导致每个buffer的个数不一样，计算在第几个buffer的第几个元素会更麻烦。所以deque在中间插入删除也有一定的消耗，相比list中间插入删除不够灵活，没有list快。栈和队列一般是插入或删除头尾的数据，使用deque当默认适配容器会比较适合！！！

deque不适合遍历。因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue**的底层数据结构

deque作为stack和queue的底层默认容器 ：在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高

总结

模拟实现stack：vector和list都可以使用
模拟实现queue：只能使用容器list（队列是先进先出，也就是头删，而vector没有头删这个接口）
实现stack和queue的默认适配容器是deque。