队列的顺序存储结构

说白了,就是一个数组 ,然后在两端进行操作 ,两端用首队指针和尾指针分别指向 ,然后进行相关的删除,插入操作, 目的还是模拟现实对数据的处理

●描述队列

        •数据元素data , 元素具有同一类型ElemType ,最多为MaxSize(数组容量)

        •当前队首front

        •当前队尾 rear

定义队列的数据结构

typedef struct
{
	ElemType data[MaxSize];
	int front,rear;//队首和队尾指针
}SqQueue;

---

---

以上是我们的队列的存储结构, 队列中有存储数据的数组 ElemType data[MaxSize];

还有对数组进行操作的指针 front ,rear 

我们现在演示顺序队的操作:

---

初始的时候 , 是空队列 ,队首和队尾指针都指向空 

当元素入队的时候 , rear 后移,然后我们对其位置赋值元素 ,rear指向新元素

---

---

当出队的时候 ,front 是指向出队的元素的 ,当没有元素出队的时候 ,指向空 ,当出队的时候 ,front上移到 数组位序为 0的位置 ,并对其进行出队,  队首指针的下一个元素变成队首元素

下面我们分析 ,顺序队的四要素

● 队空条件 : front = rear

当队首指针 和 尾指针 重合的时候 ,我们就把最后一个新元素,进行了删除了 ,

所以队空条件 , 就是两者重合

---

● 队满条件 : rear = MaxSize - 1

因为我们数组坐标是从 0 开始算的 , 所以当队尾指针指向数组最后 一个位序时 , 队满

---

●元素 e 进队 : rear++ ; data[rear] = e;

我们队尾指针指向的是队列一个元素 , 所以 当我们要插入元素的时候 ,如果队列不满, 我们就把 指针所指的位序加一  ,然后把新元素进队就可以了

---

● 元素 e 出队: front ++ ; e = data[front];

我们这里 队首指针指向的是 , 队列第一个元素的前一个位置  , 所以当我们要进行出队操作的时候 , 我们才把 front 加一 ,然后指向第一个元素 ,符合 常识

(删除前,要判断是非是空队, 空队则无需删除)

初始化队列 InitQueue(q)

   ● 构造一个空队列 q ,然后将 front 和 rear 指针均设置成初始状态 ,即 -1 值.

//传入要构造的队列
void InitQueue(SqQueue *&q)
{
	q = (SqQueue *)malloc(sizeof(SqQueue));
	q -> front = q -> rear = -1;
}

---

这里把首尾指针道法都指向负一的妙处是: 我们一会儿插入元素时, 加一即可指向新元素

销毁队列 DestroyQueue(q)

● 释放队列 q 占用的存储空间

---

//传入要销毁的队列
void DestroyQueue(SqQueue *&q)
{
	free(q);
}

---

因为我们用数组来承接数据 ,结构单一 ,直接释放队列即可

判断队列是否为空 QueueEmpty(q)

        ●若队列 q 满足 q->front = q->rear 条件 , 则返回 true ; 否则返回 false.

---

//传入要判断是否为空的队列
bool QueueEmpty(SqQueue *q)
{
	return(q->front == q->rear);
}

---

•当初始的时候 , 队列内无元素 ,队首和队尾指针都指向 -1 , 当插入新元素的时候 , 尾指针指向新元素 ; 当我们删除元素的时候  , 队首指针指向要删除的元素 ;

所以当队首指针删除到队尾时候 , 栈为空 

进队列enQueue(q,e)

        ●条件

                •队列不满时

        ●操作

                •先将队尾指针 rear 增1 ,

                • 然后将新元素添加到该位置

---

---

//进队列 enQueue(q,e)
//传入要插入队列, 和新元素的值
bool enQueue(SqQueue *&q, ElemType e)
{
	//条件,队列不满
	if(q->rear = MaxSize-1)
	{
		return false;
	}
	//不满,则可以插入新元素,队尾指针自增,指向新元素位置
	q->rear++;
	//数组承接 ,所以更改位序即可
	q->data[q->rear] = e;
	//插入成功,返回true
	return true;
 
}

出队列 deQueue(q,e)

     ●条件

                •队列 q 不为空

     ● 操作

                •将队首指针 front 循环增 1

                •将该位置的元素赋值给 e

---

---

// 出队列 deQueue(q,e)
//传入要出队的队列地址指针,记录出队元素的地址
bool deQueue(SqQueue *&q,ElemType &e)
{
	//先判断是否队空,空则返回错误
	if(q -> front == q->rear)
	{
		return false;
	}
	//不空,则删除第一个队列元素,因为我们队首指针
	//初始指向的是第一个元素的前一个位置,所以,队首指针自增1,传出元素即可
	q -> front++;
	e = q->data[q->front];
	//传出成功,则返回true
	return true;
}

上述顺序队列的基本操作已经完成 , 我们会注意到顺序队列的一个问题 ,当队首指针和队尾指针指向数组的最后一个元素时 , 队列表示队空, 但是,我们之前的元素还每利用

---

---

所以我们 , 现在遇到的问题就是, 我们增加元素,删除元素 ,此操作不能循环执行 

那怎么办呢? 我们既然 进行操作的时候 ,首尾指针到达了数组尾部 不能继续执行 ,我们就把数组的首尾链接起来, 形成循环队列,详见下节