顺序队列

基本概念

数据结构的三要素

• 逻辑结构
  • 线性结构
• 存储结构
  • 顺序存储
• 数据的运算

费曼理解

队列就是排队，先进来的就可以先出去

内部实现：

define MaxSize 10;
typedef struct {
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;

复杂度分析：

初始化

void InitQueue(SqQueue &Q){
	Q.front=0;
	Q.rear=0;
}

判断队列是否为空

bool QueueEmpty(SqQueue &Q){
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

入队

bool EnQueue(SqQueue &Q,ElemType e){
	//边界判断
	if(Q.rear-Q.front==MaxSize{
		return false;
	}
	Q.data[Q.rear]=e;
	Q.rear++;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

出队

bool OutQueue(SqQueue &Q.ElemType &e){
	//边界判断
	if(Q.rear==Q.front){
		return false;
	}
	e=Q.data[Q.front];
	Q.front++;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

应用场景：