栈与队列

栈的基本概念

栈（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