189 8069 5689

数据结构（三）——栈和队列-创新互联

栈和队列

创新互联公司"三网合一"的企业建站思路。企业可建设拥有电脑版、微信版、手机版的企业网站。实现跨屏营销，产品发布一步更新，电脑网络+移动网络一网打尽，满足企业的营销需求！创新互联公司具备承接各种类型的成都网站制作、成都做网站项目的能力。经过十载的努力的开拓，为不同行业的企事业单位提供了优质的服务，并获得了客户的一致好评。目录
  • 栈和队列
  • 栈
    • 定义以及特点
    • 栈顶指针与栈底指针
    • 操作
      • 顺序栈的定义
      • 初始化
      • 入栈
      • 出栈
      • 取栈顶元素
      • 销毁
    • 链栈
      • 定义
      • 初始化
      • 栈空
      • 栈长
      • 取栈顶元素
      • 出栈
      • 入栈
  • 队列
    • 定义以及队列
  • 进制转换

栈 定义以及特点

限定仅在表尾进行插入或删除的，后进先出的线性表
在这里插入图片描述

栈顶指针与栈底指针

base：栈底指针，始终指向栈底位置。若base=NULL，表明栈结构不存在。
top：栈顶指针，初值指向栈底。插入新元素时top+1，删除元素时top-1.。
空栈时，top与base的值相等，均指向栈底；非空时top始终指向栈顶元素的上一个位置。
在这里插入图片描述

操作 顺序栈的定义
#define MAXSIZE 100;
typedef struct
{SElemType *base;
  SElemType *top;
  int stacksize;                          //栈可用的大容量
}SqStack;
初始化
Status InitStack(SqStack &S)
{S.base=new SElemType[MAXSIZE];      //为顺序栈分配一个大容量为MAXSIZE的数组空间
   if(!S=base) exit(OVERFLOW);         //存储分配失败
   S.top = S.base;
   S.stacksize=MAXSIZE;
   return OK;
}
入栈
Status Push(SqStack &S,SElemType e)
{if(S.top-S.base==S.stacksize) return ERROR;
  *S.top++=e;     //*S.top=e;S.top++;
  return OK;
}
出栈
Status Pop(SqStack &S,SElemType e)
{if(S.top==S.base) return ERROR;
  e=*--S.top;
  return OK;
}
取栈顶元素
SElemType GetTop(SqStack S)
{if(S.top==S.base)
   return *(S.top-1);
}
销毁
void DestroyStack(SqStack &S)
{delete []S.base;
  S.stacksize=0;
  S.base=S.top=NULL;
 }
链栈

注：链栈中一般不设置头结点

定义
typedef struct Node
{SElemType data;
 struct Node *next;
}Node,*LinkStack;
初始化
Status InitStack(LinkStack &S)    //S:栈顶指针
{S==NULL;
   return OK;
}
栈空
bool StackEmpty(LinkStack S)
{return (S==NULL);
栈长
int StackLength(LinkStack S)
{for(i=0,p=S;p;i++,p=p->next);
   return i;
}
取栈顶元素
Status GetTop(LinkStack S,SElemType &e)
{if(S==NULL) return ERROR;
   e=S->data;
   return OK;
}
出栈
Status Pop(LinkStack &S,SElemType e)
{if(S==NULL) return ERROR;
  e=S->data;
  p=S;
  S=S->next;
  delete p;
  return OK;
}
入栈
Status Push(LinkStack &S,SElemType e)
{p=new StackNode;
  p->data=e;
  p->next=S;
  S=p;
  return OK;
}
队列 定义以及队列

仅允许在表的一端进行插入(队尾)，在另一端进行删除的(队头)，先进先出的线性表
在这里插入图片描述

进制转换
void conversion(int N,int r){InitStack(S);
while(N)
{Push(S,N%r);
   N=N/r;
}
while(!StackEmpty(S)){Pop(S,e);
   if(e<10)printf("%d",e);
   else printf("%c",'A'+e-10);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


文章名称：数据结构（三）——栈和队列-创新互联
分享地址：http://cdxtjz.cn/article/djhiep.html

其他资讯