队列（C语言实现）_c语言队列

目录

一、队列的基本概念

1.队列的定义及其结构

2.队列的基本操作

二、队列的顺序存储结构

1.顺序存储

2.循环队列

3.循环队列实现

3.1循环队列定义

3.2 循环队列基本操作

3.3 功能实现（浪费一个空间的实现方式）

3.4 其他两种实现方式

三、队列的链式存储结构

1.链式存储队列定义

2.链式存储队列实现

四、双端队列（知识漏洞）

1.双端队列定义

2.输出受限的双端队列

3.输入受限的双端队列

4.特殊的双端队列

五、队列的应用

1.队列在层序遍历中的使用

2.队列实现栈

---

一、队列的基本概念

1.队列的定义及其结构

1.1 定义：队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出  FIFO(First In First Out)

2.队列的基本操作

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QueDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QueDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

二、队列的顺序存储结构

1.顺序存储

队列的顺序存储是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置（front与rear定义不固定）。

初始时：rear=front=0

进队操作：队不满时，先送值到队尾元素，再将队尾指针+1；

出队操作：队不空时，先取队头元素值，再将队头指针+1；

注：rear==MaxSize不能作为判断队满的条件，如图（d），队列中仅有一个元素，但仍满足rear==MaxSize，这时入队出现“上溢出”，但这种溢出并不是真正的溢出，在data数组中依然存在可以存放元素的空位置，所以这是一种“假溢出”。

2.循环队列

把存储队列元素的顺序表从逻辑上视为一个环，成为循环队列。

当队首指针front=MaxSize-1后，再前进一个位置就自动到0，利用除法取余运算实现。

初始时：front=rear=0；

队首指针进1：front=（front+1）%MaxSize

队尾指针进1：rear=（rear+1）%MaxSize

队列长度：（rear+MaxSize-front）%MaxSize

队尾元素下标（出错点）：(rear + MaxSize - 1)% MaxSize

出队入队时：指针都按顺时针方向进1

3.循环队列实现

MaxSize指的是定义的数组长度，并非队列的最大容量

比如：创建的队列容量为3，那么需要创建数组长度为4（因为要浪费一个空间），

此时的MaxSize为4

3.1循环队列定义

typedef  int DataType;
 
typedef struct {
    DataType* arr;
    int front;
    int rear;
    int MaxSize;
} MyCircularQueue;

3.2 循环队列基本操作

//判断队满
bool myCircularQueueIsFull(MyCircularQueue* obj);
//判断队空
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k);
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj);
//获取队首元素
int myCircularQueueFront(MyCircularQueue* obj);
//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj);
//队列销毁
void myCircularQueueFree(MyCircularQueue* obj);

3.3 功能实现（浪费一个空间的实现方式）

 
//判断队满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	return (obj->rear + 1) % obj->MaxSize == obj->front;
}
//判断队空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
	return obj->rear == obj->front;
}
//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    obj->arr = (DataType*)malloc( sizeof(DataType) * (k + 1));
    if (obj->arr == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    obj->front = 0;
    obj->rear = 0;
    obj->MaxSize = k+1;
    return obj;
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, DataType value)
{
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->arr[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->MaxSize;
    return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{ 
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front = (obj->front + 1) % obj->MaxSize;
    return true;
}
//获取队首元素
DataType myCircularQueueFront(MyCircularQueue* obj)
{
    assert(!myCircularQueueIsEmpty(obj));
    return obj->arr[obj->front];
}
//获取队尾元素
DataType myCircularQueueRear(MyCircularQueue* obj)
{
    assert(!myCircularQueueIsEmpty(obj));
    return obj->arr[(obj->rear + obj->MaxSize - 1)% obj->MaxSize] ;
}
//队列销毁
void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->arr);
    obj->arr = NULL;
    obj->front = 0;
    obj->rear = 0;
    obj->MaxSize = 0;
    free(obj);
}

3.4 其他两种实现方式

       核心在于区分队满与队空（两种情况都有rear==front）

（1）类型中增设表示元素个数的数据成员。

这样队空的条件为Q.size==0；

队满的条件为Q.size==MaxSize;

（2）类型中增设tag数据成员，以区分是队满还是队空。

tag等于0时，若因删除导致rear==front，则为队空

tag等于1时，若因插入导致rear==front，则为队满

三、队列的链式存储结构

1.链式存储队列定义

typedef int QueDataType;
 
typedef struct QueNode
{
	struct QueNode* next;
	QueDataType data;
}QueNode;
 
typedef struct Queue
{
	QueNode* front;
	QueNode* rear;
	int size;
}Queue

2.链式存储队列实现

 
/*
	以无头单链表实现
	头删出队列
	尾插入队列
*/
// 初始化队列 
void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
 
// 队尾入队列 
void QueuePush(Queue* q, QueDataType data)
{
	assert(q);
	//实际上就是单链表尾插
	QueNode* newNode = (QueNode*)malloc(sizeof(QueNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newNode->data = data;
	if (QueueEmpty(q))
	{
		q->front = newNode;
		q->rear = newNode;
	}
	else
	{
		q->rear->next = newNode;
		q->rear = q->rear->next;
	}
	q->size++;
}
 
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//实际上就是单链表头删
	if (q->size == 1 && q->front == q->rear)
	{
		QueNode* tmp = q->front;
		q->front == NULL;
		q->rear == NULL;
		free(tmp);
	}
	else
	{
		QueNode* tmp = q->front;
		q->front = q->front->next;
		free(tmp);
	}
	q->size--;
}
// 获取队列头部元素 
QueDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
// 获取队列队尾元素 
QueDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	if ( q->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	while (q->size != 0)
	{
		QueNode* tmp = q->front;
		q->front = q->front->next;
		free(tmp);
		q->size--;
	}
}

四、双端队列（知识漏洞）

1.双端队列定义

双端队列是指允许两端都可以进行入队和出队操作的队列。

其元素的逻辑结构仍是线性结构。将队列的两端称为前端和后端，两端都可以入队和出队。

2.输出受限的双端队列

允许在一段进行插入和删除，但另一端只允许插入的双端队列。

3.输入受限的双端队列

允许在一段进行插入和删除，但另一端只允许删除的双端队列。

4.特殊的双端队列

限定双端队列从某个端点插入的元素只能从该端点删除。

则该双端队列就蜕变为两个栈底相邻接的栈

五、队列的应用

1.队列在层序遍历中的使用

利用队列先进先出的性质

过程描述：

（1）根节点入队。

（2）若队空（所有结点都已处理完毕），则结束遍历；否则重复（3）的操作。

（3）队列中第一个结点出队，并访问之。若其有左孩子，则左孩子入队；若其有右孩子，则右孩子入队，返回（2）。

代码实现：

// 层序遍历
void BinaryTreeLevelOrder(tNode* root)
{
	if (root == NULL)
	{
		return;
	}
	Queue* que = (Queue*)malloc(sizeof(Queue));
	if (que == NULL)
	{
		perror("malloc fail");
		return;
	}
	QueueInit(que);
	QueuePush(que,root);
	while (!QueueEmpty(que))
	{
		tNode* node = QueueFront(que);
		printf("%d ", node->val);
		QueuePop(que);
		if (node->left != NULL)
		{
			QueuePush(que, node->left);
		}
		if (node->right != NULL)
		{
			QueuePush(que, node->right);
		}
	}
 
	QueueDestroy(que);
}

2.队列实现栈

思路：两个队列实现栈

push：若两个队列都为空，则是任意一个队列入队，否则，往非空的队列中入队

pop：将非空队列的数据依次出队，入队到另一个空队列直到剩下最后一个数据，将这个数据出队即完成出栈操作

top：非空队列的队尾是栈顶元素

关键在于：巧妙区分空队列和非空队列

typedef struct {
    Queue que1;
    Queue que2;
} MyStack;
 
 
MyStack* myStackCreate() {
    MyStack* st=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(st->que1));
    QueueInit(&(st->que2));
    return st;
}
 
void myStackPush(MyStack* obj, int x) {
    Queue* EmpQ =&(obj->que1);
    Queue* unEmpQ=&(obj->que2);
    if(!QueueEmpty(EmpQ))
    {
        unEmpQ=&(obj->que1);
        EmpQ=&(obj->que2);
    }
    QueuePush(unEmpQ,x);
}
 
int myStackPop(MyStack* obj) {
    Queue* EmpQ =&(obj->que1);
    Queue* unEmpQ=&(obj->que2);
    if(!QueueEmpty(EmpQ))
    {
        unEmpQ=&(obj->que1);
        EmpQ=&(obj->que2);
    }
    while(QueueSize(unEmpQ)>1)
    {
        int x=QueueFront(unEmpQ);
        QueuePop(unEmpQ);
        QueuePush(EmpQ,x);
    }
        int result=QueueFront(unEmpQ);
        QueuePop(unEmpQ);
        return result;
 
}
 
int myStackTop(MyStack* obj) {
    Queue* EmpQ =&(obj->que1);
    Queue* unEmpQ=&(obj->que2);
    if(!QueueEmpty(EmpQ))
    {
        unEmpQ=&(obj->que1);
        EmpQ=&(obj->que2);
    }
        int result=QueueBack(unEmpQ);
        return result;
}
 
bool myStackEmpty(MyStack* obj) {
    Queue* EmpQ =&(obj->que1);
    Queue* unEmpQ=&(obj->que2);
    if(QueueEmpty(EmpQ)&&QueueEmpty(unEmpQ))
    {
        return true;
    }
    return false;
}
 
void myStackFree(MyStack* obj) {
    Queue* EmpQ =&(obj->que1);
    Queue* unEmpQ=&(obj->que2);
    QueueDestroy(EmpQ);
    QueueDestroy(unEmpQ);
    free(obj);
}