队列

队列是一种先进先出的线性表。

顺序存储

结构:

typedef struct _queue{
    int Front, Rear;
    int *Data;
    int MaxSize;
} *Queue;

相关操作:

Queue Create(int MaxSize);
int IsFull(Queue q);
void Add(Queue q, int Data);
int IsEmpty(Queue q);
int Delete(Queue q);    // 返回值为出队元素

创建队列:

Queue Create(int MaxSize){
    
    Queue q = (Queue)malloc(sizeof(struct _queue));
    q->Data = (int *)malloc((MaxSize + 1) * sizeof(int));
    q->Front = q->Rear = 0;
    q->MaxSize = MaxSize + 1;
    
    return q;
}

判断是否为空:

int IsEmpty(Queue q){
    
    return q->Front == q->Rear;
    
}
int IsFull(Queue q){
    
    return (q->Rear+1)%q->MaxSize == q->Front;
    
} 

入队:

void Add(Queue q, int Data){
    
    if(IsFull(q)){
        printf("队列满!\n");
        return ;
    }
    q->Rear = (q->Rear+1)%q->MaxSize;
    q->Data[q->Rear] = Data;
    
}

出队:

int Delete(Queue q){
    if(IsEmpty(q)){
        printf("队列空!\n");
        return ;
    }
    q->Front = (q->Front+1)%q->MaxSize;
    return q->Data[q->Front];
}

链式存储

结构:

typedef struct _node{
    int Data;
    struct _node *Next;
} *Node;

typedef struct _q{
    Node Front, Rear;
} *Queue;

相关操作:

Queue Create();
void Add(Queue q, int Data);
int Delete(Queue q);    // 返回值为出队元素
int IsEmpty(Queue q);

创建队列:

Queue Create(){
    
    Queue q = (Queue)malloc(sizeof(struct _q));
    q->Front = q->Rear = NULL;
    
    return q;
}

判断是否为空:

int IsEmpty(Queue q){
    
    return q->Front == NULL;
    
}

入队:

void Add(Queue q, int Data){
        
    Node temp = (Node)malloc(sizeof(struct _node));
    temp->Data = Data;
    temp->Next = NULL;
    if(q->Front == NULL){
        q->Front = temp;
        q->Rear = temp;    
    }else{
        q->Rear->Next = temp;
        q->Rear = temp;
    }
    
}

出队:

int Delete(Queue q){
    int temp;
    Node Front;
    
    if(IsEmpty(q)){
        printf("队列空!\n");
        return ;
    }
    
    temp = q->Front->Data;
    Front = q->Front;
    q->Front = q->Front->Next;
    free(Front);
    return temp;
    
}