[Day09]程序菜鸟自学C++资料结构演算法 – 堆叠Stack介绍与建立

前言：介绍完了阵列和链结串列的实作之後，接着就要进入下一个主题－堆叠。那堆叠事甚麽，又有怎麽样的特性？
先给大家一些生活上的实例，自己发现的话印象会底较深刻喔！

范例图：品客洋芋片

图片来源：https://s.yimg.com/zp/images/0F49AD5EC9273540E2676E406BE52EC902A406B7

叠好的盘子

图片来源：https://img95.699pic.com/xsj/00/1y/83.jpg!/fh/300

装满东西的袋子

图片来源：https://png.pngtree.com/png-vector/20190905/ourmid/pngtree-paper-bag-with-food-cucumbers-tomatoes-png-image_1724444.jpg
有发现这些东西的相同点吗？
是不是拿东西的时候都是从最上方开始拿的，况且这些最上方的东西都是最晚放进去的，这就是堆叠最终要的特性「後进先出(LIFO： Last in First Out)」。

堆叠其实是一群相同资料型态的组合，所有的动作均在堆叠顶端进行，此外堆叠还有许多中应用，最常被用在副程序、递回的呼叫和记忆体的使用。

堆叠的操作：在堆叠中增添资料称为『推进Push』，以及删去元素称为『移出Pop 』，这两个事堆叠最常用且最基本的函示，其他还有Create建立新的堆叠和Peek回传顶端资料等用法。

抽象资料型别（Abstract Data Type，ADT）：

在解析资料时，可能会将原本的资料转换成不同形式处理，再以资料的样貌显示或存取，但在设计与分析演算法的时候，并不会针对某一个演算法特定的资料型态，而是对资料的一般特性与操作方式进行讨论。ADT是一种理论上的观念，并不局限於一种特定的语言，每一种ADT更可以透过不同方式实现。
堆叠就是属於ADT的一种，简而言之，从抽象角度描述的数据结构之间的关系和对数据进行的操作，以堆叠为例，抽象的堆叠就是由Push、Pop等操作来定义。
之後会提到的伫列和树也都算ADT的一种。

简单介绍完基本的堆叠，现在要来实际创建看看， 一样先创建一个新的专案，忘记或是初见的人如果不知道怎麽创建的话可以去Day04的阵列实作看看
≧ω≦

首先创建空堆叠并编写基本的应用。

可以看到最先进入堆叠的A在最後才显示出来，表示创建成功。

也可以将字元的资料改成字串。

不过要注意在主程序(main)前要加上#include 的标头档才能对对字串进行较高阶的操作，像是字串指定、串接等。

今日小结：了解堆叠之後，是不是觉得经常出现在生活中呢？有了熟悉感在学习上也比较不那麽排斥吧！今天简单介绍了堆叠是甚麽以及实作创建，明天会来做括号匹配和河内塔等堆叠的延伸应用٩(●˙▿˙●)۶…⋆ฺ

template<typename T>
class SqlStack {
	T* data, * top_; //建立指针变量T指向元素，及top_指向堆叠的位置
	int capacity;

public:
	SqlStack(int cap = 3) {
		data = new T[cap];
		if (!data) { top_ = 0; capacity = 0; return; } //创建失败的情况
		top_ = data; capacity = cap; //创建成功的条件
	}
	T& top() { //编写top()检查堆叠是否为空的，并返回T类型的引用变量
		if (top_ == data) throw "堆叠为空";
		return *(top_ - 1);
	}
	bool push(T e) { //编写push()函式，且容量也会随资料的增加变多
		if (top_ - data == capacity) {
			T* p = new T[2 * capacity];
			if (!p) return false;
			for (int i = 0; i < capacity; i++)
				p[i] = data[i];
			delete[] data; data = p;
			top_ = data + capacity;
			capacity = 2 * capacity;
		}
		*top_ = e; top_++; return true;
	}
	bool pop() { //编写pop()函示，需先判对堆叠是否为空
		if (top_ == data) return false;
		top_--; return true;
	}
	bool empty() { //检查堆叠是不是空的，与top()相同概念
		return top_ == data;
	}
	void clear() { //清除堆叠所有元素
		top_ == data;
	}
};

#include<iostream>
#include<string>
using std::string;

int main(){
	SqlStack<char> S;
	S.push('A'); //push元素
	S.push('B');
	S.push('C');
	S.push('D');
	while (!S.empty()) { //pop元素直到堆叠为空
		char e = S.top();
		std::cout << e << " ";
		S.pop();
	}

	SqlStack<string> S2;
	S2.push("Jason");
	S2.push("Allen");
	S2.push("Chris");
	while (!S2.empty()) { //pop元素直到堆叠为空
		string e = S2.top();
		std::cout << e << " ";
		S2.pop();
	}

};