栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶（ top)，另一端称为栈底（bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
理解栈的定义需要注意:
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得:栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫作进栈，也称压栈、入栈。
栈的删除操作，叫作出栈，也有的叫作弹栈。

栈的抽象数据类型

ADT 栈（stack)
DATA 同线性表
OPERATION 
	Init_Stack(*S);//初始化操作
	Destroy_Stack(*S);//摧毁一个栈
	Clear_Stack(*S);//清空一个栈
	IsEmpty_Stack(*S);//判空
	Top_Stack(*S);//非空，则返回栈顶
	Pop_Stack(*S);//弹出栈顶
	Push_Stack(*S,e);//压入一个数据
	Size_Stack(*S);//返回栈大小

由于栈是一个表，因此任何实现表的方法都能实现栈。99%的情况下，它们都是最合理的选择。有时候为特殊目的而设计的实现可以运行得更快。由于栈的所有操作都是常量时间的操作，所以，除非是在很特别的环境下，否则不太可能会有明显的改进。

除此之外，我们也可以在对顺序表进行二次封装来实现栈。

这里我们选择稍微修改顺序表的代码来实现

栈的数组实现

结构体定义

#define INITSIZE 20  //初始化的大小
#define EXPANDTIMES 2 //每次的扩容倍数
typedef int ELemType;//用int来模拟数据项类型
typedef struct
{
	ELemType* data; //存储数据的初始位置
	int capacity; //容量（总共的:未使用的+已经使用的）
	int size;//已经使用的
}Stack;

可以把栈看作一个立起来的数组，我们只能操作最后一个元素。

初始化

bool Init_Stack(Stack* S)
{
	assert(S != NULL);//对输入也检测一下，使用空指针可能会导致程序奔溃，具体原因自己去搜，后续不解释
	S->data = (int*)malloc(sizeof(ELemType) * INITSIZE);//申请一段堆空间来存储元素
	//assert(L->data != NULL);//因为malloc可能会申请失败，判断一下
	if (S->data == NULL)
	{
		return false;
	}
	else
	{
		S->capacity = INITSIZE;//初始容量通过宏定义设定
		S->size = 0;//初始使用的大小当然是0喽
		return true;
	}
}

判空

bool IsEmpty_Stack(Stack* S)
{
	assert(S != NULL);
	return S->size == 0;//只用检测一下使用的大小为不为0，就ok
}

清空

bool Clear_Stack(Stack* S)
{
	assert(S != NULL);
	free(S->data);//因为空间是malloc来的，不用就free掉
	Init_Stack(S);//最简单的做法，重新给他初始化下，就消除了数据，也缩小了容量
	//S->size = 0;//最最最简单的方法因为数据是否有效，我们说了算，容量没变
	return true;
}

摧毁

bool Destroy_Stack(Stack* S)
{
	S->capacity = 0;
	S->size = 0;
	free(S->data);//Destroy以后就彻底不能用了，因为0乘以任何数还是0
	S->data = NULL;
	return true;
}

返回栈顶

ELemType Top_Stack(Stack* S)
{
	assert(S != NULL);
	if (S->size == 0)
	{
		printf(" stack is empty \n");
		return -1;
	}
	return S->data[S->size-1];
}

弹出栈顶

bool Pop_Stack(Stack* S)
{
	assert(S != NULL);
	S->size = S->size == 0 ? 0 : S->size - 1;
	if (S->capacity > INITSIZE && S->size < S->capacity / EXPANDTIMES)
		Change_Stack(S, -1);
	return true;
}

压入

bool Push_Stack(Stack* S, ELemType e)
{
	assert(S != NULL);//为满足线性表的定义，应对下标进行检测
	if (S->capacity == S->size)
	{
		if (!Change_Stack(S, 1))
		{
			return false;
		}
	}
	S->data[S->size] = e;
	S->size++;
	return true;
}

大小

int Size_Stack(Stack* S)
{
	assert(S != NULL);
	return S->size;
}

栈的链表实现

我使用的带头结点，图可能有些出入

typedef int ELemType; //用int来模拟数据项类型

typedef struct Node//数据节点/头节点公用
{
	ELemType data;
	struct Node* next;
}Stack;

初始化

bool Init_Stack(Stack* S)
{
	assert(S != NULL);
	S->data = 0;//头节点的数据项我们拿来存大小/长度
	S->next = NULL;
	return true;
}

判空

bool IsEmpty_Stack(Stack* S)//线性表为空则返回true,否则false
{
	assert(S != NULL);
	return S->data == 0;
}

清空

bool Clear_Stack(Stack* S)//清空L;
{
	while (!IsEmpty_Stack(S))
	{
		Pop_Stack(S);
	}
	return true;
}

返回栈顶

ELemType Top_Stack(Stack* S)
{
	assert(S != NULL);
	if (S->data == 0)
	{
		printf("Stack is Empty\n");
		return -1;
	}
	else
	{
		return S->next->data;
	}
}

弹出栈顶

bool Pop_Stack(Stack* S)
{
	assert(S != NULL);
	if (S->data == 0)
	{
		return true;
	}
	else
	{
		S->data = S->data - 1;
		Node* pt = S->next;
		S->next = pt->next;
		free(pt);
		return true;
	}
}

压入

bool Push_Stack(Stack *S, ELemType e)
{
	assert(S != NULL);
	Node* temp = (Node*)malloc(sizeof(Node));
	if (temp == NULL)
	{
		return false;
	}
	else
	{
		S->data++;
		temp->next = S->next;
		temp->data = e;
		S->next = temp;
		return true;
	}
}

大小

int Size_Stack(Stack* S)
{
	assert(S != NULL);
	return S->data;
}