【C/C++|DataStructure】栈与队列之栈的顺序存储结构

Python小灶

共 2810字,需浏览 6分钟

 ·

2021-03-29 02:18


本文章适合有一定C/C++基础,对数据结构感兴趣的同学。

如果你觉得C语言很难,为什么不试试Python呐?

栈与队列

栈的基本概念

栈(Stack)是只允许在一端进行插入或删除操作的线性表。

栈的顺序存储结构

顺序栈的实现

顺序栈的定义、初始化、判空

#define MaxSize 10  //定义栈中最大元素个数

typedef struct{
 ElemType data{MaxSize};  //ElemType元素类型,例如int
 int top;  //定义栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S){  
 S.top = -1;  //从-1开始是因为S.top指向元素下标,当第一个元素进来,top+1正好对应下标0
}

void teststack(){
 SqStack S;  //声明一个栈
 InitStack(S);
}

//栈的判空
bool StackEmpty(SqStack S){
 if (S.top == -1){
  return true;  //栈空
 }else{
  return false;  //不空
 }
}

进栈、出栈操作、读栈顶

#define MaxSize 10  //定义栈中最大元素个数

typedef struct{
 ElemType data{MaxSize};  //ElemType元素类型,例如int
 int top;  //定义栈顶指针
}SqStack;

//新元素入栈
bool push(SqStack &S, ElemType x){
 if(S.top == MaxSize - 1){ //栈满
  return false;
 }else{
  S.top = S.top + 1;  //指针+1
  S.data[S.top] = x;  //新元素入栈
  return true;
 }
}

//出栈
bool Pop(SqStack &S, ElemType &x){
 if(S.top == - 1){ //空栈
  return false;
 }else{
  x = S.data[S.top];  //获取要出栈的元素
  S.top = S.top - 1;  //指针-1
  return true;
 }
}

//读栈顶
bool GetTop(SqStack &S, ElemType &x){
 if(S.top == - 1){ //空栈
  return false;
 }else{
  x = S.data[S.top];  //获取要读取的元素
  return true;
 }
}

顺序栈的实现另一种方式S.top = 0

共享栈

#define MaxSize 10  //定义栈中最大元素个数

typedef struct{
 ElemType data{MaxSize};  //ElemType元素类型,例如int
 int top0;  //0号栈栈顶指针
 int top1;  //1号栈栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S){  
 S.top0 = -1;
 S.top1 = MaxSize;
}

//栈满的条件:top0 + 1 == top1


如果你觉得C语言很难,为什么不试试Python呐?


猜你喜欢

                                

                                           



浏览 21
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报