队列

概念
- 图示
- - 时间复杂度
顺序表实现
- 结构体定义
- 队列的操作
- - 初始化
  - 入队
  - 出队
  - 清空和销毁
  - 只读接口
  - 判空判满
  - 获取有效元素个数
- 循环队列要点
链表实现
- 结构体定义
- 链式队列操作
- - 初始化
  - 入队
  - 出队
  - 销毁
  - 只读接口
- 总结

概念

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

是一种先进先出的线性表(First in first out)，允许插入的一端称为队尾，允许删除的一端叫做队头。

图示

基础数据结构——队列概念顺序表实现链表实现

时间复杂度

队尾入的时候：时间复杂度O(n);

队头出的时候：时间复杂度O(1).

而栈：不管是顺序栈还是链栈

入栈时间复杂度：O(1);

出栈时间复杂度：O(1)。

顺序表实现

难点：

1.如何将队列的入队以及出队时间复杂度都降低为O（1）？

我们数据不需要挪动，而是是让队头指针以及队尾指针来回走动，得把它臆想成一个环状

2.怎么将判空和判满操作区分开？

2.1：浪费一个尾部空间，当做标记位，当(rear+1)%MAXSIZE == front; 我们就认为已满

2.2：在结构体里多申请一个变量，当做标记位，保存的是队列的有效元素个数

3.怎么获取其队列有效元素个数？求队列的有效元素个数的公式是啥？

(rear - front + MAXQSIZE) % MAXQSIZE

结构体定义

typedef int ElemType;

#define MAXQSIZE 100
typedef struct Queue
{
	ElemType* base;//(1)
	int front;//(2)
	int rear;//(3)
	//int length;//有效元素个数
}Queue, * PQueue;

数据域指向malloc申请来的动态内存。
头指针，当队列不空的时间，保存是队头，指向的第一个元素的下标。
尾指针，当队列不空的时间，保存的是队尾，指向的下一个元素入队的下标。

队列的操作

//初始化
void Init_Queue(PQueue pq);

//入队 push
bool Push(PQueue pq, ElemType val);

//出队 pop 需要删除操作
bool Pop(PQueue pq, ElemType* rtval);

//top  获取队头元素值， 不需要删除操作
bool Top(PQueue pq, ElemType* rtval);

//获取其有效元素个数
int Get_length(PQueue pq);

//判空
bool IsEmpty(PQueue pq);

//判满
bool IsFull(PQueue pq);

//清空
void Clear(PQueue pq);

//销毁
void Destroy(PQueue pq);

//打印
void Show(PQueue pq);

初始化

//初始化
void Init_Queue(PQueue pq)
{
	assert(pq != nullptr);
	pq->base = (ElemType*)malloc(sizeof(ElemType) * MAXQSIZE);
	assert(pq->base != nullptr);

	pq->front = 0;
	pq->rear = 0;
	//pq->front = pq->rear = 0;
}

入队

//入队 push
bool Push(PQueue pq, ElemType val)
{
	assert(pq != nullptr);
	//如果队列已满 则入队不进去
	if (IsFull(pq))
		return false;

	pq->base[pq->rear] = val;
	//把它臆想成了一个环,所以rear向后跑的代码会有不同
	
	pq->rear = (pq->rear + 1) % MAXQSIZE;

	return true;
}

出队

//出队 pop 需要删除操作
bool Pop(PQueue pq, ElemType* rtval)
{
	assert(pq != nullptr);
	//如果队列为空  则不需要出队
	if (IsEmpty(pq))
		return false;

	*rtval = pq->base[pq->front];
	//把它臆想成了一个环,所以front向后跑的代码会有不同
	//pq->front++;//error
	pq->front = (pq->front + 1) % MAXQSIZE;

	return true;
}

清空和销毁

//清空
void Clear(PQueue pq)
{
	pq->front = pq->rear = 0;
}

//销毁
void Destroy(PQueue pq)
{
	assert(pq != nullptr);

	free(pq->base);
	pq->base = nullptr;
	pq->front = pq->rear = 0;
}

只读接口

//top  获取队头元素值， 不需要删除操作
bool Top(PQueue pq, ElemType *rtval)
{
	assert(pq != nullptr);
	//如果队列为空  则不需要出队
	if(IsEmpty(pq))
		return false;

	*rtval = pq->base[pq->front];
	//不需要将front指针改变

	return true;
}

//获取其有效元素个数
int Get_length(PQueue pq)
{
	assert(pq != nullptr);

	int length = (pq->rear - pq->front + MAXQSIZE) % MAXQSIZE;
	return length;
}

//判空
bool IsEmpty(PQueue pq)
{
	return pq->front == pq->rear;
}

//判满
bool IsFull(PQueue pq)
{
	return (pq->rear+1)%MAXQSIZE == pq->front;
}

void Show(PQueue pq)
{
	for(int i=pq->front; i!=pq->rear; i=(i+1)%MAXQSIZE)
	{
		printf("%d ", pq->base[i]);
	}
	printf("\n");
}

判空判满

基础数据结构——队列概念顺序表实现链表实现

获取有效元素个数

基础数据结构——队列概念顺序表实现链表实现

循环队列要点

一共需要知道三个要点：

第一个：为了使队列的入队和出队的时间复杂度都为O（1），所以我们需要将其臆想成一个环形。

第二个：判空和判满操作的判断依据出现了冲突，都是rear==front; 所以我们需要浪费一个尾部节点，当做标记位，当尾指针再向后跑一步就遇到了头指针，此时我们就认为队列满了。

第三个：求队列有效元素个数的公式为：(rear - front + MAXQSIZE) % MAXQSIZE，加上一个MAXQSIZE的作用是为了防止（rear-front）出现负数，后边的%MAXQSIZE的作用是防止多加了。

链表实现

其实就是线性表的单链表，只不过它只能尾进头出

基础数据结构——队列概念顺序表实现链表实现

结构体定义

typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node* next;
}Node, *PNode;

//对头结点重新设计其结构体
typedef struct Head
{
	struct Node* front;	//(1)
	struct Node* rear;	//(2)
	//int length	//(3)
}Head, *PHead;

一直指向第一个节点。
一直指向最后一个节点。
若需要频繁获取其有效长度再加上

链式队列操作

//初始化
void Init_LQueue(PHead pqueue);

//入队
bool Push(PHead pqueue, ElemType val);

//出队
bool Pop(PHead pqueue, ElemType* rtval);

// 获取队列顶部元素
bool Top(PHead pqueue, ElemType* rtval);

//获取其有效长度个数 
int Get_Length(PHead pqueue);

//判空
bool IsEmpty(PHead pqueue);
//

//清空
void Clear(PHead pqueue);

//销毁
void Destory(PHead pqueue);

//打印
void Show(PHead pqueue);

初始化

//初始化
void Init_LQueue(PHead pqueue)
{
	assert(pqueue != nullptr);
	if (pqueue == nullptr)
	{
		return;
	}

	pqueue->front = nullptr;
	pqueue->rear = nullptr;
}

空队列：

基础数据结构——队列概念顺序表实现链表实现

入队

//入队
bool Push(PHead pqueue, ElemType val)
{
	assert(pqueue != nullptr);

	//申请新节点
	Node* pnewnode = (Node*)malloc(sizeof(Node) * 1);
	assert(pnewnode != nullptr);
	pnewnode->data = val;

	//找到合适的插入位置,分情况
	//若插入的时候里面没有数据
	if (pqueue->front == nullptr)
	{
		pnewnode->next = nullptr;
		pqueue->front = pnewnode;
		pqueue->rear = pnewnode;
	}
	else
	{
		pnewnode->next = pqueue->rear->next;
		pqueue->rear->next = pnewnode;
		pqueue->rear = pnewnode;
	}

	return true;
}

出队

//出队
bool Pop(PHead pqueue, ElemType* rtval)
{
	assert(pqueue != nullptr && rtval != nullptr);
	if (pqueue->front == nullptr)
	{
		return false;
	}

	//找到删除的位置	头删，不需要找

	//删除
	if (pqueue->front->next == nullptr)
	{
		Node* p = pqueue->front;
		*rtval = p->data;	//通过输出参数把数据带出去
		free(p);
		p = nullptr;

		pqueue->front = pqueue->rear = nullptr;
	}
	else
	{
		Node* p = pqueue->front;
		pqueue->front = p->next;
		*rtval = p->data;
		free(p);
		p = nullptr;
	}

	return true;
}

销毁

//销毁
void Destory(PHead pqueue)
{
	while (pqueue->front != nullptr)
	{
		Node* p = pqueue->front;
		pqueue->front = p->next;
		free(p);
		p = nullptr;
	}
}

只读接口

// 获取队列顶部元素
bool Top(PHead pqueue, ElemType* rtval)
{
	assert(pqueue != nullptr && rtval != nullptr);
	if (pqueue->front == nullptr)
	{
		return false;
	}

	*rtval = pqueue->front->data;

	return true;
}

//获取其有效长度个数 
int Get_Length(PHead pqueue)
{
	assert(pqueue != nullptr);
	
	int count = 0;
	Node* p = pqueue->front;
	for (p; p != nullptr; p = p->next)
	{
		count++;
	}

	return count;
}

//判空
bool IsEmpty(PHead pqueue)
{
	return pqueue->front == nullptr;
}

//打印
void Show(PHead pqueue)
{
	assert(pqueue != nullptr);

	Node* p = pqueue->front;
	for (p; p != nullptr; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

总结

对于循环队列与链队列的比较

可以从两方面来考虑

从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。

对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

基础数据结构——队列概念顺序表实现链表实现

队列

概念

图示

时间复杂度

顺序表实现

结构体定义

队列的操作

初始化

入队

出队

清空和销毁

只读接口

判空判满

获取有效元素个数

循环队列要点

链表实现

结构体定义

链式队列操作

初始化

入队

出队

销毁

只读接口

总结

继续阅读