【数据结构——栈篇】

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

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++;//栈顶指针+1return OK;
}

4、顺序栈出栈

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

Status Pop(SqStack& S, SElemType& e)
{if (S.top == S.base)return ERROR;//栈空报错--S.top;//栈顶指针-1e = *S.top;//获取栈顶元素ereturn 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");elsefor (p = S.top - 1;p >= S.base;p--)printf("%d\n", *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;//将新结点数据域置为ep->next = S;//将新结点插入栈顶S = p;//修改栈顶指针为preturn 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("空栈！");elsewhile (p){printf("%d", p->data);p = p->next;}
}