【CPP】栈简介及简化模拟实现

CPP栈和队列简单模拟实现

1. 栈的简介

栈 是一种 特殊的线性表，具有数据 先进后出 特点。
具体参考：【数据结构】栈

CPP库参考文档：stl_stack

注意：
1.stack本身 不支持迭代器操作
主要原因是因为stack不支持数据的随机访问，必须保证数据先进后出的特点。

2.stack在CPP库中实现为一种 容器适配器
所谓容器适配器，是为了适应不同的数据存储而修改底层的数据结构从而达到优化效率的目的。
参考：C++ STL容器适配器（详解）

2. 栈简化模拟实现

C版简化模拟栈：【数据结构】栈
CPP版简化模拟栈：

#pragma once
#include
#include

using namespace std;
namespace szg
{
	template<class T, class Container = vector<T>>
	class stack
	{
	private:
		Container _st;
	public:
		void push_back(const T& num)
		{
			_st.push_back(num);
		}

		void pop_back()
		{
			_st.pop_back();
		}

		bool empty()
		{
			return _st.empty();
		}

		size_t size()
		{
			return _st.size();
		}

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

实际上，stack在库中给的容器缺省值是deque，是一个 顺序表与链表的结合体。
deque参考文档：stl_deque
deque底层逻辑简介：【CPP】双端队列简介(deque)

3. 栈练习题

栈算法——最小栈
栈算法——逆波兰表达式求值
栈算法——栈的压入、弹出序列

---

EOF