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

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

  
  
  
  
  1. typedef struct Node *PtrToNode; 
  2. typedef PtrToNode Stack; 
  3. typedef struct Node 
  4.     int Element; 
  5.     PtrToNode Next; 
  6. }; 

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

  
  
  
  
  1. //  
  2. int IsEmpty(Stack S); 
  3. //  
  4. Stack CreateStack(); 
  5. //  
  6. void DisposeStack(Stack S); 
  7. //  
  8. void MakeEmpty(Stack S); 
  9. //  
  10. void Push(int X,Stack S); 
  11. //  
  12. int Top(Stack S); 
  13. //  
  14. void Pop(Stack S); 

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

  
  
  
  
  1. #include <stdio.h> 
  2. #include <stdlib.h> 
  3.  
  4. typedef struct Node *PtrToNode; 
  5. typedef PtrToNode Stack; 
  6. typedef struct Node 
  7.     int Element; 
  8.     PtrToNode Next; 
  9. }; 
  10.  
  11. int IsEmpty(Stack S); 
  12. Stack CreateStack(); 
  13. void DisposeStack(Stack S); 
  14. void MakeEmpty(Stack S); 
  15. void Push(int X,Stack S); 
  16. int Top(Stack S); 
  17. void Pop(Stack S); 
  18.  
  19. //  
  20. int IsEmpty(Stack S) 
  21.     return S->Next == NULL; 
  22. //  
  23. Stack CreateStack() 
  24.     Stack S = malloc(sizeof(struct Node)); 
  25.     if(S == NULL) 
  26.     { 
  27.         printf("No enough memory!"); 
  28.         return NULL; 
  29.     } 
  30.     S->Next = NULL; 
  31.     MakeEmpty(S); 
  32.     return S; 
  33.  
  34. void MakeEmpty(Stack S) 
  35.     if(S == NULL) 
  36.     { 
  37.         printf("Use CreateStack First!"); 
  38.     } 
  39.     else 
  40.     { 
  41.         while(!IsEmpty(S)) 
  42.         { 
  43.             Pop(S); 
  44.         } 
  45.     } 
  46.  
  47. void Push(int X,Stack S) 
  48.     PtrToNode Tmp; 
  49.     Tmp = malloc(sizeof(struct Node)); 
  50.     if(Tmp != NULL) 
  51.     { 
  52.         Tmp->Element = X; 
  53.         Tmp->Next = S->Next; 
  54.         S->Next = Tmp; 
  55.     } 
  56.     else 
  57.     { 
  58.         printf("Out of space!"); 
  59.     } 
  60.  
  61. void Pop(Stack S) 
  62.      
  63.     if(IsEmpty(S)) 
  64.     { 
  65.         printf("The Stack is Empty!"); 
  66.     } 
  67.     else 
  68.     { 
  69.         PtrToNode Tmp = S->Next; 
  70.         S->Next = Tmp->Next; 
  71.         free(Tmp); 
  72.     } 
  73.  
  74. int Top(Stack S) 
  75.     if(IsEmpty(S)) 
  76.     { 
  77.         printf("The stack is empty!"); 
  78.         return 0; 
  79.     } 
  80.     else 
  81.     { 
  82.         return S->Next->Element; 
  83.     } 
  84.  
  85. int main(void
  86.     Stack S = CreateStack(); 
  87.     int i; 
  88.     for(i = 0; i < 5; i++) 
  89.     { 
  90.         Push(i,S); 
  91.     } 
  92.  
  93.     while(!IsEmpty(S)) 
  94.     { 
  95.         printf("%d
    "
    ,Top(S)); 
  96.         Pop(S); 
  97.     } 
  98.     return 0; 

좋은 웹페이지 즐겨찾기