스 택 공유 저장 공간

두 창고 의 공유 공간 이란 그 중의 한 창고 의 공간 을 다 쓸 때 다른 창고 의 공간 을 빌려 쓸 수 있어 공간의 이 용 률 을 크게 높 인 다 는 것 을 말한다.
   한 배열 은 두 개의 점 이 있 고, 하 나 는 시작 점 이 며, 다른 하 나 는 배열 의 끝 이다.그리고 두 개의 스 택 에 두 개의 스 택 바닥 이 있 으 면 우 리 는 그 중의 한 스 택 바닥 을 배열 의 시작 점 으로 하고 다른 스 택 바닥 은 배열 의 끝 으로 한다.두 창고 에 원 소 를 추가 하면 중간 으로 뻗 습 니 다.
   그렇다면 우 리 는 이 공유 공간의 스 택 을 어떻게 조작 해 야 합 니까?그 중 한 스 택 의 top 지침 은 배열 0 곳 을 가리 키 고 다른 스 택 의 top 지침 은 배열 (n - 1) 곳 을 가리 키 며 n 은 배열 길이 입 니 다.top 1 = - 1, top 2 = n 일 때 스 택 1 과 스 택 2 가 모두 빈 스 택 임 을 의미 합 니 다.스 택 1 에 데이터 가 저장 되 어 있 을 때 top 1 + + 요소 가 스 택 2 에 저장 되 어 있 으 면 top 2 - -.그렇다면 어떻게 두 창고 의 공유 공간 이라는 구 조 를 개척 합 니까?한 배열 이 필요 한 것 이 분명 합 니 다. 두 개의 지침 이 필요 합 니 다. 하 나 는 배열 의 맨 끝 을 가리 키 는 스 택 1 의 스 택 포인터 로 하고 다른 하 나 는 배열 의 맨 끝 을 가리 키 는 스 택 2 의 스 택 포인터 로 합 니 다.코드 는 다음 과 같 습 니 다:

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

   그러면 어떻게 요소 의 삽입 을 실현 합 니까?우선 스 택 1 인지 스 택 2 인지 확인 해 야 하기 때문에 스 택 1 인지 스 택 2 인지 판단 하 는 변수 stackNumber 가 필요 합 니 다.요소 의 삽입 을 실현 할 때 먼저 스 택 이 만 스 택 인지 여 부 를 판단 해 야 합 니 다. 만 스 택 이 되면 삽입 에 실 패 했 습 니 다. 새로운 요 소 를 넣 을 공간 이 없 기 때 문 입 니 다.언제 만 잔 입 니까?포인터 top 1 과 포인터 top 2 의 차이 가 1 일 때, 즉 두 바늘 이 만 났 을 때, 이 때 는 스 택 이 가득 합 니 다.코드 는 다음 과 같 습 니 다:

top1 + 1 == top2;

스 택 이 가득 차지 않 으 면 요 소 를 계속 삽입 할 수 있 습 니 다. 이때 스 택 1 에 넣 을 지 스 택 2 에 넣 을 지 판단 합 니 다.창고 1 에 넣 으 면,

s->data[++s->top1] = e;

창고 2 에 넣 으 면,

s->data[--S->top2] = e;

전체 코드 는 다음 과 같 습 니 다:

Status Push ( SqDoubleStack *S, ElemType e, int stackNumber )
{
    if ( top1 + 1 == top2 )
        return ERROR;
    
    if ( stackNumber == 1 )
        S->data[++S->top1] = e;
    if ( stackNumber == 2 )
        S->data[--S->top2] = e;
        
    return OK;

}

   마찬가지 로 원소 의 삭 제 는 원소 의 팝 업 (POP) 동작 으로 원소 의 팝 업 (PUSH) 과 유사 하 다.요 소 를 삭제 하려 면 먼저 스 택 1 의 요소 인지 스 택 2 의 요소 인지 판단 해 야 합 니 다. 스 택 1 의 요소 라면 스 택 1 이 빈 스 택 인지 판단 해 야 합 니 다. 빈 스 택 이면 삭제 에 실 패 했 습 니 다. 빈 스 택 이 아니라면.

--S->top1;

스 택 2 의 요소 라면 스 택 2 가 빈 스 택 인지 아 닌 지 를 판단 해 야 합 니 다. 빈 스 택 이 아니라면...

++S->top2;

전체 코드 는 다음 과 같 습 니 다:

Status ( SqDoubleStack *S, ElemType *e, int stackNumber )
{
    if ( stackNumber == 1 ){
    
        if ( S->top1 == -1 )
            return ERROR;
        
        *e = S->data[S->top1--];
        
    }
    
    if ( stackNumber == 2 ){
    
        if ( S->top2 == MAXSIZE )
            return ERROR;
            
        *e = S->data[S->top2++];
  
    }

    return OK;
}