队列

队列

#define MaxSize 10   			//定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];		//用静态的“数组”存放队列元素
    int front,rear;            	//对头指针和队尾指针
}SqQueue;                   	

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;
}

入队（循环队列）

bool EnQueue(SqQueue &Q,ElemType x){
	if((Q.rear+1)%MaxSize==Q.front)
        return false;
    Q.data[Q.rear]=x;					//新元素插入队尾
    Q.rear=[Q.rear+1]%MaxSize;			//队尾指针+1取模
    return true;
}

出队

bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];					//新元素插入队尾
    Q.front=[Q.front+1]%MaxSize;			//队尾指针+1取模
    return true;
}

队列链式实现

typedef struct LinkNode{		//链式队列结点
    ElemType data;			
    struct LinkNode *next;		
}LinkNode;

typedef struct{					//链式队列
    LinkNode *front,*rear;		//对列的对头和队尾指针
}LinkQueue;

初始化（带头结点）

void InitQueue(LinkQueue &Q){
    //初始时，front,rear都指向头结点
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

不带头结点

void InitQueue(LinkQueue &Q){
    //初始时，front,rear都指向NULL
	Q.front=NULL;
    Q.rear=NULL;
}

入队（带头结点）

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;		//新结点插入到rear之后
    Q.rear=s;			//修改表尾指针
}

入队（不带头结点）

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL){		//在空队列中插入第一个元素
        Q.front=s;			//修改对头队尾指针
        Q.rear=s;			
    }
    else{
        Q.rear->next=s;		//新结点插入到rear之后
    	Q.rear=s;			//修改rear指针
    }
}

出队（带头结点）

void EnQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)
        return false;		//空队
    LinkNode *p=Q.front->next;
    x=p->data;				//用变量x返回对头元素
    Q.front->next=p->next;	//修改结点的next指针
    if(Q.front==p)			//此次是最后一个结点出队
         Q.rear=Q.front;	//修改rear指针
    free(p);
    return true;
}

出队（不带头结点）

void EnQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==NULL)
        return false;		//空队
    LinkNode *p=Q.front;	//p指向此次出队结点
    x=p->data;				//用变量x返回对头元素
    Q.front=p->next;		//修改front指针
    if(Q.rear==p)			//此次是最后一个结点出队
        Q.front=NULL;		//front指向NULL
    	Q.rear=NULL;		//rear指向NULL
    free(p);
    return true;
}

双端队列