数据结构（四）：栈
一、栈的定义
栈是只能在一端进行插入和删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的位置是动态的，由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。
当栈中没有元素时，称为空栈。栈的插入操作通常称为入栈或者进栈，栈的删除操作一般称作出栈或者退栈。
栈的主要特点是 ”后进先出“ ，即后进栈的元素先出栈。每次进栈的元素都放在原来栈顶元素之前，成为新的栈顶元素，每次出栈的元素都是当前栈顶元素。所以栈也被称为后进先出表。
栈的抽象数据类型定义如下：
ADT List
{
数据对象：
D={a(i)|1=<i<=n, a(i)是 ElemType类型}
数据关系：
R={<a(i), a(i+1)>|a(i),a(i+1)属于 D, i=1,2,3,···,n-1}
基本运算：
InitStack(&s): 初始化栈，构建一个空栈 s
ClearStack(&s): 销毁栈：释放栈 s所占的内存空间
StackLength(s): 求栈的长度: 返回栈 s中的元素个数
StackEmpty(s): 判断栈是否为空：若栈 s为空则返回真，否则返回假
Push(&s, e): 进栈：将元素 e添加到栈顶
Pop(&s, &e): 出栈：将栈顶元素赋值给 e并从栈顶删除
GetTop(s, &e): 取栈顶元素：将当前栈顶元素的值赋值给 e
DispStack(s)：显示栈中所有元素的值：按照从栈顶到栈底的顺序显示栈中所有元素的值
}
二、栈的顺序存储结构与基本运算
使用顺序存储结构存储栈时，我们会分配一块连续的内存空间来存放栈中的元素，并用一个变量指向当前的栈顶。采用顺序存储结构的栈称为顺序栈。
定义顺序栈的结合体时，我们假设栈能够存储的最大元素数量为 MaxSize，指向栈顶的变量为 STop（在顺序存储结构中 STop是一个整数，表示当前栈顶元素的下标），存放栈中元素的数组 data。
所以我们可以定义栈的结构体为：
#define MaxSize 100
typedef char ElemType;
typedef struct Stack{
int STop;
ElemType data[MaxSize];
}Stack;
这里栈的最大大小我们通过宏来定义，在实现时也可以使用其他的方法定义，比如在栈中再加一个 MaxSize，data改为一个 ElemType[] 类型的指针，在初始化栈时，通过 malloc函数读取 MaxSize来为 data分配内存。
1、栈的初始化
void InitStack(Stack* &s) {
s = (Stack*)malloc(sizeof(Stack));
s->STop = -1;
}//InitStack
在初始化函数里我我们把 s->STop赋值为 -1，以此来标记栈 s是空栈。
也可以把 STop赋值为 0，这与 -1区别不大，只是当初始化为 -1时 STop总是指向栈顶元素，而初始化为 0时 STop总是指向栈顶元素的前一位。
2、销毁栈
void ClearStack(Stack* &s) {
free(s);
s = NULL;
}//ClearStack
3、求栈的长度
int StackLength(Stack* s) {
return s->STop + 1;
}//StackLengt
这里我们返回 STop+1是因为 STop总是指向栈顶元素，而栈顶元素的下标就是数组元素个数减一。
当 STop初始化为 0时我们就可以直接返回 STop。
4、判断栈是否为空
bool StackEmpty(Stack* s) {
if (s->STop < 0) {
return true;
}
else{
return false;
}
}//StackEmpty
5、进栈
void Push(Stack* &s, ElemType e) {
s->STop++;
if (s->STop > MaxSize || s->STop < 0) {
throw;
}
else{
s->data[s->STop] = e;
}
}//Push
6、出栈
void Pop(Stack* &s, ElemType &e) {
if (!StackEmpty(s)) {
e = s->data[s->STop];
s->STop--;
}
else {
throw;
}
}//Pop
7、取栈顶元素
void GetTop(Stack* s, ElemType &e) {
if (!StackEmpty(s)) {
e = s->data[s->STop];
}
else {
throw;
}
}//GetTop
8、打印栈
void DispStack(Stack* s) {
if (StackEmpty(s)) {
printf("stack is empty.\n");
}
else {
int top = s->STop;
while (top >= 0) {
printf("index: %d, value: %c\n", top, s->data[top]);
top--;
}
}
}//DispStack
三、栈的链式存储结构与基本运算
栈的链式存储结构叫做链栈，通常用单链表实现。链栈的有点是不用考虑满栈的情况，操作也很方便，我们只要在头节点处操作就行。最靠近头节点的节点是栈顶节点，而链表中与头节点相对的一端则是栈底。
链栈中节点的结构定义如下：
typedef char ElemType;
typedef struct LinkStack {
ElemType data;
struct LinkStack* next;
}LinkStack;
1、链栈的初始化
void InitStack(LinkStack* &s) {
s = (LinkStack*)malloc(sizeof(LinkStack));
s->next = NULL;
}
2、销毁链栈
void ClearStack(LinkStack* &s) {
while(s->next != NULL) {
LinkStack* temp = s->next->next;
free(s->next);
s->next = temp;
}
free(s);
s = NULL;
}
3、求链栈的长度
int StackLength(LinkStack* s) {
int i = 0;
while (s->next != NULL) {
i++;
s->next = s->next->next;
}
return i;
}
4、判断链栈是否为空
bool StackEmpty(LinkStack* s) {
return s->next == NULL;
}
5、进栈
void Push(LinkStack* &s, ElemType e) {
LinkStack* new_node = (LinkStack*)malloc(sizeof(LinkStack));
if (new_node == NULL) {
throw;
}
new_node->data = e;
new_node->next = s->next;
s->next = new_node;
}
链栈进栈与单链表添加节点很相似，只是链栈进栈时我们只在头节点后面添加节点，而单链表则可以在链表的任意位置添加节点。
6、出栈
void Pop(LinkStack* &s, ElemType &e) {
if (StackEmpty(s)) {
throw;
}
LinkStack* temp = s->next;
e = temp->data;
s->next = temp->next;
free(temp);
}
7、取栈顶元素
void GetTop(LinkStack* s, ElemType &e) {
if (StackEmpty(s)) {
throw;
}
e = s->next->data;
}
8、打印栈
void DispLStack(LinkStack* s) {
LinkStack* temp = (LinkStack*)malloc(sizeof(LinkStack));
*temp = *s;
int i = 0;
while (temp->next != NULL) {
i++;
printf("index: %d, value: %c\n", i, temp->next->data);
temp->next = temp->next->next;
}
}
这里使用一个 temp作为中间变量是为了避免直接修改 s所指向的内存。
