栈和队列（1）——栈

栈的基本概念

1. 栈的定义：只允许在一端进行插入或删除操作的线性表（可以理解为操作受限的线性表）。

2. 栈的特点：后进先出（LIFO）。

3. 栈的基本操作：初始化、销毁、进栈、出栈、读栈顶元素等。

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

栈的常考题型：进栈顺序与出栈顺序的关系。

n个不同的元素进栈，出栈元素不同排列的个数为

栈的顺序存储实现（顺序栈）

顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)。

顺序栈的定义

#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; //静态链表中存放栈中元素int top; //指向栈顶元素
} SqStack;

我们通过top的值指向栈顶元素，即top的范围数组索引值[0,n-1]。因此如果栈是空栈，就令top=-1。

顺序栈的初始化与判断栈空

void InitStack(SqStack &S){S.top==-1; //初始化栈顶指针
}
bool StackEmpty(SqStack S){if(S.top==-1)return true;elsereturn false;
}

新元素入栈

bool PushStack(SqStack &S,ElemType x){if(S.top==MaxSize-1) //判断是否满栈return false;S.data[++S.top]==x;return true;
}

由于S.top是索引指向当前的栈顶位置，因此S.data[++S.top]==x，而不是S.data[S.top++]==x。对于后者我们可以采取另一种方式——让top指向下一个可以插入的位置，这时需要将top初始化为0，判断栈满的条件也变成了：top==MaxSize。

出栈

bool PopStack(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;
}

顺序栈的缺点：栈的大小不可变。

共享栈

共享栈：两个栈共享同一片存储空间，这片存储空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间；
两个栈的栈底在这片存储空间的两端，当元素入栈时，两个栈的栈顶指针相向而行。

栈满的条件：top0+1=top1；(top是int类型，是数组的索引值)

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top0; //0号栈栈顶指针int top1; //1号栈栈顶指针
} ShStack;
void InitStack(ShStack &S){S.top0=-1;S.top1=MaxSize;
}

链栈

1. 栈的链式存储实现通过单链表模拟，进栈采用头插法。

2. 出栈操作对应单链表的删除操作，需对头结点进行“后删”处理。

3. 链栈定义及初始化，带头结点的链栈便于操作。

#include<stdlib.h>
#include<stdio.h>#define MAXSIZE 10typedef int ElemType;typedef struct Linknode {ElemType data;struct Linknode*next;
}*LiStack;

带头结点的链栈

//初始化
void InitLiStack(LiStack &s){s=(Linknode*)malloc(sizeof(Linknode));if(s==NULL){printf("内存分配失败!\n");return ;}s->next=NULL;printf("空间申请成功!\n");
} //销毁
void DestryLiStack(LiStack &s){Linknode* p=s->next;while(p!=NULL){Linknode* r=p;p->next=r->next;free(r);}free(s);printf("销毁成功!\n");
} //入栈
void PushLiStack(LiStack &s,ElemType e){Linknode* r=(Linknode*)malloc(sizeof(Linknode));r->data=e;r->next=s->next;s->next=r;printf("插入节点成功!\n"); 
} //出栈
void PopLiStack(LiStack &s,ElemType &e){if(s->next==NULL){printf("栈空!\n");return;}Linknode* p=s->next;e=p->data;s->next=p->next;free(p);printf("出栈成功!\n"); 
} //获取栈顶节点
Linknode* GetElem(LiStack &s,ElemType &e){if(s->next==NULL){printf("栈空!\n");return NULL;}Linknode* p=s->next;e=p->data;
} 

不带头结点的链栈

//初始化
void InitLiStack(LiStack &s){s=NULL;printf("申请空间成功!\n"); 
} //销毁
void DestryLiStack(LiStack&s){Linknode* p=s;while(p->next!=NULL){Linknode* r=p;p=r->next;free(r);}//最后一个节点特殊处理free(p); printf("销毁成功!\n");
} //入栈
void PushLiStack(LiStack &s,ElemType e){//如果开始没有节点，特殊处理 if(s==NULL){Linknode* r=(Linknode*)malloc(sizeof(Linknode));r->data=e;r->next=NULL;s=r;printf("插入节点成功!\n"); return ; } Linknode* r=(Linknode*)malloc(sizeof(Linknode));//首先将头结点的值修改为要插入的值e，将r->data=s->data,最后直接在头结点后面插入节点r即可 r->data=s->data;s->data=e;r->next=s->next;s->next=r;printf("插入节点成功!\n"); 
} //出栈
void PopLiStack(LiStack &s,ElemType &e){if(s==NULL){printf("栈空!\n");return;}//只有一个节点的时候特殊处理 if(s->next==NULL){e=s->data; free(s);return ;} Linknode* p=s;e=p->data;s->next=p->next;free(p);printf("出栈成功!\n"); 
} //获取栈顶节点
Linknode* GetElem(LiStack &s,ElemType &e){if(s==NULL){printf("栈空!\n");return NULL;}Linknode* p=s;e=p->data;
}