栈和队列

队列的特点：先进先出（FIFO）或者后进后出（LILO）。在生活工作中应用非常广泛，例如生活中的小到银行抽号，医院挂号，小时放学要排队回家，打饭要依次排队。大到正式的颁奖典礼。获奖人员依次排队。举行一场盛大的晚会，舞会等等各种会议。从计划到结束其中过程也是一个排队的过程。

栈的特点：先进后出（FILO）或者后进先出（LIFO）。栈在生活中也是应用很广泛的，比如学过栈的老铁听到栈都会想起那个子弹夹。其实它离我们普通人有些过远。那说说我们息息相关的用栈的例子。比如我们每天都会用的一个东西，水杯等等一系列这类容器，最先倒进去的水是不是先喝到。还有每天上网打开的网页，当觉得又想看之前的网页时直接回退，这也是利用了栈原理。

既然它们有如此广泛的应用。那么就要切实的掌握它并且应用于生活。提高生活水平做一点贡献，有点大呵呵。

接下来模拟栈和队列。

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

namespace StackAndQueue
{
	//模拟实现栈
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		//1.构造函数
		stack()
		{}

		//2.压栈
		void push(const T& data)
		{
			Deque.push_back(data);
		}

		//3.弹栈
		void pop()
		{
			Deque.pop_back();
		}

		//4.返回栈顶元素
		T& top()
		{
			return Deque.back();
		}

		T& top()const
		{
			return Deque.back();
		}

		//5.判断栈是否为空
		bool empty()const
		{
			return Deque.empty();
		}

		//6.获取栈的数据个数
		size_t size()const
		{
			return Deque.size();
		}

		//7.析构函数
		~stack()
		{}
	private:
		Container Deque;
	};

	//模拟实现队列
	template<class T, class Contianer = deque<T>>
	class queue
	{
	public:
		//1.构造函数
		queue()
		{}

		//2.入队列
		void push(const T& data)
		{
			Deque.push_back(data);
		}

		//3.出队列
		void pop()
		{
			Deque.pop_front();
		}

		//4.获取队尾元素
		T& back()
		{
			return Deque.back();
		}

		T& back()const
		{
			return Deque.back();
		}
		//5.获取队首元素
		T& front()
		{
			return Deque.front();
		}

		T& front()const
		{
			return Deque.front();
		}
		//6.判断队列是否为空
		bool empty()
		{
			return Deque.empty();
		}
		//7.获取队列的数据个数
		size_t size()
		{
			return Deque.size();
		}
		//8.析构函数
		~queue()
		{}
	private:
		Contianer Deque;
	};
}

void TestStack()
{
	StackAndQueue::stack<int> S;
	cout << "stack empty = " << S.empty() << endl;
	S.push(0);
	S.push(1);
	S.push(2);
	S.push(3);
	S.push(4);
	S.push(6);

	cout << "stack size = " << S.size() << endl;
	cout << "stack top = " << S.top() << endl;
	cout << "stack empty = " << S.empty() << endl;

	S.pop();
	cout << "stack popOne" << endl;
	cout << "stack size = " << S.size() << endl;
	cout << "stack top = " << S.top() << endl;
	cout << "stack empty = " << S.empty() << endl;
}

void TestQueue()
{
	StackAndQueue::queue<int> Q;
	cout << "queue empty = " << Q.empty() << endl;
	Q.push(0);
	Q.push(1);
	Q.push(3);
	Q.push(4);
	Q.push(5);
	Q.push(6);

	cout << "queue size = " << Q.size() << endl;
	cout << "queue back = " << Q.back() << endl;
	cout << "queue front = " << Q.front() << endl;
	cout << "queue empty = " << Q.empty() << endl;

	Q.pop();
	cout << "queue popOne" << endl;
	cout << "queue size = " << Q.size() << endl;
	cout << "queue back = " << Q.back() << endl;
	cout << "queue front = " << Q.front() << endl;
	cout << "queue empty = " << Q.empty() << endl;
}
int main()
{
	TestStack();
	system("pause");
	return 0;
}

运行栈测试用例：

运行队列测试用例：

疑问：

? ? ?1.为什么要用deque来实现queue和stack而没有用vector和list呢？

这是因为deque它的效率高于vector和list。主要表现在：它在扩容时不需要搬移数据避免了vector的缺点。队列和栈的元素都是相邻更加易于管理。而用list的话要增加过多的内存，没必要。（它要保存前后数据的地址）。

? ? 2.stack和queue都没有迭代器，是因为它们都只是在端点进行操作，不须遍历每个数据。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍&源码