앞장서지 않는 결점을 가진 체인 대기열과 비교

결론: 선두 노드의 체인 대기열을 조작하는 것이 더욱 편리하다.

앞장서지 않는 결점의 체인 대기열은 팀에 들어갈 때 첫 번째 요소를 특수 처리해야 한다.먼저 비어 있는지 판단한 다음에 삽입 방식을 선택하고 선두 결점은 이 조작이 필요하지 않다.

분석은 다음과 같습니다.

체인 대기열의 저장 유형은 다음과 같다.

typedef struct {
    ElemType data;
    strcut LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front;
    LinkNode *rear;
} LinkQueue;

1. 선두 노드의 체인 대기열

/* with a head node */
/* initialize the queue */
void InitQueue(LinkNode *Q)
{
    /* creat a head node */
    Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q->front->next = NULL;
}

/* judge whether the queue is empty */
bool IsEmpty(LinkNode *Q)
{
    if (Q->front == Q->rear) return true;
    else return false;
}

/* Push a element into the queue */
void EnQueue(LinkQueue *Q, ElemType x)
{
    LinkNode *S;
    S = (LinkNode*)malloc(sizeof(LinkNode));
    S->data = x;
    S->next = NULL;
    Q->rear->next = S;
    Q->rear = S;
}

/* Pop a element from the queue */
bool DeQueue(LinkNode *Q, ElemType *x)
{
    if (IsEmpty(Q)) return false;
    P = (LinkNode)malloc(sizeof(LinkNode));
    P = Q->front->next;
    *x = P->data;
    Q->front->next = P->next;
    if (Q->rear == P)
        Q->rear = Q->front;
    free(P);
    return true;
}

2. 앞장서지 않는 결점의 체인 대기열

/* with no head node */
/* initialize the queue */
void InitQueue(LinkNode *Q)
{
    Q->front = Q->rear = NULL;
}

/* judge whether the queue is empty */
bool IsEmpty(LinkNode *Q)
{
    if (Q->front == NULL) return true;
    else return false;
}

/* Push a element into the queue */
void EnQueue(LinkQueue *Q, ElemType x)
{
    LinkNode *S;
    S = (LinkNode*)malloc(sizeof(LinkNode));
    S->data = x;
    S->next = NULL;
    if (IsEmpty(Q)) {
        Q->front = Q->rear = S;
    } else {
        Q->rear->next = S;
        Q->rear = S;
    }
    return;
}

/* Pop a element from the queue */
bool DeQueue(LinkNode *Q, ElemType *x)
{
    if (IsEmpty(Q)) return false;
    P = (LinkNode)malloc(sizeof(LinkNode));
    P = Q->front;
    *x = P->data;
    if (Q->front == Q->rear) Q->front = Q->rear = NULL;
    else {
        Q->front = P->next;
    }
    free(P);
    return true;
}