数据结构--------------队列

队列

  FIFO(first in first out)

#include<iostream>
#define OVERFLOW -2
#define OK 0
#define ERROR -1
#define MAXQSIZE 100

循环队列

//------------循环队列的顺序存储结构-----------

typedef struct
{
	QElemType *base;
	int front;
	int rear;
}SqQueue;

1）初始化  O(1)

Status InitQueue(SqQueue &Q)
{
   Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间	
   if(!Q.base) exit(OVERFLOW);  //储存分配失败
   Q.front =Q.rear =0;   //头尾指针为0，队列为空
   return OK; 
} 

2）求队列长度   O(1)

int  Queuelength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
} 

3）入队  O(1)

Status EnQueue(SqQueue &Q，QElemtype e)
{
	if((Q.rear+1)%MAXQSIZE==Q.front)//判满 
	 return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXQSIZE;
	return OK; 
} 

4）出队  O(1)

Status DeQueue(SqQueue &Q,QElemType &e)
{
   if((Q.front == Q.rear ))	return ERROR; //判空 
    e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXQSIZE;
	return OK;  
}

5）取队头元素  O(1)

SElenType GetHead(SqQueue Q)
{
	if(Q.front!=Q.rear) //判空 
	 return Q.base[Q.front];
}

循环链队的几条重要语句

1）队空  Q.front==Q.rear；

2）队满  (Q.front+1)&MAXQSZIE==Q.front;

3）入队 Q.rear=(Q.rear+1)%MAXQSZIE;

4）出队 Q.front=(Q.front+1)%MAXQSZIE;

5）队长 (Q.front-Q.rear+MAXQSZIE)%MAXQSZIE;

6）队的最大长度   MAXQSZIE-1;

链队

//------------链队的存储结构------

typedef struct QNode
{
      QElemType data;
	  struct QNode *next;	
}QNode,*QueuePtr; 
typedef struct
{
	QueuePtr front; //队头指针 
	QueuePtr rear;  //队尾指针 
}LinkQueue;

1）初始化  O(1)

Status InitQueue (LinkQueue &Q)
{
	Q.front=Q.rear=new QNode;  //生成的新结点作为头结点，队头和队尾指针指向该结点 
	Q.front->next=NULL;   //头结点指针域置空 
	return OK;
} 

2）入队  O(1)

Status EnQueue(LinkQueue &Q,QElemType e)
{
	QNode p;
	p=new QNode;  //创建新结点 
	p->date=e;    //将新节点的数据域置为e 
	p->next=NULL; //新结点的next域置空 
	Q.rear->next=p; // 新结点插入队尾 
	Q.rear=p;      //修改队尾指针 
	return OK;
} 

3）出队  O(1)

Status DeQueue(LinkQueue &Q,QElemtype &e)
{
	if(Q.front=Q.rear) return ERROR; //判空 
	QNode p;
	p=new QNode;    //新建结点 
	p=Q.front->next;  //p指向队头元素 
	e=p->data;        //e保存队头元素的值 
	Q.front->next=p->next; //修改头结点的指针域  即队头指针后移 
	if(Q.rear==p) Q.rear=Q.front; //最后一个元素被删，队尾指针指向头结点 
	delete p;         //释放原队头元素的空间
	return OK; 
}

4）取队头元素  O(1)

Selemtype Gethead(LinkQueue Q)
{
	if(Q.front!=Q.rear) //队列非空
	 return Q.front->next->data;   //返回队头元素的值，队头指针不变 
 } 

对于队列来说顺序存储较为方便