title: 【对列】
date: 2023-09-28 21:18:45
tags: 数据结构

一：循环队列

循环队列的引入是为了克服==“假上溢”现象==。

1、存储结构

#define MAXQSIZE 100
typedef struct
{
	ElementType* base;
	int front;
	int rear;
}Queue;

front和rear是头尾指针（相对于数组），front指向第一个元素，rear指向最后一个元素的==下一个位置==

2、初始化

void InitQueue(Queue& q)
{
	q.base = new ElementType[MASQSIZE];//开辟空间
	if (!q.base) 	exit(OVERFLOW);//存储分配失败
	q.front = q.rear = 0;
}

3、入队

Status EnQueue(Queue& q, ElementType e)
{
	if ((q.rear + 1) % MAXQSIZE == q.front)
		return ERROR;		//队满
	q.base[q.rear] = e;
	q.rear = (q.rear + 1) % MAXQSIZE;
	return OK;
}

3、出队

Status DeQueue(Queue& q, ElementType &e)
{
	if (q.front == q.rear)
		return ERROR;		//队空
	e = q.base[q.front];
	q.front = (q.front + 1) % MAXQSIZE;
	return OK;
}

4、队列长度

int QueueLength(Queue q)
{
    return ( q.rear - q.front + MAXQSIZE ) % MAXQSIZE;
}

5、队满

int QueueFull(Queue q)
{
    return ( q.rear + 1 ) % MAXQSIZE == q.front;
}

二、链队列

链队带头结点

1、存储结构

typedef struct Node
{
	ElementType data;
	struct Node* next;
}Node;
typedef struct
{
	Node* front;//队头指针
	Node* rear;//队尾指针
}Queue;

2、链队的初始化

Status InitQueue(Queue& Q)
{
	Q.front = Q.rear = new Node;
	if(!Q.front)	 exit(OVERFLOW);
	Q.front->next = NULL;
	return OK;
}

3、链队的入队

Status EnQueue(Queue& Q, ElementType x)
{
	p = new Node;
	if (!p) 	exit(OVERFLOW);		//存储分配失败
	p->data = x;
	p->next = NULL;
//头插法    
	Q.rear->next = p;
	Q.rear = p;
	return OK;
}

4、链队的出队

Status DeQueue(Queue& Q, ElementType& x)
{
	if (Q.front == Q.rear)
		return ERROR;	//队列为空
	p = Q.front->next;	//p指向队头元素
	x = p->data;		//e保存队头元素的值
	Q.front->next = p->next;	
    if (Q.rear == p)	//如果最后一个元素被删，则队尾指针为空
		Q.rear = NULL;	
	free(p);		//释放原队头元素的空间
	return OK;
}

  如果队列Q中==**<font color='red'>最后一个元素被删除</font>**==了，则队列中没有元素了，

• Q.rear不指向任何元素，要修改并赋值NULL
• Q.front由于是头结点，所以其值始终不会改变

例题

例一

不设置头结点，就必须考虑

1. 初始时==链表是否为空==
2. 是否在**第一个结点前插入新结点**
3. 是否**删除结点后链表为空**

void EnQueue(node* rear,ElementType x)
{
    node* p=new node;
    p->data=x;
    if(rear==NULL)		//队列为空
    {	
        p->next=p;		
        rear=p;   
    }
    else
    {
        p->next=rear->next;
        rear->next=p;
        rear=p;
    }
}


status DeQueue(ElementType &x,node* rear)
{
    if(rear==NULL)		return ERROR;       
    node* p=rear->next;
    x=p->data;
    if(p==rear)		//删除后队列为空
        rear=NULL;
    else
        rear->next=p->next;
    free(p);
    return OK;
}