데이터 구조 --- 체인 스 택 실현

체인 스 택 은 말 그대로 플러그 만 삭제 하거나 꼬리 만 삭제 할 수 있 는 체인 표를 규정 하여 스 택 구조의 선진 적 인 원칙 을 실현 하 는 것 이다.
여기 서 우 리 는 머리 삽입 과 머리 삭제 방법 을 선택한다. 왜냐하면 꼬리 삽입 과 꼬리 삭 제 는 모두 링크 를 옮 겨 다 녀 야 하기 때문에 시간 복잡 도가 비교적 높다.
비교 하지 않 고 코드 를 통 해 직접 보 여 줍 니 다.
구조 체 성명

typedef char LinkListType;

typedef struct LinkListStack{
    struct LinkListStack* next;//   ，          
    LinkListType data;//   ，      
}LinkListStack;

구체 적 함수 성명

//    
void LinkListStackInit(LinkListStack** head);

//  
void LinkListStackPush(LinkListStack** head,LinkListType value);

//                                                                                                                                    
void LinkListStackPop(LinkListStack** head);

//   
void DestroyNode(LinkListStack* node);

//     
LinkListStack* CreateNode(LinkListType value);

//     
int LinkListStackGetTop(LinkListStack* head,LinkListType* value);

초기 화 및 폐기

void LinkListStackInit(LinkListStack** head)
{
    if(head==NULL){
        //    
        return;
    }
    *head=NULL;                                                                                                                         
}

//  free  ，         ，           ，      ，                                                 
void DestroyNode(LinkListStack* node)
{
    free(node);
}   

창고 에 들 어 가 는 것 과 출고 하 는 것

//                   ，               ，           
//        ，              ，             next                                                 
LinkListStack* CreateNode(LinkListType value)
{
    LinkListStack* newNode = (LinkListStack*)malloc(sizeof(LinkListStack));
    newNode->next = NULL;
    newNode->data = value;
    return newNode;
}

//  
//        O(1),  
void LinkListStackPush(LinkListStack** head,LinkListType value)
{
    if(head == NULL)
    {
        //    
        return;
    }
    if(*head==NULL)
    {
        //  
        *head = CreateNode(value);
        return;
    }
    LinkListStack* cur = CreateNode(value);
    cur->next = *head;
    *head = cur;
}

//  
//        O(1),  
void LinkListStackPop(LinkListStack** head)
{
    if(head==NULL)
    {
        //    
        return;
    }
    if(*head==NULL)
    {
        //  
        return;
    }
    LinkListStack* cur = *head;
    *head=(*head)->next;
    DestroyNode(cur);
}

스 택 상단 요 소 를 꺼 내 는 것 도 출력 형 매개 변수 가 필요 합 니 다.

int LinkListStackGetTop(LinkListStack* head,LinkListType* value)
{
    if(head==NULL){
        //   
        return 0; 
    }
    *value = head->data;
    return 1;
}