队列

循环队列

顺序存储

• 存储类型

typedef struct
{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

• 初始化

void InitQueue(SqQueue *Q)
{
    Q->rear = Q->front = 0;
}

• 判队空

int isEmpty(SqQueue *Q)
{
    if(Q->rear == Q->front)
        return 1;
    else
        return 0;
}

• 入队

int EnQueue(SqQueue *Q, ElemType x)
{
    if((Q->rear + 1)%MaxSize == Q->front)
        return 0;
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize;
    return 1;
}

• 出队

int DeQueue(SqQueue *Q, ElemType *x)
{
    if(Q->rear == Q->front)
        return 0;
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    return 1;
}

链式存储

• 存储结构

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

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

• 初始化

void InitQueue(LinkQueue *Q)
{
    Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q->front->next = NULL;
}

• 判队空

int isEmpty(LinkQueue *Q)
{
    if(Q->front == Q->rear)
        return 1;
    else
        return 0;
}

• 入队

void EnQueue(LinkQueue *Q, ElemType x)
{
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
}

• 出队

int DeQueue(LinkQueue *Q, ElemType *x)
{
    LinkNode *p;
    if(Q->front == Q->rear)
        return 0;
    p = Q->front->next;
    *x = p->data;
    Q->front->next = p->next;
    if(Q->rear == p)
        Q->rear = Q->front;
    free(p);
    return 1;
}