【数据结构——栈篇】

一、栈的顺序存储——顺序栈

1、顺序栈的表示和实现

因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需要一个变量top来指示当前栈顶的位置，通常称top为栈顶指针。

2、顺序栈的定义

#define MAXSIZE 100 typedef struct {  SElemType* base;//栈底指针  SElemType* top;//栈顶指针 int stacksize;//可使用的最大容量 }SqStack;  SqStack S;//定义顺序栈 S.stacksize = s;//栈的大小 S.base == S.top;//空栈 S.top - S.base == stacksize;//满栈 

2、顺序栈初始化

算法思想：
1、分配空间并检查空间是否分配成功，否则返回错误
2、栈顶指针top初始化为栈底指针base
3、stacksize = 栈的最大容量

Status IniStack(SqStack& S) {  S.base = new SElemType[MAXSIZE];//分配空间 if (!S.base) exit(OVERFLOW);//分配失败，返回错误  S.top = S.base;//栈顶指针初始化为栈底指针  S.stacksize = MAXSIZE;//初始化栈的最大容量 return OK; } 

3、顺序栈入栈

算法思想
1、判断是否栈满，若满则出错
2、新元素e压入栈顶
3、栈顶指针+1

Status Push(SqStack& S, SElemType e) { if (S.top - S.base == S.stacksize) return ERROR;//栈满 *S.top = e;//新元素e压入栈顶  S.top++;//栈顶指针+1 return OK; } 

4、顺序栈出栈

算法思想
1、判断是否栈空，若空则出错
2、栈顶指针-1
3、获取栈顶元素e

Status Pop(SqStack& S, SElemType& e) { if (S.top == S.base) return ERROR;//栈空报错 --S.top;//栈顶指针-1  e = *S.top;//获取栈顶元素e return OK; } 

5、取顺序栈栈顶元素

SElemType GetTop(SqStack S) { if (S.top != S.base)//栈非空 return *(S.top - 1);//返回栈顶元素的值 //栈顶指针不变 } 

6、输出栈内容

void OutPut_SqS(SqStack S) {  SElemType* p; if (S.top == S.base) printf("空栈！n"); else for (p = S.top - 1;p >= S.base;p--) printf("%dn", *p); } 

二、栈的链式存储——链栈

1、链式存储方式表示的栈称链栈
2、运算受限的单链表
3、链表的头指针就是栈顶
4、不需要头结点
5、插入与删除仅在栈顶执行

1、链栈的存储结构

typedef struct StackNode {  SElemType data; struct StackNode* next; }StackNode,*LinkStack;  LinkStack S; 

2、栈链的初始化

算法思想：
1、不需要头结点
2、链栈的头指针就是栈顶
3、栈链无栈满问题，空间可扩充
4、空栈相当于头指针指向NULL

Status IniStack(LinkStack& S) {//构造一个空栈，栈顶指针置空  S = NULL; return OK; } 

3、链栈的入栈

算法思想：
1、为入栈元素e分配空间，用指针p指向
2、将新结点指针域置为e
3、将新结点插入栈顶
4、修改栈顶指针为p

Status Push(LinkStack& S, SElemType e) {  p = new StackNode;//生成新结点  p->data = e;//将新结点数据域置为e  p->next = S;//将新结点插入栈顶  S = p;//修改栈顶指针为p return OK; } 

4、链栈的出栈

算法思想：
1、判断是否是空栈，若是空栈，返回错误
2、将栈顶元素赋值给e
3、临时保存栈顶元素的空间，以备释放
4、修改栈顶指针，指向新的栈顶元素
5、释放原栈顶元素的空间

Status Pop(LinkStack& S, SElemType& e) { if (S == NULL) return ERROR;//栈空  e = S->data;//将栈顶元素存储到e中  p = S;//用p临时保存栈顶元素的空间，以备释放  S = S->next;//修改栈顶指针 delete p;//释放原栈顶元素的空间 return OK; } 

5、取链栈栈顶元素

SElemType GetTop(LinkStack S) { if (S != NULL) return S->data; } 

6、输出链栈的内容

void OutPut(LinkStack S) {  p = S; if (!p) printf("空栈！"); else while (p) { printf("%d", p->data);    p = p->next; } }