数据结构——队列（Queue）

一、队列的基本概念

1. 定义
   队列（Queue）是一种先进先出（First In First Out，FIFO）的线性数据结构。

2. 特点
   • 只允许在**队尾（rear）插入，在队头（front）**删除。
   • 插入称为 入队（Enqueue），删除称为 出队（Dequeue）。

二、队列的抽象数据类型（ADT）描述

ADT Queue {
    Data: 线性序列
    Operations:
        enqueue(x)   // 入队
        dequeue()    // 出队并返回队首
        peek()       // 查看队首
        isEmpty()    // 判空
        size()       // 返回元素个数
}

三、队列的常见应用场景（如任务调度、消息队列、BFS算法等）

• 操作系统：进程/线程就绪队列、打印任务队列
• 网络：TCP 报文重组、消息队列（Kafka、RabbitMQ）
• 算法：BFS 层序遍历、滑动窗口最大值、缓存 LRU
• 前端：JS 事件循环宏任务/微任务队列

四、队列的实现方式

1. 基于数组的静态队列
   思路：用一段连续内存存储，维护 front、rear 两个索引。
   问题：出队后前面空间浪费 → 采用循环队列。

2. 基于链表的动态队列
   思路：用带头指针 front 和尾指针 rear 的单链表，无需考虑容量。

3. 循环队列（Circular Queue）
   • 逻辑上把数组视为环，模运算取余。
   • 牺牲一个空位或维护计数器区分空/满。
   • 优势：O(1) 入队/出队，空间利用率高。

五、队列的基本操作复杂度

操作	数组队列（循环）	链表队列	说明
Enqueue	O(1)	O(1)	尾插
Dequeue	O(1)	O(1)	头删
Peek	O(1)	O(1)	直接读 front
Size	O(1) 或 O(n)	O(1)	若维护计数器
Space	O(n)	O(n)	均与元素数成正比

六、队列的变种与扩展

1. 双端队列（Deque）
   两端都可插入删除，可用于滑动窗口最大值、撤销/重做。

2. 优先队列（Priority Queue）
   按优先级出队：二叉堆 O(log n)，斐波那契堆 O(1) amortized。

3. 阻塞队列（Blocking Queue）
   线程安全，满/空时阻塞等待，用于生产者-消费者。

4. 并发队列（Concurrent Queue）
   无锁 CAS 实现（如 Java ConcurrentLinkedQueue），高并发场景。

七、完整代码实现

#define  _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
#include<stdlib.h>
#define Maxsize 5
typedef int ElemType;
//队列的顺序存储结构和基本运算实现
typedef struct
{
	ElemType data[Maxsize];
	int front, rear;
}SqQueue;

// 1）初始化队列
void InitQueue(SqQueue & q)
{
	q.front = q.rear = -1;
}

//2) 判断队列是否为空
bool QueueEmpty(SqQueue* q)
{
	return (q->front == q->rear);
}
// 3)进队列
bool enQueue(SqQueue& q, ElemType e)
{
	if (q.rear == Maxsize - 1)//队满上溢出
		return false;
	q.rear++;
	q.data[q.rear] = e;
	return true;
}
// 4)出队列 
bool deQueue(SqQueue& q, ElemType& e)
{
	if (q.front == q.rear)//队空下溢出
		return false;
	q.front++;
	e = q.data[q.front];
	return true;
}
bool PrintQueue(SqQueue q)
{
	if (q.front == q.rear)//队空下溢出
		return false;
	int i = 0;
	while (i <= q.rear)
	{
		printf("%d->", q.data[i++]);
	}
	printf("end\n");
	return true;
}

int main()
{
	SqQueue	Q1;
	InitQueue(Q1);
	int x = 0;
	scanf("%d", &x);
	int i = Q1.rear;
	while (x != 9999 && Q1.rear <
		Maxsize - 1)
	{
		enQueue(Q1, x);
	    scanf("%d", &x);
	}
	PrintQueue(Q1);
	return 0;

}

//为了解决假溢出，引进循环队列 //循环队列会牺牲一个存储单元

// 1）初始化队列
void InitQueue1(SqQueue*& q)
{
	q = (SqQueue*)malloc(sizeof(SqQueue));
	q->front = q->rear = -1;
}
// 2) 销毁队列
void DestroyQueue1(SqQueue*& q)
{
	free(q);
}
//3) 判断队列是否为空
bool QueueEmpty1(SqQueue* q)
{
	return (q->front == q->rear);
}
// 4)进队列
bool enQueue1(SqQueue*& q, ElemType e)
{
	if ((q->rear+1)%Maxsize==q->front)//队满上溢出
		return false;
	q->rear=(q->rear+1)%Maxsize;
	q->data[q->rear] = e;
	return true;
}
// 5)出队列 
bool deQueue1(SqQueue*& q, ElemType& e)
{
	if (q->front == q->rear)//队空下溢出
		return false;
	q->front = (q->front+1)%Maxsize;
	e = q->data[q->front]; 
	return true;
}
//6)判断队满
/*队列的链式存储结构及其基本运算的实现*/

typedef struct qnode 
{
	ElemType data;
	struct qnode* next;//下一个结点指针
}DataNode;  //链队数据结点的类型
typedef struct 
{
	DataNode* front;//指向队头结点
	DataNode* rear;//指向队尾结点
}LinkQuNode;   //链队结点的类型  

// 1) 初始化队列
void InitLinkQueue(LinkQuNode*& q)
{
	q = (LinkQuNode*)malloc(sizeof(LinkQuNode));
	q->front = q->rear = NULL;
}
void DestroyLinkQueue(LinkQuNode*& q)
{
	DataNode* pre = q->front, * p;
	if (pre != NULL)
	{
		p = pre->next;
		while (p != NULL)
		{
			free(pre);
			pre = p;
			p = p->next;
		}
		free(pre);
	}
	free(q);
}
// 3）判断是否为空

bool LinkQueueEempty(LinkQuNode* q)
{
	return (q->rear == NULL);
}

// 4)进队列
bool  enLinkQueue(LinkQuNode*& q, ElemType e)
{
	DataNode* p = (DataNode*)malloc(sizeof(DataNode));
	p->data = e;
	p->next = NULL;
	if (q->rear == q->front) {//如果链队为空,不带头节点的第一个元素入队需要特殊处理
		q->rear = p;
		q->front = p;
	}else{
		q->rear->next = p;
		q->rear = p;
	}
	return true;
}
//5)出队列
bool deLinkQueue(LinkQuNode*& q, ElemType& e)
{
	if (q->rear==NULL)//链队为空
		return false;
	DataNode* p=q->front;
	e = p->data;
	q->front = p->next;  //移动
	if (q->rear == p)//当出队时，链队只有一个结点需要移动队尾指针
		q->front = q->rear = NULL;
	
	free(p);
	return true;
}

常见面试题与解答

Q1. 如何用两个栈实现队列？
答：入队压入栈 A，出队时若栈 B 空则把 A 全部倒入 B，B 弹出即 FIFO。均摊 O(1)。

Q2. 循环队列如何判断空/满？
答：① 牺牲一个单元 (rear+1)%cap==front 为满；② 额外计数器 size==capacity。

Q3. 队列与栈的区别？
答：队列 FIFO，栈 LIFO；栈可 DFS，队列可 BFS；两者可互相模拟（两栈/两队列）。

Q4. 线程安全的队列实现？
答：Java ArrayBlockingQueue, ConcurrentLinkedQueue; C++ std::queue + 互斥锁；无锁环形缓冲区（Disruptor）。