棧與隊(duì)列

棧的基本概念

棧（Stack）是只允許在一端進(jìn)行插入或刪除操作的線性表。

棧的順序存儲結(jié)構(gòu)

順序棧的實(shí)現(xiàn)

順序棧的定義、初始化、判空

#define MaxSize 10  //定義棧中最大元素個(gè)數(shù)

typedef struct{
 ElemType data{MaxSize};  //ElemType元素類型，例如int
 int top;  //定義棧頂指針
}SqStack;

//初始化棧
void InitStack(SqStack &S){  
 S.top = -1;  //從-1開始是因?yàn)镾.top指向元素下標(biāo)，當(dāng)?shù)谝粋€(gè)元素進(jìn)來，top+1正好對應(yīng)下標(biāo)0
}

void teststack(){
 SqStack S;  //聲明一個(gè)棧
 InitStack(S);
}

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

進(jìn)棧、出棧操作、讀棧頂

#define MaxSize 10  //定義棧中最大元素個(gè)數(shù)

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;
 }
}

順序棧的實(shí)現(xiàn)另一種方式S.top = 0

共享?xiàng)?span style="display: none;">

#define MaxSize 10  //定義棧中最大元素個(gè)數(shù)

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