데이터 구조 - 스 택 - 스 택 의 첫 만 남

1. 창고 의 정의
        스 택 은 표 끝 에 만 삽입 하고 삭제 하 는 선형 표 입 니 다.
        저 희 는 삽입 과 삭 제 를 허용 하 는 한 끝 을 스 택 지붕 (top) 이 라 고 부 르 고 다른 한 끝 은 스 택 바닥 (bottom) 이 라 고 부 르 며 데이터 요소 가 없 는 스 택 을 빈 스 택 이 라 고 부 릅 니 다.
스 택 은 후진 선 출 (Last In First Out) 의 선형 표 라 고도 부 르 는데 LIFO 구조 라 고 부른다.
        창고 의 정 의 를 이해 하기 위해 주의해 야 할 상황
        먼저 이것 은 선형 표 이다. 즉, 스 택 요 소 는 선형 관 계 를 가진다. 즉, 전구 후계 관 계 를 가진다.단지 이것 은 특수 한 선형 표 일 뿐, 정의 중의 선형 표 의 끝 에 만 삽입 하고 삭제 하 는 작업 을 한다. 이곳 의 표 끝 은 창고 바닥 이 아니 라 창고 지붕 을 가리킨다.
        그것 의 특수 한 점 은 이 선형 표 의 삽입 과 삭제 위 치 를 제한 하 는 것 이다. 이것 은 항상 창고 꼭대기 에서 진행 되 기 때문에 창고 밑 은 고정 되 고 가장 선진 적 인 것 은 창고 밑 에 만 있 을 수 있다.
2. 창고 작업
        창고 의 삽입 작업 은 창고 에 들 어 가 는 것 을 창고 에 들 어 가 는 것 이 라 고 하고 창고 에 들 어 가 는 것 을 창고 에 들 어 가 는 것, 창고 에 들 어 가 는 것 이 라 고도 한다.
        창고 의 삭제 작업 은 창고 에서 나 오 는 것 이 라 고도 하고, 어떤 책 은 탄창 으로 건 네 주기 도 한다.
3. 창고 에 들 어가 창고 에서 나 오 는 변화 상황
        주의: 가장 선진 적 인 스 택 의 요 소 는 반드시 마지막 에 스 택 에서 나 오 는 것 이 아 닙 니 다.이것 은 스 택 이 선형 표 의 삽입 과 삭제 위 치 를 제한 하지만 요소 의 출입 시간 을 제한 하지 않 았 기 때 문 입 니 다. 즉, 모든 요소 가 스 택 에 들 어 갈 때 선진 스 택 의 요 소 는 스 택 에서 나 올 수 있 습 니 다.
예 를 들 어 우 리 는 현재 3 개의 정형 요소 가 있 는데 1, 2, 3 번 에 창고 에 들 어가 면 다음 과 같은 몇 가지 창고 순서 가 있 을 것 이다.
        1. 첫 번 째: 1, 2, 3 진, 그리고 3, 2, 1 출
        2. 두 번 째: 1 진, 1 출, 2 진, 2 출, 3 진, 3 출 이 므 로 출고 순 서 는 1, 2, 3 입 니 다.
       。。。。 등등 다섯 가지 상황.
4. 스 택 의 추출 데이터 형식

ADT  （stack）
DATA 
               ，         ，             。
Operation
           InitStack(*S):      ，      。
           DestroyStack（*S）:     ，    。
           ClearStack（*S）:     。
           StackEmpty（*S）:     ，   true，    false。
           GetTop(*S， *e):        ， e      。
           Push(*s, e):     ，     e  S        。
           Pull(*s,*e) :    S      ，  e    。
           StackLength(s):    S     。
endADT

5. 창고 의 순서 저장 구조 와 그 실현
창고 의 순서 저장 구조                스 택 의 순서 저장 은 선형 표 순서 저장 의 간소화 로 우 리 는 순서 스 택 이 라 고 부른다.선형 표 의 순서 저장 구 조 는 배열 에 의 해 이 루어 집 니 다. 스 택 에 대해 우 리 는 다음 과 같이 0 으로 표시 할 수 있 습 니 다. 첫 번 째 요 소 는 스 택 밑 에서 변화 가 가장 적 고 top 변 수 를 정의 하여 스 택 꼭대기 요소 가 배열 에 있 는 위 치 를 표시 할 수 있 습 니 다.스 택 의 길이 가 Stacksize 라면 스 택 꼭대기 위치 top 은 Stacksize 보다 작 아야 합 니 다.스 택 에 하나의 요 소 를 저장 할 때 top 은 0 과 같 기 때문에 우 리 는 빈 스 택 의 판정 조건 을 top = - 1 로 정의 하 는 것 을 공인 합 니 다.
                창고 의 구조 정의:
             

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

스 택 순서 저장 구조 - 스 택 작업              

               /*    e       */ 
               Static  Push(SqStack *s, SelemType e)
               {
                      if (S->top == MAXSIZE -1 ) /*  */
                     ｛
                                return ERROR;
                      ｝ 
                       S->top++;  /*     1*/
                       S->data[S->top] = e;  /*              */
                       return OK;
                }            

스 택 의 순서 저장 구조 - 스 택 작업                 
            

  <span style="white-space:pre">	</span>       /*     ，       ， e    ，   OK，    ERROR*/ 
               Static  Pop(SqStack *s, SelemType *e)
               {
                      if (S->top == MAXSIZE -1 ) /*  */
                     ｛
                                return ERROR;
                      ｝ 
                      
                       *e = S->data[S->top] ;  /*            e*/
                       
                        S->top++;  /*     1*/
                        return OK;
                }            

이 두 작업 의 시간 복잡 도 는 모두 O (1) 이다.
6. 두 스 택 공유 공간
         
하나의 배열 로 두 개의 스 택 을 저장 합 니 다. 실현 방식:
       배열 은 두 개의 점 이 있 고 두 개의 스 택 은 두 개의 스 택 밑 이 있 습 니 다. 한 스 택 의 스 택 밑 을 배열 의 시작 부분 으로 합 니 다. 즉, 아래 는 0 곳 으로 표시 하고 다른 하 나 는 배열 의 끝 입 니 다. 즉, 아래 는 배열 길이 의 n - 1 곳 으로 표시 합 니 다. 그러면 두 스 택 이 요 소 를 증가 하면 모두 두 개의 점 에서 중간 으로 연장 합 니 다.
       그 중 한 스 택 의 스 택 상단 지침 이 top 1 이 고 다른 하 나 는 top 2 라면 top 1 = - 1 일 때 이 스 택 은 비어 있 고 다른 하 나 는 top 2 = n - 1 일 때 비어 있 습 니 다.top 1 + 1 = = top 2 시 두 창고 가 가득 찼 습 니 다.
 두 스 택 공유 공간의 구조 코드 구현

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

두 창고 의 공간 을 공유 하 는 Push 방법           두 스 택 의 공유 공간의 push 방법 에 대해 우 리 는 요소 값 인 자 를 삽입 하 는 것 외 에 스 택 1 인지 스 택 2 인지 판단 하 는 스 택 번호 파라미터 stackNumber 가 필요 합 니 다.
         

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

두 창고 의 공간 을 공유 하 는 팝 방법         
          

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