|
目录
一、栈的概念:
栈是一种只允许在一端插入与删除的线性表,操作受限。只允许插入与删除操作的一端为栈顶，另一端为栈底。栈的操作通常为“入栈或进栈”、“出栈或退栈”。当栈中无数据元素时为空栈。栈的特点是：先进后出也就是后进先出。
二、栈的运算：
1.InitStack(S)初始化：初始化一个新的栈
2. Empty(S)栈的非空判断：若栈不空返回TRUE，否为FALSE
3. Push(S,x)入栈：在栈顶的头部插入元素，若栈满返回FALSE
4. Pop（S）出栈：若栈不空，返回栈顶元素，并且删除该元素
5.GetTop（S）取出栈顶元素：若栈不空，返回栈顶元素，否则返回NULL
6.SetEmpty（s)置栈空操作：使栈为空栈。
需要注意：
(1)进栈前需要判断栈是否满
（2）出栈和取栈顶元素时判断栈是否为空
（3）出栈与取栈顶元素的不同在于，出栈是返回数据元素的同时，栈顶指针移动到下一位置。取栈顶元素是并不改变栈顶指针的位置，返回栈顶数据元素。
三、栈的顺序存储结构
类似顺序表的操作，栈中需要预设一个足够长度的存储空间，ElemType elem[MAXSIZE]，栈底的位置可以设置在数组的端点，定义一个int top 作为栈顶的指针，指明当前的位置。
(1)栈的初始化操作
typedef struct //定义一个结构
{
ElemType elem[MAXSIZE];
int top;
}Sepstack;
Sepstack InitStack()
{
Sepstack* s;
s = (Sepstack*)malloc(sizeof(Sepstack));
s->top = -1; //栈顶指针初始化，此时为空栈
return s;
}
（2）判空栈
int Empty(Sepstack* s)
{
if (s->top == -1)
return 1; //判断栈为空
else
return 0;
}
（3）入栈
int Push(Sepstack* s, ElemType x) //Elem自定义一个数据类型
{
if (s->top == MAXSIZE - 1) //判断栈满，栈满不能入栈
return 0;
else
{
s->top++; //先使栈顶指针移动到下一个位置接受数据元素
s->elem[s->top] = x;
rerurn 1;
}
}
（4）出栈
int Pop(Sepstack* s,ElemType*x)
{
if (s->top == -1)
return 0;
else
{
*x = s->elem[s->top]; //定义一个指针用于接受栈顶元素
s->top--; //出栈，栈顶指针减一
return 1;
}
}
（5）取栈顶元素
int Get(Sepstack* s)
{
if (s->top == -1) //判断栈是否为空栈
return 0;
else
return s->elem[s->top];
}
（6）遍历出栈
void Traver(Sepstack* s)
{
while (s->top != -1)
{
printf("%d", s->elem[s->top]); //此时一整形数据元素举例
s - > top--;
}
}
四、多栈共享邻接空间
让多个栈共用一个足够大的连续存储空间，利用栈的动态特性使存储空间互补。
两栈共享为例：
(1)初始化操作
typedef struct
{
ElemType elem[MAXSIZE];
int lefttop; //定义一个指向左栈的栈顶指针
int righttop;
}Sepstack;
Sepstack InitStack()
{
Sepstack* s;
if(s = (Sepstack*)malloc(sizeof(Sepstack))==NULL); //判断申请栈的空间是否成功
return FALSE;
s->lefttop = -1; //让一个栈的栈顶在左边，初始化为数组的端点-1
s->righttop = MAXSIZE; //右边的栈，初始化为数组下标最大值+1。
return s;
}
（2）入栈
int Push(Sepstack* s, ElemType x, char status) //char 是选择将x压入左栈还是右栈
{
if (s->lefttop + 1 == s->righttop) // 判断栈是否满
return 0;
if (status == 'L')
{
s->elem[++s->lefttop++] = x; //压栈时左栈栈顶指针先移动下一个空间
}
if (status == 'R')
{
s->elem[--s->righttop] = x; //右端压栈时向左移动空间减一
}
return TURE;
}
（3）出栈
int Pop(Sepstack* s,char status)
{
if (status == 'L')
{
if (s->lefttop <0) //判断左栈是否为空
return 0;
else
return s->elem[s->lefttop--]; //左栈出栈是方向向左
}
if (status == 'R')
{
if (s->righttop > MAXSIZE-1) //判断右栈是否为空
return 0;
else
return s->elem[s->righttop++]; //右栈出栈方向与左栈相反
}
else
return NULL;
}
五、栈的链式存储结构
避免申请的存储空间过小导致栈满（上溢），可以使用链式存储结构，让多个栈共享存储空间。采用链式存储结构同时满足先进后出的特点，及数据元素进栈时需要采用头插法php指针，栈的进栈和出栈都只允许在一端。所以链栈中的第一个元素即栈顶，最后一个为栈底。
（1）链栈初始化
typedef struct Stacknode
{ //定义一个结构
Datatype data;
struct Stacknode* next;
}Slstacktype;
Slstacktype* Initslstack()
{
Slstacktype* top; //对栈顶指针初始化
top = (Slstacktype*)malloc(sizeof(Slstacktype));
top->next = NULL;
return top;
}
（2）入栈
int Pushtack(Slstacktype*top,Datatype x)
{
Slstacktype* p; //申请一个新的结点
if(p = (Slstacktype*)malloc(sizeof(Slstacktype))==NULL)
return FALSE;
p->data = x;
p->next = top->next;
top->next = p;
return TRUE;
}
（3）出栈
Datatype Pop(Slstacktype* top)
{
Slstacktype* p;
Datatype x;
if (top->next == NULL) //出栈判断是否为空栈
return;
p = top->next;
x = p->data;
top->next = p->next;
free(p);
return x;
}
（4）多个链栈的操作
多个链栈操作，是指将多个单链栈的栈顶指针放在一个一维数组中统一管理（也就是指针数组），及通过一维数组下标就可找到每个单链栈的栈顶指针，就能找到单链栈并且进行操作，定义一个链栈Slstacktype*top[M]。
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
