首页 > 代码库 > 栈的笔记（2）--顺序栈
栈的笔记（2）--顺序栈
顺序栈是利用一组地址连续的储存单元依次存放栈顶到栈底的数据元素，同时，还必须附加一个指针top（栈顶指针），来动态储存栈顶元素在顺序战中的位置。（通常，top=-1表示空栈）
储存结构如下：
#define Stack_Size 50//设栈中的元素为50
typedef struct {
StackElementType elem[Stack_Size];//用来存放栈中元素的一维数组
int top;//用来存放栈顶元素的下标，top为-1时，表示栈为空
}SeqStack;
初始化顺序栈
void InitStack(SeqStack *S)
{
S->top=-1;//构建一个空栈S,栈顶为空
}
进栈（先判断栈是否为满，如果为满，返回FALSE）
int Push(SeqStack *S,StackElementType x)
{
if(S->top==Stack_size-1)//栈已满
return (FALSE);
S->top++;
S->elem[S->top]=x;
return(TRUE);
}
出栈(先判断栈是否为空,若为空，返回FALSE)
int Pop(SeqStack *S,StackElementType *x)
{
if(S->top==-1)//栈为空
return(FALSE);
else{
*x=S->elem[S->top];//把栈顶元素放到x所指向的存储空间中
S->top--;
return(TRUE);
}
}
读取栈顶元素(先判断栈是否为空,若为空，返回FALSE)
int GetTop(SeqStack *S,StackElementType *x)
{
if(S->top==-1)//栈为空
return(FALSE);
else {
*x=S->elem[S->top];///把栈顶元素放到x所指向的存储空间中
return(TRUE); }
}
多栈共享技术 一个程序使用多个栈时，为防止有的栈溢出，可以 让多个栈共用一个足够大的数组。 最常用的是两个栈的共享技术，即双端栈。他主要利用了“栈底位置不变，栈顶位置动态变化”的特性。 首先，申请一个共享的一维数组S[M],将两个栈的栈底，分别放到一维数组的两端，分别为0，M-1
数据结构定义为：
#define M 100 //假设，两个栈的和用大小为100
typedef struct {
StackElementType Stack[M];
StackElementType top[2];
}DqStack;
双端顺序栈初始化
void InitStack(DqStack *S)
{
S->top[0]=-1;
S->top[1]=M;
}
双端顺序栈进栈（需先判断栈是否为满）
int Push(DqStack *S,StackElementType x,int i)
{
\\把数据元素装入第i号堆栈
if(S->top[0]+1==S->top[1])
return(FALSE);
switch(i) {
case 0: S->top(0)++; S->Stack[S->top[0]]=x; break;
case 1: S->top[1]--; S->Stack[S->top[1]]=x; break;
default: return(FALSE);
}
return(TRUE);
}
双端顺序栈出栈
int Pop(DeStack *S,StackElmentType *x,int i)
{
Switch(i) {
case 0: if(S->top[0]==-1) return(FALSE); *x=S->Stack[S->top[0]]; S->top[0]--; break;
case 1: if(S->top[1]==M) return(FALSE); *x=S->Stack[S->top[1]]; S->top[1]++; break;
default: return(FALSE);
}
return(TRUE);
}
栈的笔记（2）--顺序栈