C 언어 체인 스 택 실현

순서 스 택 과 달리 체인 스 택 은 체인 시트 를 사용 하여 스 택 요 소 를 저장 합 니 다. 링크 의 요소 주소 가 연속 되 지 않 기 때문에 스 택 의 최대 저장 용량 을 미리 알 필요 가 없습니다. 필요 할 때 동태 적 으로 개척 하면 됩 니 다.따라서 체인 스 택 에서 스 택 구 조 를 유지 하 는 것 은 스 택 바닥 과 스 택 꼭대기 두 개의 지침 만 있 습 니 다.체인 스 택 의 기본 작업 은 실제 적 으로 모두 링크 의 삽입, 삭제, 옮 겨 다 니 는 작업 으로 실현 하기 가 비교적 쉽다.구체 적 인 기능 은 다음 과 같다.

#include
#include
#include
//    

//             
typedef struct Lnode{
int data;//  
struct Lnode *next;//          
}Lnode, *pLnode;

//           
typedef struct Lstack{
pLnode base;//       
pLnode top;//       
}Lstack;

/**      
       
  
  
         
       
      
        
     
*/

//       
bool initStack(Lstack &S){
  S.base = (pLnode)malloc(sizeof(Lnode));
  if(S.base == NULL){exit(-1);}//        ,  
  S.base->next = NULL;
  S.top = S.base;
  return true;
}

//  
bool push(Lstack &S, int e){
  if(S.base == NULL){exit(-1);}//      
  S.top->data = e;
  pLnode pnew = (pLnode)malloc(sizeof(Lnode));
  if(pnew == NULL){exit(-1);}
  pnew->next = NULL;
  S.top->next = pnew;
  S.top = pnew;
  return true;
}

//    e  
bool getTop(Lstack &S,int &e){
 if(S.top == S.base){return false;}//      
 pLnode p = S.base;
 while(p->next != S.top){
    p = p->next;
 }
 e = p->data;
 return true;
}

//        e  
bool pop(Lstack &S,int &e){
if(S.top == S.base){return false;}//      
 pLnode p = S.base;
 while(p->next != S.top){
    p = p->next;
 }
 e = p->data;
 pLnode q = p->next;
 p->next = NULL;
 S.top = p;
 free(q);
 q = NULL;
 return true;
}

//       ,    true，    false
bool isEmptyStack(Lstack &S){
 if(S.base == NULL){exit(-1);} //     ，    
 return S.top == S.base ? true : false;
}

//          
bool resetStack(Lstack &S){
  if(S.base == NULL){exit(-1);}
  S.top = S.base;
  pLnode p = S.base->next;
  S.base->next = NULL;
  while(p != NULL){
    pLnode q = p->next;
    free(p);
    p = q;
  }
  return true;
}
//        
int getStackLen(Lstack &S){
  if(S.base == NULL){exit(-1);}
  pLnode p = S.base;
  int length = 0;
  while(p != S.top){
    length += 1;
    p = p->next;
  }
  return length;
}
//   
bool destroyStack(Lstack &S){
  if(S.base == NULL){exit(-1);}
  pLnode p, q;
  p = S.base;
  while(p != NULL){
    q = p->next;
    free(p);
    p = q;
  }
  S.base = NULL;
  return true;
}