个人笔记栈的基本操作（初始化，出栈，入栈以及进制转换）

目录

• 栈的一些基本操作
• • 栈的概念(新手必看)
  • 初始化栈
  • 销毁栈
  • 清空栈
  • 判空栈
  • 栈长度
  • 取栈顶元素
  • 入栈操作
  • 出栈操作
  • 输出栈
  • 进制转换

栈的概念(新手必看)

栈（stack）又名堆栈，是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作入栈，就是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈，它是把栈顶元素删除掉，使前一个元素成为新的栈顶元素。

存在两个指针，一个始终指向栈底，叫做栈底指针，一个指向栈顶元素的上一位，叫做栈顶指针。当然，初始时两个指针同时指向栈底。

初始化栈

Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));//申请空间
if(!S.base) exit(OVERFLOW);//如果内存不够，分配空间失败
S.top=S.base;//初始时让栈顶指针和栈底指针同时指向栈底
S.stacksize=STACK_INIT_SIZE;//栈初始容量
return OK;
}


销毁栈

Status DestroyStack(SqStack &S)
{
free(S.base);//释放内存
S.base=S.top=NULL;//指针指向空
S.stacksize=0;//清空栈容量
}


清空栈

Status ClearStack(SqStack &S)
{
S.top=S.base;//让栈顶指针回到最初位置，即栈底元素位置
return OK;
}


判空栈

Status EmptyStack(SqStack &S)
{
if(S.top==S.base)//当栈顶指针指向栈底时，栈为空
return 1;
else
return 0;
}


栈长度

Status LengthStack(SqStack &S)
{
return (S.top-S.base);//这个简单，栈顶指针地址减去栈底指针地址就行了
}


取栈顶元素

Status TopStack(SqStack &S,int &e)
{
if(S.top==S.base)//栈为空，取不了元素
return ERROR;
e=*(S.top-1);//栈顶指针减一后把对应值赋值给e（注意，此时栈顶指针没动）
return OK;
}


入栈操作

Status PushStack(SqStack &S,int e)
{
if(S.top-S.base>=S.stacksize)
{ //栈满的情况，扩容
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;//栈顶指针指向新扩充空间首位
S.stacksize+=STACKINCREMENT;
}
*S.top++ = e;//先把e赋值给栈顶，指针再自加
return OK;
}


出栈操作

Status PopStack(SqStack &S,int &e)
{
if(S.top == S.base) return ERROR;
e= *--S.top;//栈顶指针先自减，再把对应值赋值给e（注意，栈顶指针下移一位了）
return OK;
}


输出栈

Status ShowStack(SqStack S)
{
//cout<<*S.top<
while(S.base!=S.top)//当栈不为空时
cout<<*--S.top<<' ';//栈顶指针先自减，再输出对应值
cout<<endl;
return OK;
}


进制转换

这里只展示10进制转换为任意进制（这里最大只到36进制）
考虑特殊情况
1、为0的情况
2、进制大于10后，对应值应用字母显示
3、负数

//输入
cout<<"输入一个十进制数"<<endl;
cin>>e;
cout<<"输入要转换的进制"<<endl;
int jinzhi;
cin>>jinzhi;
InitStack(J);
cout<<"10进制数"<<e<<"转换为"<<jinzhi<<"进制数后为：";
if(e<0)//负数
{
cout<<'-';//先输出符号‘-’
e=-e;//转换为正数继续执行
}
if(!e)//0
cout<<0;
JinZhi(J,e,jinzhi);
ShowjzStack(J);
break;


//入栈
Status JinZhi(SqStack &S,int e,int jinzhi)
{
while(e)
{
PushStack(S,e%jinzhi);
e/=jinzhi;
}
}


//输出
Status ShowjzStack(SqStack &S)
{
SElemType *p=S.top;
while(!EmptyStack(J))
{
int ans;
PopStack(J,ans);
if(ans<10)//小于10直接输出
cout<<ans;
else
{ //大于10，用ASCII码规律输出字符
char c;
c=ans-10+'A';
cout<<c;
}
}
cout<<endl;
}


完整代码：

#include
#include
#include
using namespace std;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
typedef int SElemType;
typedef int Status;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
SqStack S,J;
Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack &S)
{
int len=S.stacksize;
free(S.base);
S.base=S.top=NULL;
S.stacksize=0;
}
Status ClearStack(SqStack &S)
{
S.top=S.base;
return OK;
}
Status EmptyStack(SqStack &S)
{
if(S.top==S.base)
return 1;
else
return 0;
}
Status LengthStack(SqStack &S)
{
return (S.top-S.base);
}
Status TopStack(SqStack &S,int &e)
{
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
return OK;
}
Status PushStack(SqStack &S,int e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status PopStack(SqStack &S,int &e)
{
if(S.top == S.base) return ERROR;
e= *--S.top;
return OK;
}
Status ShowStack(SqStack &S)
{
SElemType *p=S.top;
while(p!=S.base)
cout<<*--p<<' ';
cout<<endl;
}
Status JinZhi(SqStack &S,int e,int jinzhi)
{
while(e)
{
PushStack(S,e%jinzhi);
e/=jinzhi;
}
}
Status ShowjzStack(SqStack &S)
{
SElemType *p=S.top;
while(!EmptyStack(J))
{
int ans;
PopStack(J,ans);
if(ans<10)
cout<<ans;
else
{
char c;
c=ans-10+'A';
cout<<c;
}
}
cout<<endl;
}
int main()
{
int order,init=0,des=0,len,e;
cout<<"*----------------栈--------------*"<<endl;
cout<<"*---------1.初始化栈-------------*"<<endl;
cout<<"*---------2.销毁栈---------------*"<<endl;
cout<<"*---------3.清空栈---------------*"<<endl;
cout<<"*---------4.栈判空---------------*"<<endl;
cout<<"*---------5.求栈长度-------------*"<<endl;
cout<<"*---------6.获取栈顶元素---------*"<<endl;
cout<<"*---------7.插入一个元素---------*"<<endl;
cout<<"*---------8.删除一个元素---------*"<<endl;
cout<<"*---------9.输出所有元素---------*"<<endl;
cout<<"*---------10.进制转换------------*"<<endl;
do{
cout<<"请输入指令"<<endl;
cin>>order;
if(order==0 || order>10)
cout<<"没有该指令"<<endl;
else if(!init && order>1 && order!=10)
cout<<"请先初始化栈"<<endl;
else if(des && order>1 && order!=10)
cout<<"栈已销毁，请先初始化"<<endl;
else
switch(order)
{
case 1:
InitStack(S);
init=1;
des=0;
cout<<"初始化栈完成"<<endl;
break;
case 2:
DestroyStack(S);
des=1;
cout<<"栈已销毁"<<endl;
break;
case 3:
ClearStack(S);
cout<<"栈已清空"<<endl;
break;
case 4:
if(!EmptyStack(S))
cout<<"栈非空"<<endl;
else
cout<<"栈为空"<<endl;
break;
case 5:
len=LengthStack(S);
cout<<"栈长度为："<<len<<endl;
break;
case 6:
if(TopStack(S,e))
cout<<"栈顶元素为："<<e<<endl;
else
cout<<"空栈，无栈顶元素"<<endl;
break;
case 7:
cout<<"请输入插入元素：";
cin>>e;
PushStack(S,e);
cout<<"入栈成功"<<endl;
break;
case 8:
if(PopStack(S,e))
cout<<"栈顶元素"<<e<<"出栈成功"<<endl;
else
cout<<"栈为空"<<endl;
break;
case 9:
cout<<"栈为："<<endl;
ShowStack(S);
break;
case 10:
cout<<"输入一个十进制数"<<endl;
cin>>e;
cout<<"输入要转换的进制"<<endl;
int jinzhi;
cin>>jinzhi;
InitStack(J);
cout<<"10进制数"<<e<<"转换为"<<jinzhi<<"进制数后为：";
if(e<0)
{
cout<<'-';
e=-e;
}
if(!e)
cout<<0;
JinZhi(J,e,jinzhi);
ShowjzStack(J);
break;
default:
cout<<"程序已退出"<<endl;
break;
}
}while(order>=0);
cout<<endl<<" ————MADE BY 敖丙"<<endl;
return 0;
}


写这个主要是加深印象，当然也能对新手起到1…帮助吧
欢迎各位指出错误与不足之处
谢谢