창고 (스 택)

콘 셉 트
스 택 (stack) 은 표 끝 에 만 삽입 하고 삭제 하 는 선형 표 입 니 다.삽입 과 삭 제 를 허용 하 는 한 끝 을 스 택 꼭대기 (top) 라 고 하고, 다른 한 끝 을 스 택 밑 (bottom) 이 라 고 하 며, 데이터 요 소 를 포함 하지 않 은 스 택 은 빈 스 택 이 되 고, 스 택 은 후진 선 출 (Last In First Out) 의 선형 표 라 고도 하 며, LIFO 구조 라 고 부른다.
스 택 의 삽입 작업 을 스 택 / 스 택 / 스 택 에 들 어 가 는 것 이 라 고 합 니 다.스 택 의 삭제 작업 을 스 택 / 탄 스 택 이 라 고 합 니 다.
스 택 의 추상 데이터 형식

ADT  （stack）

Data
       。        ，             。
Operation
   InitStack(*S):     ，      。
   DestoryStack(*S):    ，    。
   ClearStack(*S):    。
   StackEmpty(S):    ，  true，    false。
   GetTop(S,*e):       ， e      。
   Push(*S,e):  S  ，     e  S        。
   Pop(*S,*e):    S      ，  e    。
   SrackLength(S):   S     。
 endADT  

순차 기억 구조
스 택 은 선형 표 의 특례 로 배열 로 스 택 의 순서 저장 구 조 를 실현 하고 아래 표 시 된 0 의 한 끝 을 스 택 밑 으로 선택 하여 top 변 수 를 정의 하여 스 택 꼭대기 요소 가 배열 에 있 는 위 치 를 표시 합 니 다. 커서 에 해당 합 니 다. 커서 는 왔다갔다 이동 할 수 있 지만 배열 범 위 를 초과 해 서 는 안 됩 니 다.스 택 에 요소 가 존재 할 때 top = 0 이 므 로 빈 스 택 의 판정 조건 을 top 과 - 1 (배열 아래 표 시 는 0 부터) 로 설정 합 니 다.
창고 의 구조 정 의 는 다음 과 같다.

typedef int SElemType; //        ，     int
typedef struct{
   SElemType data[MAXSIZE];
   int top; //          
}SqStack;

창고 에 들 어가 조작 하 다.

/*    e        */
Status Push(SqStack *S,SElemType e){
   if(S->top >= MAXSIZE-1) return ERROR; //  
   //            ，       ，        。
   S->top++; //        ，       
   S->data[S->top]=e;
   return OK;
}

출고 작업

/*     ，   S     ， e    ，   OK；    ERROR*/
Status Pop(SqStack *S,SElemType *e){
   if(S->top == -1) return ERROR; //   
   *e=S->data[S->top]; //        
   S->top--; //      
   return OK;
}

확장 - 두 스 택 공유 공간
한 배열 로 두 개의 스 택 을 실현 합 니 다. 한 스 택 의 스 택 밑 은 배열 의 시작 부분 (아래 는 0 으로 표시) 에 있 고 다른 스 택 의 스 택 밑 은 배열 의 끝 (아래 는 n - 1 로 표시) 에 있 으 며 두 개의 top 포인터 로 스 택 의 위 치 를 표시 합 니 다.(양 끝 에 위치 하고 가운데 로 접근)
스 택 1 이 비어 있 습 니 다: top 1 은 - 1 입 니 다.스 택 2 가 비어 있 습 니 다: top 2 는 n 과 같 습 니 다.
스 택 가득: 두 바늘 사이 의 차이 1, top 1 + 1 = top 2.
두 창고 공유 공간의 구조 와 관련 방법의 코드 는 다음 과 같다.

/*        */
typedef struct{
   SElemType data[MAXSIZE];
   int top1;  // 1    
   int top2;  // 2    
}SqDoubleStack;

/*    e       ，  */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber){
   //      stackNumber    1   2

   if(S->top1+1 == S->top2) return ERROR; //  

   if(stackNumber==1){// 1  
      //    ：S->data[++S->top1]=e;
      S->top1++;
      S->data[S->top1]=e;
   }else if(stackNumber== 2){// 2  
      //    ：S->data[--S->top]=e;
      S->top2--;
      S->data[S->top]=e;
   }
   return OK;
}

/*     ，  S     ， e    ，   OK；    ERROR*/
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber){    
   if(stackNumber==1){ // 1  ，        ，       
      if(S->top1==-1)  return ERROR; //   
      *e=S->data[S->top1--]; //      ，       
   }else 
   if(stackNumber== 2){// 1  ，        ，       
      if(S->top2==MAXSIZE) return ERROR; //   
      *e=S->data[S->top2++]; //      ，       
   }
   return OK;
}

소결: 두 창고 의 공간 수요 가 상 반 된 관계 가 있 을 때, 즉 하 나 는 창고 에 나 가 고 하 나 는 창고 에 들어간다. 예 를 들 어 매매 하 는 것 이다.두 개의 같은 유형의 스 택 디자인 기법 에 대해 유형 에 따라 이 방법 을 사용 하면 더욱 복잡 해 지고 적용 되 지 않 습 니 다.
체인 메모리 구조
헤드 포인터 와 스 택 포인 터 를 합 쳐 스 택 포인 터 를 만 들 기 때문에 스 택 지붕 을 링크 머리 에 놓 습 니 다.빈 창 고 를 판단 하 는 조건 은 top = = NULL 입 니 다.
창고 의 구조 정 의 는 다음 과 같다.

typedef struct StackNode{
   SElemType data;
   struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack{ //    ，     
   LinkStackPtr top;
   int count;
}LinkStack;

창고 에 들 어가 조작 하 다.

/*    e        */
Status Push(LinkStack *S,SElemType e){
   //       ，       
   LinkStackPtr s=(LinkStackPtr)malloc(size(StackNode));
   s->data=e;  //    
   s->next=S->top;  //       
   S->top=s;  //        
   S->count++;  //      +1
   return OK;
}

출고 작업

/*     ，   S     ， e    ，   OK；    ERROR*/
Status Pop(LinkStack *S,SElemType *e){
   LinkStackPtr p; //        
   //        S->top->next==NULL
   if(StackEmpty(*S)) return ERROR;  
   *e=S->top->data;  //       
   p=S->top;  //    
   S->top=S->top->next;  //      
   free(p);  //    
   S->count--;  
   return OK;
}

순서 스 택 과 링크 스 택 의 비교: 시간 복잡 도 와 마찬가지 로 모두 O (1) 입 니 다.순서 스 택 은 고정 길 이 를 미리 정 해 야 하기 때문에 공간 낭비 문제 가 발생 할 수 있 지만 액세스 할 때 위치 추적 이 편리 합 니 다.링크 스 택 은 요소 가 모두 포인터 영역 이 있 고 메모리 소 비 를 증가 하 라 고 요구 하지만 길이 에 제한 이 없습니다.
소결: 스 택 의 사용 과정 에서 요소 의 변 화 를 예측 할 수 없 으 면 작 을 때 도 있 고 클 때 도 있 으 므 로 링크 스 택 을 사용 하 는 것 이 좋 습 니 다. 반대로 제어 가능 한 범위 내 에서 변화 하면 순서 스 택 을 사용 하 는 것 이 좋 습 니 다.