队列的顺序存储

2023-11-22 10:23:22

一、队列的定义：

队列是只允许在一端进行插入，另一端进行删除的线性表
特点：先入队的元素先出队，先进先出
队尾：允许插入的一端
队头：允许删除的一端

front 指向队头元素
rear 指向队尾元素的后一个元素（下一个应该插入的位置）
注意：具体题目中的rear 和 front 可能会跟上面不同，代码实现会有所区别

二、队列的顺序存储的实现

1.定义与初始化

#define MaxSize 10

typedef struct 
{
	int data[MaxSize];  //静态数组存放队列
	int front,rear;     //队头指针和队尾指针
}SqQueue;

void InitQueue(SqQueue &Q)
{   
	//初始化时 队头、队尾指针指向0
	Q.rear = Q.front = 0;
}

void testQueue()
{
	SqQueue Q;//声明一个队列（顺序存储）

	InitQueue(Q);
}

2.入队与出队

循环队列：将存储空间在逻辑上变成“环状”

//入队
bool EnQueue(SqQueue &Q,int x)
{
	if(（Q.rear+1）%MaxSize == Q.front){  //队列已经满
		return false;
	}
	Q.data[Q.rear] = x;          //新元素插入队尾
	Q.rear = (Q.rear+1)%MaxSize;//队尾指针加1取模
	                           //将存储空间在逻辑上变成“环状”
}

//出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue &Q,int &x)
{
	if(Q.rear==Q.front){
		return false;
	}
	x = Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true;
}

3.判空和获取队头元素

//判空操作
bool QueueEmpty(SqQueue &Q)
{
	if(Q.rear==Q.front){
		return true;
	}else{
		return false;
	}
}

//获得队头元素的值 用x返回
bool GetHead(SqQueue &Q,int &x)
{
	if(Q.rear==Q.front){
		return false;
	}
	x = Q.data[Q.front];
	
	return true;
}

三、判断队满和队空

1.方案一（牺牲一个存储单元）

此时队满的情况下，会浪费一个存储空间，因为若继续存储，会使rear指向d，即rear == front,而这是判断队空的情况

#define MaxSize 10

typedef struct 
{
	int data[MaxSize];  //静态数组存放队列
	int front,rear;     //队头指针和队尾指针
}SqQueue

初始化时，让Q.rear = Q.front = 0;
队列已满的条件：队尾指针的再下一个位置是队头
（Q.rear+1）%MaxSize == Q.front
队列空的条件：Q.rear == Q.front
队列元素个数：（rear + MaxSize - front）%MaxSize

2.方案二(定义变量表示队列长度)

#define MaxSize 10

typedef struct 
{
	int data[MaxSize];  //静态数组存放队列
	int front,rear;     //队头指针和队尾指针
	int size;           //队列当前长度
	          
}SqQueue

初始化时，rear =front = 0;size = 0

队满条件：size == MaxSize;
队空条件：size == 0;

3.方案三（标记插入或删除操作）

#define MaxSize 10

typedef struct 
{
	int data[MaxSize];  //静态数组存放队列
	int front,rear;     //队头指针和队尾指针
	int tag;           //最近进行的是插入还是删除
	          
}SqQueue

初始化时，rear =front = 0;size = 0
删除时，tag = 0
插入时，tag = 1

队满条件：front == rear && tag== 1
队空条件：front == rear && tag == 0

码农公寓