相关概念
栈(Stack)是只允许在一端进行插入或删除操作的线性表。
栈顶(Top):线性表允许插入删除的那一端。
栈底(Bottom):固定的,不允许进行插入和删除的另一端。
栈的基本操作
InitStack(&S)
:初始化一个空栈S。StackEmpty(S)
:判断一个栈是否为空,若栈S为空则返回true,否则返回false。Push(&S,x)
:进栈,若栈S未满,则将x加入使之成为新栈顶。Pop(&S,&x)
:出栈,若栈S非空,则弹出栈顶元素,并用x返回。GetTop(S,&x)
:读栈顶元素,但不出栈,若栈S非空,则用X返回栈顶元素。DestoryStack(&S)
:销毁栈,并释放栈S所占用的存储空间。
栈的数学性质:当\(n\)个不同元素进栈时,出栈元素的不同排列的个数为\(C^n_{2n}/(n+1)\)。该公式称为卡特兰数(Catalan)公式,可采用数学归纳法证明。
顺序栈
#define MaxSize 50
typedef int Elemtype;
typedef struct {
Elemtype data[MaxSize];
int top;
} SqStack;
void InitStack(SqStack& S) {
S.top = -1;
}
bool StackEmpty(SqStack S) {
if (S.top = -1)
return true;
else
return false;
}
bool Push(SqStack& S, Elemtype x) {
if (S.top == MaxSize - 1)
return false;
S.data[++S.top] = x;
return true;
}
bool Pop(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;
}
标签:return,SqStack,Elemtype,top,链栈,false,数据结构,true,基本概念
From: https://www.cnblogs.com/SXWisON/p/18314847