재 학 데이터 구조 003 ― 스 택 의 기본 조작 및 실현 (체인 저장)

1. 창고 의 개념
    한 끝 에 만 삽입 어 삭제 작업 을 할 수 있 는 표를 보 여 줍 니 다.정의 상 스 택 도 선형 표 이기 때문에 스 택 도 대부분 선형 표 가 갖 춘 기본 적 인 조작 을 가진다.그러나 정의 에서 알 수 있 듯 이 스 택 은 삽입, 삭제 작업 을 할 때 한 끝 에서 만 작업 을 할 수 있 고 이 한 끝 은 스 택 꼭대기 (top) 가 됩 니 다.
    스 택 의 가장 핵심 적 인 작업 은 주로 스 택 (Push), 스 택 (Pop), 스 택 정상 요소 (Top) 로 돌아 가 는 것 입 니 다.그 밖 에 스 택 이 비어 있 는 지, 스 택 을 만 들 고 스 택 을 비 우 는 지 등 조작 도 판단 한다.
    선형 표 인 이상 스 택 은 실현 방식 으로 볼 때 주로 두 가지 가 있다. 순서 저장 실현 (배열), 체인 저장 실현 (링크) 이다.다음은 체인 식 저장 실현 방식 에서 사이트 의 데이터 구조 정의 입 니 다.

  
  
  
  

   
   
   
   
typedef struct Node *PtrToNode; 
   
   
   
   
typedef PtrToNode Stack; 
   
   
   
   
typedef struct Node 
   
   
   
   
{ 
   
   
   
   
    int Element; 
   
   
   
   
    PtrToNode Next; 
   
   
   
   
}; 
  
  
  
  

    사이트 의 기본 동작 은 다음 과 같 습 니 다.

  
  
  
  

   
   
   
   
//        
   
   
   
   
int IsEmpty(Stack S); 
   
   
   
   
//    
   
   
   
   
Stack CreateStack(); 
   
   
   
   
//    
   
   
   
   
void DisposeStack(Stack S); 
   
   
   
   
//    
   
   
   
   
void MakeEmpty(Stack S); 
   
   
   
   
//   
   
   
   
   
void Push(int X,Stack S); 
   
   
   
   
//       
   
   
   
   
int Top(Stack S); 
   
   
   
   
//   
   
   
   
   
void Pop(Stack S); 
  
  
  
  

    다음은 스 택 에 대한 완전한 기본 작업 의 예 입 니 다.

  
  
  
  

   
   
   
   
#include <stdio.h> 
   
   
   
   
#include <stdlib.h> 
   
   
   
   
 
   
   
   
   
typedef struct Node *PtrToNode; 
   
   
   
   
typedef PtrToNode Stack; 
   
   
   
   
typedef struct Node 
   
   
   
   
{ 
   
   
   
   
    int Element; 
   
   
   
   
    PtrToNode Next; 
   
   
   
   
}; 
   
   
   
   
 
   
   
   
   
int IsEmpty(Stack S); 
   
   
   
   
Stack CreateStack(); 
   
   
   
   
void DisposeStack(Stack S); 
   
   
   
   
void MakeEmpty(Stack S); 
   
   
   
   
void Push(int X,Stack S); 
   
   
   
   
int Top(Stack S); 
   
   
   
   
void Pop(Stack S); 
   
   
   
   
 
   
   
   
   
//        
   
   
   
   
int IsEmpty(Stack S) 
   
   
   
   
{ 
   
   
   
   
    return S->Next == NULL; 
   
   
   
   
} 
   
   
   
   
//     
   
   
   
   
Stack CreateStack() 
   
   
   
   
{ 
   
   
   
   
    Stack S = malloc(sizeof(struct Node)); 
   
   
   
   
    if(S == NULL) 
   
   
   
   
    { 
   
   
   
   
        printf("No enough memory!"); 
   
   
   
   
        return NULL; 
   
   
   
   
    } 
   
   
   
   
    S->Next = NULL; 
   
   
   
   
    MakeEmpty(S); 
   
   
   
   
    return S; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void MakeEmpty(Stack S) 
   
   
   
   
{ 
   
   
   
   
    if(S == NULL) 
   
   
   
   
    { 
   
   
   
   
        printf("Use CreateStack First!"); 
   
   
   
   
    } 
   
   
   
   
    else 
   
   
   
   
    { 
   
   
   
   
        while(!IsEmpty(S)) 
   
   
   
   
        { 
   
   
   
   
            Pop(S); 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void Push(int X,Stack S) 
   
   
   
   
{ 
   
   
   
   
    PtrToNode Tmp; 
   
   
   
   
    Tmp = malloc(sizeof(struct Node)); 
   
   
   
   
    if(Tmp != NULL) 
   
   
   
   
    { 
   
   
   
   
        Tmp->Element = X; 
   
   
   
   
        Tmp->Next = S->Next; 
   
   
   
   
        S->Next = Tmp; 
   
   
   
   
    } 
   
   
   
   
    else 
   
   
   
   
    { 
   
   
   
   
        printf("Out of space!"); 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void Pop(Stack S) 
   
   
   
   
{ 
   
   
   
   
     
   
   
   
   
    if(IsEmpty(S)) 
   
   
   
   
    { 
   
   
   
   
        printf("The Stack is Empty!"); 
   
   
   
   
    } 
   
   
   
   
    else 
   
   
   
   
    { 
   
   
   
   
        PtrToNode Tmp = S->Next; 
   
   
   
   
        S->Next = Tmp->Next; 
   
   
   
   
        free(Tmp); 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
int Top(Stack S) 
   
   
   
   
{ 
   
   
   
   
    if(IsEmpty(S)) 
   
   
   
   
    { 
   
   
   
   
        printf("The stack is empty!"); 
   
   
   
   
        return 0; 
   
   
   
   
    } 
   
   
   
   
    else 
   
   
   
   
    { 
   
   
   
   
        return S->Next->Element; 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
int main(void) 
   
   
   
   
{ 
   
   
   
   
    Stack S = CreateStack(); 
   
   
   
   
    int i; 
   
   
   
   
    for(i = 0; i < 5; i++) 
   
   
   
   
    { 
   
   
   
   
        Push(i,S); 
   
   
   
   
    } 
   
   
   
   
 
   
   
   
   
    while(!IsEmpty(S)) 
   
   
   
   
    { 
   
   
   
   
        printf("%d
",Top(S)); 
   
   
   
   
        Pop(S); 
   
   
   
   
    } 
   
   
   
   
    return 0; 
   
   
   
   
}