栈的增长方向永远是从杯底到杯顶，所以对于栈来说上面是栈底下面是栈顶，而对于堆来说，上面是堆顶下面是堆底。栈是连续分配内存的，如果给一个数组或对象分配内存，栈会选择还没分配的最小的内存地址给数组，在这个内存块中，数组中的元素从低地址到高地址依次分配。所以数组中第一个元素的其实地址对应于已分配栈的最低地址。最后，栈只能获取栈顶的内存地址，所以如果栈是从高地址往低地址扩展的话，正好栈顶指向数组的起始地址，即数组的指针。
栈(Stack)
栈的基本概念
定义
只允许在一端进行插入或删除操作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一段进行插入和删除操作。
栈顶（Top）：线性表允许进行插入和删除的一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素。
如上图：a1为栈底元素，an为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1，a2，... ,an 而出栈次序为an，...，a2，a1。栈的明显的操作特征为后进先出（Last In First Out，LIFO）,故又称 后进先出的线性表。
栈的基本操作
1）InitStack（&S）：初始化空栈S
2）StackEmpty（S）：判断一个栈是否为空
3）Push（&S，x）：进栈，若栈未满，则将x加入使之成为新栈顶
4）Pop（&S，&x）：出栈，若栈非空，则将栈顶元素，并用x返回
5）GetTop(S，&x)：读栈顶元素，若栈顶元素非空，则用x返回栈顶元素
6）DestroyStack(&S)：销毁栈，并释放栈S占用的存储空间
栈的顺序存储结构
顺序栈的实现
采用顺序存储的栈称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。
栈的顺序存储类型可以用以下表示：
#define MAXSIZE 100 //栈中元素的最大个数
typedef struct {
ElemType data[MAXSIZE]; //存放栈中元素
int top; //栈顶指针
} SqStack;
栈顶指针：S.top，初始时设置S.top = -1；栈顶元素：S.data[S.top]；
进栈操作：栈不满时，栈指针加1，再送值到栈顶元素
出栈操作：栈非空时，先去栈顶元素值，再将栈顶指针减1
栈空条件：S.top == -1
栈满条件：S.top == MAXSIZE - 1
栈长：S.top + 1
顺序栈的基本运算
初始化
void InitStack(SqStack& S){
S.top = -1; //初始化栈顶指针
}
判栈空
bool StackEmpty(SqStack& S){
if( S.top == -1){
return true;
}
return false;
}
进栈
bool Push(SqStack& S, ElemType x){
if( S.top == MAXSIZE - 1 ){ //栈满，报错
return false;
}
S.top ++ ; //栈顶指针加1
S.data[S.top] = x; //入栈
return true;
}
出栈
bool Pop(SqStack& S, ElemType& x){
if( S.top == -1 ){ //栈空，报错
return false;
}
x = S.data[S.top];
S.top --;
return true;
}
读栈顶元素
bool GetTop(SqStack& S,ElemType& x){
if( S.top == -1 ){ //栈空，报错
return false;
}
x = S.data[S.top];
return true;
}
注意：若栈顶指针初始化为S.top = 0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为S.data[S.top++]，出栈操作为x = S.data[--S.top]。因为栈顶指针若初始化为 0 时，则栈顶指针始终指向顺序栈将要入栈的位置，也就是栈顶指针的下标就是入栈元素的下标。
共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top1 = -1 时，stack1 为空，top2 = MAXSIZE - 1 时，stack2 为空；仅当两个栈顶指针相邻（top1 - top2 == 1)时，判断栈满。当stack1进栈时top1先加1再赋值，stack2进栈时top2先减1再赋值；出栈正好相反。
共享栈是为了更有效地利用存储空间，两个栈的空间正好互相调节，只有在整个存储空间被占满时才发生上溢。存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。
栈的链式存储结构
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，top指向栈顶元素，
链栈的存储类型可描述为：
typedef struct LinkNode{
ElemType data;
struct LinkNode* next;
}LinkNode, *LinkStack;
