데이터 구조선형 표순서 대기 행렬순환 대기 행렬체인 큐

#pragma mark --abstract
//  (queue)             ,              ,           (rear)
//           (font),            
//          (FIFO   )


#pragma mark --  
//1.               (sequential queue),                           .    :                      ,                           

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#pragma mark --       

#if 0
#define maxsize 10 //         
typedef int elemtype;
typedef struct {

    elemtype elem[maxsize];
    int font,rear;

}sequeuetp;
#endif
//  sa sequeuetp      
//    
//sq.rear=sq.rear+1;
//sq.elem[sq.rear]=x;

//    
//sq.font=sq.font+1

//   sq.font=sq.rear

//   sq.rear=maxsize ,        ,    
//2.    
//    ,   sq.elem[0]  sq.elem[maxsize-1]  ,                  1  
//  
//sq.rear=(sq.rear+1)%maxsize
//sq.elem[sq.rear]=x;

//  
//sq.font=(sq.font+1)%maxsize

//  sq.rear=sq.font;
//   (sq.rear+1)%maxsize=sq.font;

#pragma mark -------------       --------------------
#define maxsize 11 //(         10 +1)
typedef int elemtype;

typedef struct {

    elemtype elem[maxsize];
    int font,rear;

}cqueuetp;

#pragma mark --        
void initQueue(cqueuetp*cq) {

    cq->font=0;
    cq->rear=0;

}

#pragma mark         
bool QueueEmpty(cqueuetp*cq) {

    return (*cq).font==(*cq).rear?true:false;
}

#pragma mark       
int size(cqueuetp*cq) {
//   maxsize     cq->rear -cq->font<0   
    return (maxsize+cq->rear-cq->font)%maxsize;
}

#pragma mark        

elemtype Head(cqueuetp*cq) {

    if (cq->rear==cq->font) {//       
        return NULL;
    }
    else {

        return cq->elem[cq->font+1]%maxsize;
    }

}

#pragma mark     
void EntrayQueue(cqueuetp*cq,elemtype x) {

    if ((cq->rear+1)%maxsize==cq->font) { //  
        printf("overflow
");
    }
    else {

        cq->rear=(cq->rear+1)%maxsize;
        cq->elem[cq->rear]=x;
    }

}

#pragma mark     

elemtype DeletQueue(cqueuetp*cq) {

    if ((*cq).font==(*cq).rear) {
        return NULL;
    }else {

        cq->font=(cq->font+1)%maxsize;
        return (cq->elem[cq->font]);
    }

}


#pragma mark ------------------   ---------------------
//         ,                 ,             
//              (linked queue),                      ,
//        ,        ,                  ,         
//    ,        ,         ,  O(1)  O(n)

//      lq.front=lq.rear;


#pragma mark --      
typedef struct node{

    elemtype data;
    struct node*next;;

}nodetype;
typedef struct {
    nodetype *front;
    nodetype *rear;

}lqueue;

#pragma mark --   
void initLqueue(lqueue*lq) {
    //       
    lq->front=(nodetype*)malloc(sizeof(nodetype));
    lq->front->next=NULL;
    lq->rear=lq->front;

}

#pragma mark --  
bool EmptyLqueue(lqueue*lq) {

    return lq->front==lq->rear?true:false;
}

#pragma mark --   
int lqSize(lqueue*lq) {

    int i=0;
    nodetype*p=lq->front->next;
    while (p) {
        i++;
        p=p->next;
    }
    return i;
}

#pragma mark --        

elemtype getHead(lqueue*lq) {

    if (lq->front==lq->rear) {
        return NULL;
    }
    else {

        return lq->front->next->data;
    }

}

#pragma mark     
void EntryQueue(lqueue*lq,elemtype x){
    nodetype*s;
    s=(nodetype*)malloc(sizeof(nodetype));
    s->data=x;
    s->next=NULL;
    lq->rear->next=s;
    lq->rear=s;


}

#pragma mark     

elemtype delQueue(lqueue*lq){

    elemtype x;
    nodetype*p;
    if (lq->front==lq->rear) {
        return NULL;
    }
    else {

        p=lq->front->next;
        lq->front->next=p->next;
        if (p->next==NULL) //            ,          
            lq->rear=lq->front;


            x=p->data;
            free(p);
            return x;


    }

}

#pragma mark   
//1>        ,         
//2>       ,          ,           ,               ,            
//3>       ,     ,        ,            ,