数据结构：栈的基本概念、顺序栈、共享栈以及链栈

相关概念

栈(Stack)是只允许在一端进行插入或删除操作的线性表。
栈顶(Top)：线性表允许插入删除的那一端。
栈底(Bottom)：固定的，不允许进行插入和删除的另一端。

栈的基本操作

• InitStack(&S)：初始化一个空栈S。
• StackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回false。
• Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
• Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
• GetTop(S,&x)：读栈顶元素，但不出栈，若栈S非空，则用X返回栈顶元素。
• DestoryStack(&S)：销毁栈，并释放栈S所占用的存储空间。

栈的数学性质：当\(n\)个不同元素进栈时，出栈元素的不同排列的个数为\(C^n_{2n}/(n+1)\)。该公式称为卡特兰数(Catalan)公式，可采用数学归纳法证明。

顺序栈

#define MaxSize 50
typedef int Elemtype;

typedef struct {
	Elemtype data[MaxSize];
	int top;
} SqStack;


void InitStack(SqStack& S) {
	S.top = -1;
}

bool StackEmpty(SqStack S) {
	if (S.top = -1)
		return true;
	else
		return false;
}

bool Push(SqStack& S, Elemtype x) {
	if (S.top == MaxSize - 1)
		return false;
	S.data[++S.top] = x;
	return true;
}

bool Pop(SqStack& S, Elemtype& x) {
	if (S.top == -1)
		return false;
	x = S.data[S.top--];
	return true;
}

bool GetTop(SqStack& S, Elemtype& x) {
	if (S.top == -1)
		return false;
	x = S.data[S.top];
	return true;
}