스 택, 팀 데이터 구조

Stack
첫 번 째 정의 (추천, 동적 분배 Stack SIZE 가능)

typedef struct {
  ElemType *base;    //     stack base;
  int top;    //   stack top;
  int stacksize;    //           ,       ;    MAXSIZE  
}SqStack;

첫 번 째 정 의 를 통 해 알 수 있 듯 이 현재 stack length 는 직접 (top - base) / sizeof (ElemType) (+ 1 을 사용 하지 않 습 니 다. top 이 다음 을 가리 키 기 때 문 입 니 다).

두 번 째 정의 (고정 Stack 의 SIZE)

typedef struct {
  ElemType stack[MAXSIZE];    //        ,      
  int top;    //   stack top;
} SqStack;

두 번 째 정의 에서 우 리 는 stack length 가 직접 top 에서 나 올 수 있 음 을 알 수 있다. (top 이 가리 키 는 것 은 빈 다음 을 가리 키 지만 stack 배열 은 stack [0] 에서 시작 하여 stack - length = top - 1 - 0 + 1 = top);

/*    */
//      struct       base, top, stacksize;
Status InitStack(SqStack *S) {
    S->base = (ElemType *)malloc(SIZE*sizeof(ElemType));
    S->stacksize = SIZE;
    S->top = 0; 
    return 0;
}

/*GetTop*/
//        ,        base[top-1];
ElemType GetTop(SqStack *S) {
    if (S->top==0) {printf("GetTop UNDERFLOW
"); return ERROR;}
    else {return S->base[S->top-1];}
}

/*Pop*/
//        ,       top--       ;
Status Pop(SqStack *S) {
    if (S->top==0) {printf("Pop UNDERFLOW
"); return ERROR;}
    else {S->top--; return 0;}
}

/**/
//        ,    realloc  ,      push e top    ,    top    ;
Status Push (SqStack *S, ElemType e) {
    if (S->top >= SIZE) {
        S->base = (ElemType *)realloc(S->base,(SIZE+INCREMENT)*sizeof(ElemType));
        S->stacksize += INCREMENT;
        if (!S->base) {printf("Push OVERFLOW
"); exit(OVERFLOW);}
    }
    S->base[S->top] = e;
    S->top++;
    return 0;
}

Queue

typedef struct {
    ElemType *base;  //        ,           
    int front, rear;
    int length;    //               ,     num        ; stack      , length  top    ; 
    int queuesize; 
}SqQueue;

/*GetFront*/
//     length==0,     base[front]
ElemType GetFront(SqQueue *Q) {
    if (Q->length==0) {
        printf("GetFront UNDERFLOW
"); return ERROR;
    } else {
        return Q->base[Q->front];
    }
}

//   Q     ,     front        ;
Status DeQueue(SqQueue *Q) {
    if (Q->length==0) {
        printf("DeQueue UNDERFLOW
"); return ERROR;
    } else {
        Q->front++;
    }
}

//   Q     ,       ,    rear, length  ++
Status EnQueue(SqQueue *Q, ElemType e) {
    if (Q->length==SIZE) {
        //      
        Q->base = (ElemType *)realloc(Q->base,(SIZE+INCREMENT)*sizeof(ElemType));
        Q->queuesize += INCREMENT;
        if (!Q->base) {printf("EnQueue OVERFLOW
"); exit(OVERFLOW);}
    }
    Q->base[Q->rear] = e;
    Q->rear++;
    Q->length++;
    printf("rear: %d
",Q->rear);
    return 0;
}

후기: queue 의 데이터 구조 정의 와 stack 의 기본 적 인 세트 는 모두 순서 선형 표 의 정의 방식 (* elem, length, listize → stack / queue (배열 이름 은 지침), top / front, rear, length, size (top 자체 가 length 를 계산 하 는 방법 을 포함) 을 사용 합 니 다.
DFS 와 스 택, BFS 와 대기 열
스 택 과 대기 열 은 간단 하고 사용 하 는 데이터 구조 로 사용 범위 가 넓 습 니 다. 그림 알고리즘 에서 가장 기본 적 인 DFS 와 BFS 알고리즘 의 실현 은 각각 스 택 과 대기 열 에 의존 합 니 다. 관련 알고리즘 코드 는 제 그림 알고리즘 글 을 참고 할 수 있 습 니 다.