算法基础（三）——栈
栈的抽象数据类型
从数据的逻辑结构的角度看，栈是线性结构的，也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，是一种操作受限的线性表。但从抽象数据类型角度来看，栈是和线性表大小不相同的，由于它广泛应用于各种系统软件中，所以是一类非常重要的抽象数据类型。
栈是限制在表的一段进行插入和删除运算的线性表，通常称允许进行插入，删除的一端为栈顶，另一端为为栈底。当表中没有元素时称为空栈。、
栈的示意图如下：
由图可知，栈有着这样一个特点：先进后出，因此栈又称先进后出的线性表。
栈的顺序存储结构
栈的顺序存储结构简称为顺序栈。顺序栈是利用一组地址连续存储单元依次存放自栈底到栈顶的数据元素，同时用一个变量top记录栈顶的位置，通常称此变量为栈顶指针。
顺序栈的类型定义
#defineStackSize20//顺序栈的初始分配空间
typedefstringElemType;
typedefstruct
{
ElemTypedata[StackSize];//保存栈中元素
inttop;//栈顶指针
}SqStack;
由于数组下表的约定从0开始，因此用top=-1表示栈空。
如下列图，栈中数据元素金和栈顶指针之间的对应关系。
栈基本运算在顺序栈上的实现
//初始化栈
voidInitStack(SqStackst)
{
st.top=-1;
}
//进栈运算
intPush(SqStackst,ElemTypee)
{
if(st.top==StackSize-1)//判断栈满
return0;
else
{
st.top++;
st.data[st.top]=e;
return1;
}
}
//出栈运算
intPop(SqStackst,ElemTypee)
{
if(st.top==-1)//判断栈空
return0;
else
{
e=st.data[st.top];
st.top--;
return1;
}
}
//取栈顶元素运算
intGetTop(SqStackst,ElemTypee)
{
if(st.top==-1)
return0;
else
{
e=st.data[st.top];
return1;
}
}
顺序栈的应用举例
将非负的十进制数转换为其他进位制的输出数，10及其以上的数字用‘A’开始的字母表示。思路：根据进位制的转化公式（取余数的倒序），因此选用栈的数据结构。
程序如下：
#includeiostream
usingnamespacestd;
#defineMaxSize
typedefcharElemType;
typedefstruct
{
ElemTypedata[MaxSize];
inttop;
}SqStack;
inttrans(intd,intb,charstring[])//string用于存放转换后的字符串
{
SqStackst;
charch;
intr,i=0;
st.top=-1;
if(b=1
b36
b==10)//转换的进位制范围尽在2到36，且不为10
{
cout错误指令;
return0;
}
while(d!=0)
{
r=d%b;//求余数
ch=r+(r10?0:A-10);//将余数转换为相应的字符
st.top++;
st.data[st.top]=ch;//进栈
d/=b;
}
while(st.top!=-1)
{
string[i++]=st.data[st.top];//将出栈的字符放入字符串数组中
st.top--;
}
string=/0;//加入字符串结束标志，输出后的数字，最后的0为结束标志
return1;
}
voidmain()
{
charstr[10];
intd,b,t;
cout输入需要转化的整数：;
cind;
cout输入待转换的进位制：;
cinb;
t=trans(d,b,str);
if(t==0)
cout错误输入;
else
coutstrendl;
}