佇列

Queue
Queue
用大O符號表示的時間複雜度
演算法
演算法
空間
搜尋
插入
刪除

佇列，又稱為隊列（queue），電腦科學中的一種抽象資料型別，是先進先出（FIFO, First-In-First-Out）的線性表。在具體應用中通常用鏈結串列或者陣列來實現。佇列只允許在後端（稱為rear）進行插入操作，在前端（稱為front）進行刪除操作。

佇列的操作方式和堆疊類似，唯一的區別在於佇列只允許新數據在後端進行添加。

單鏈佇列

單鏈佇列使用鏈結串列作為基本數據結構，所以不存在偽溢位的問題，佇列長度也沒有限制。但插入和讀取的時間代價較高

儲存結構

/* c3-2.h 单链队列－－队列的链式存储结构 */
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
	QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

基本操作

/* bo3-2.c 链队列(存储结构由c3-2.h定义)的基本操作(9个) */
void InitQueue(LinkQueue *Q)
{	/* 构造一个空队列Q */
	(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
	if(!(*Q).front)
		exit(OVERFLOW);
	(*Q).front->next=NULL;
}

void DestroyQueue(LinkQueue *Q)
{	/* 销毁队列Q(无论空否均可) */
	while((*Q).front)
	{
		(*Q).rear=(*Q).front->next;
		free((*Q).front);
		(*Q).front=(*Q).rear;
	}
}

void ClearQueue(LinkQueue *Q)
{	/* 将Q清为空队列 */
	QueuePtr p,q;
	(*Q).rear=(*Q).front;
	p=(*Q).front->next;
	(*Q).front->next=NULL;
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
}

Status QueueEmpty(LinkQueue Q)
{	/* 若Q为空队列，则返回TRUE，否则返回FALSE */
	if(Q.front->next==NULL)
		return TRUE;
	else
		return FALSE;
}

int QueueLength(LinkQueue Q)
{	/* 求队列的长度 */
	int i=0;
	QueuePtr p;
	p=Q.front;
	while(Q.rear!=p)
	{
		i++;
		p=p->next;
	}
	return i;
}

Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免与bo2-6.c重名 */
{	/* 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR */
	QueuePtr p;
	if(Q.front==Q.rear)
		return ERROR;
	p=Q.front->next;
	*e=p->data;
	return OK;
}

void EnQueue(LinkQueue *Q,QElemType e)
{	/* 插入元素e为Q的新的队尾元素 */
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p) /* 存储分配失败 */
		exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	(*Q).rear->next=p;
	(*Q).rear=p;
}

Status DeQueue(LinkQueue *Q,QElemType *e)
{	/* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR */
	QueuePtr p;
	if((*Q).front==(*Q).rear)
		return ERROR;
	p=(*Q).front->next;
	*e=p->data;
	(*Q).front->next=p->next;
	if((*Q).rear==p)
		(*Q).rear=(*Q).front;
	free(p);
	return OK;
}

void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
{	/* 从队头到队尾依次对队列Q中每个元素调用函数vi() */
	QueuePtr p;
	p=Q.front->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
}

^[1]

迴圈佇列

迴圈佇列可以更簡單防止偽溢位的發生，但佇列大小是固定的。

// 队列的顺序存储结构(循环队列)
#define MAX_QSIZE 5 // 最大队列长度+1
typedef struct {
    int *base; // 初始化的动态分配存储空间
    int front; // 头指针，若队列不空，指向队列头元素
    int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;


// 构造一个空队列Q
SqQueue* Q_Init() {
    SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue));
    // 存储分配失败
    if (!Q){
        exit(OVERFLOW);
    }
    Q->base = (int *)malloc(MAX_QSIZE * sizeof(int));
    // 存储分配失败
    if (!Q->base){
        exit(OVERFLOW);
    }
    Q->front = Q->rear = 0;
    return Q;
}

// 销毁队列Q，Q不再存在
void Q_Destroy(SqQueue *Q) {
    if (Q->base)
        free(Q->base);
    Q->base = NULL;
    Q->front = Q->rear = 0;
    free(Q);
}

// 将Q清为空队列
void Q_Clear(SqQueue *Q) {
    Q->front = Q->rear = 0;
}

// 若队列Q为空队列，则返回1；否则返回-1
int Q_Empty(SqQueue Q) {
    if (Q.front == Q.rear) // 队列空的标志
        return 1;
    else
        return -1;
}

// 返回Q的元素个数，即队列的长度
int Q_Length(SqQueue Q) {
    return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
}

// 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
int Q_GetHead(SqQueue Q, int &e) {
    if (Q.front == Q.rear) // 队列空
        return -1;
    e = Q.base[Q.front];
    return 1;
}

// 打印队列中的内容
void Q_Print(SqQueue Q) {
    int p = Q.front;
    while (Q.rear != p) {
        cout << Q.base[p] << endl;
        p = (p + 1) % MAX_QSIZE;
    }
}

// 插入元素e为Q的新的队尾元素
int Q_Put(SqQueue *Q, int e) {
    if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满
        return -1;
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_QSIZE;
    return 1;
}

// 若队列不空，则删除Q的队头元素，用e返回其值，并返回1；否则返回-1
int Q_Poll(SqQueue *Q, int &e) {
    if (Q->front == Q->rear) // 队列空
        return -1;
    e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAX_QSIZE;
    return 1;
}

陣列佇列

#define MAX_QSIZE 10 // 最大队列长度+1
// 阵列队列的存储结构
struct Queue {
    int Array[MAX_QSIZE]; // 阵列空间大小
    int front; // 队头
    int rear; // 队尾
    int length; // 队列长度
};

// 构造一个空队列Q
Queue* Q_Init() {
    Queue *Q = (Queue*)malloc(sizeof(Queue));
    if (!Q){
        // 存储分配失败
        exit(OVERFLOW);
    }
    //初始化
    Q->front = Q->rear = Q->length = 0;
    return Q;
}

// 将Q清为空队列
void Q_Clear(Queue *Q) {
    //清除头尾下标和长度
    Q->front = Q->rear = Q->length = 0;
}

// 入列
int Q_Put(Queue *Q, int x) {
    //如果当前元素数量等于最大数量 返回 -1
    if (Q->rear + 1 == MAX_QSIZE) {
        return -1;
    }
    Q->Array[Q->rear] = x;
    Q->rear = Q->rear + 1;
    //length + 1
    Q->length = Q->length + 1;
    return 1;
}

// 出列
int Q_Poll(Queue *Q) {
    //如果当前元素数量等于最大数量 返回 -1
    if (Q->front + 1 == MAX_QSIZE)
        return -1;
    int x = Q->Array[Q->front];
    Q->front = Q->front + 1;
    // 移出后減少1
    Q->length = Q->length - 1;
    return x;
}

參考文獻

^ 高一凡. 《数据结构》算法实现及解析 2004年10月第2版. 西安: 西安電子科技大學出版社. ISBN 9787560611761 （中文）.

參見

[1] 高一凡. 《数据结构》算法实现及解析 2004年10月第2版. 西安: 西安電子科技大學出版社. ISBN 9787560611761 （中文）.

[1]

閱論編數據結構
類型	集合容器
抽象類型	關聯陣列多重關連陣列（英語：Multimap）串列前向串列堆疊佇列雙端佇列優先佇列雙端優先佇列集合多重集併查集可持久化數據結構線段樹
陣列	字串位陣列環形緩衝區動態陣列雜湊表雜湊陣列樹（英語：Hashed array tree）稀疏矩陣
鏈（英語：Linked data structure）	關聯表（英語：Association list）鏈結串列跳躍列表鬆散鏈結串列（英語：Unrolled linked list）異或鏈結串列
樹	線段樹自平衡二叉搜尋樹 B樹二叉樹 AA樹 AVL樹紅黑樹平衡樹伸展樹二叉搜尋樹堆二叉堆積左偏樹二項堆斐波那契堆 R樹 R*樹 R+樹希爾伯特R樹（英語：Hilbert R-tree）希爾伯特字首樹雜湊樹
圖	有向圖有向無環圖二元決策圖無向圖確定性非迴圈有限自動機（英語：Deterministic acyclic finite state automaton）
數據結構術語列表