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

怼烎@ 2022-04-22 12:48 160阅读 0赞

# 队列 #

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;   //返回队头元素的值，队头指针不变 
     }

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