順序佇列的定義

和堆疊相反，佇列是一種先進先出的線性表，它只允許在表的一端進行插入，二在另一端洗掉元素，允許插入的一端叫隊尾，洗掉元素的一端叫對頭

typedef int status;
typedef int qeelemtype;

typedef struct {
	qeelemtype data[MAXSIZE];
	int front;//隊頭指標
	int rear;//隊尾指標
}squeue;

佇列初始化

//佇列初始化
status initsqueue(squeue *sq){
	sq->front = sq->rear = 0;
	return OK;
} 

佇列是否為空

//佇列是否為空
status emptysq(squeue *q){
	if(q->front == q->rear)
	return OK;
	else return FALSE;
} 

隊尾插入

//隊尾插入
status insqueue(squeue *q,qeelemtype e){
	if((q->rear+1)%MAXSIZE ==q->front)
	return ERROR;
	
	q->data[q->rear] = e;
	q->rear = (q->rear+1)%MAXSIZE;
	return OK;
} 

回傳隊頭

//回傳對頭
status gethead(squeue *q,qeelemtype *e){
	if(q->front == q->rear)
	return ERROR;
	*e = q->data[q->front];
	return OK;
} 

隊頭洗掉

//出隊 
status dqueue(squeue *q,qeelemtype *e) {
	if(q->front == q->rear)
	return ERROR;
	*e = q->data[q->front];
	q->front = (q->front+1)%MAXSIZE;
	return OK;
} 

雙端佇列

雙端佇列是限定插入和洗掉操作在表的兩端進行的線性表，但實際的應用卻很少

鏈佇列

單鏈佇列初始化

typedef int Status;
typedef int qeelemtype;

typedef struct QNode
{
	qeelemtype data;
	struct QNode* next;
}QNode,*Queueptr;
typedef struct
{
	Queueptr front;//隊頭指標
	Queueptr rear;//隊尾指標
}LinkQueue;

佇列初始化

//佇列初始化
Status InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (Queueptr)malloc(sizeof(QNode));
	if (!Q.front)exit(-1);
	Q.front->next = NULL;
	return OK;
}

銷毀佇列

//銷毀佇列
Status DestroyQueue(LinkQueue& Q)
{
	while (Q.front)
	{
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	return OK;
}

隊尾插入

//隊尾插入
Status EnQueue(LinkQueue& Q, qeelemtype e)
{
	Queueptr p = (Queueptr)malloc(sizeof(QNode));
	if (!p)exit(-1);
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return OK;
}

隊頭洗掉

//隊頭洗掉
Status DeQueue(LinkQueue& Q, qeelemtype& e)
{
	if (Q.front == Q.rear)return ERROR;
	Queueptr p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if (Q.rear == p) Q.rear = Q.front;
	free(p);
	return OK;
}

佇列的遍歷

//輸入元素↓
int PrintQueue(LinkQueue& Q)
{
	QueuePtr p;
	printf("鏈式佇列中的元素");
	if (Q.front->next != NULL)
	{
		p = Q.front->next;
		do
		{
			printf("%5d", p->data);
			p = p->next;
		} while (p != NULL);
	}
	else
		printf("佇列為空\n");
	printf("\n");
	return 0;
}//遍歷鏈式佇列

測驗

void main()
{
	int n, e, i;
	LinkQueue Q;
	InitQueue(Q);
	printf("\n"); printf("\n");
	printf("初始化佇列成功！");
	printf("\n"); printf("\n");

	printf("請輸入要進隊的元素個數：\n");
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		printf("請輸入要進隊的元素：\n");
		scanf("%d", &e);
		if (EnQueue(Q, e))
			printf("元素 %d 進隊成功\n", e);
		else
			printf("進隊失敗\n");
	}
	printf("\n");
	PrintQueue(Q);
	printf("\n"); printf("\n");
	printf("洗掉元素后的佇列：\n");
	printf("\n");
	DeQueue(Q, e);
	PrintQueue(Q);
	printf("\n"); printf("\n");
}

回圈佇列

當佇列處于圖d時，不可再繼續插入新的隊尾元素，否則會因為陣列越界導致代碼被破壞，如果繼續擴大空間的話，就造成了空間的浪費，所以我們將順序佇列假想成如下圖一樣的環狀空間，稱之為回圈佇列

回圈佇列有頭指標和尾指標：
頭指標指向對列頭部元素，隨著對列出隊而變化，元素入隊時不變化
尾指標指向對列尾部元素，隨著對列入隊而變化，元素出隊時不變化

• 所以我們只需移動指標來控制插入和洗掉元素
• 遍歷的時間復雜度為O（1）
• 插入、洗掉的時間復雜度為O（1）

此部分代碼借鑒李四老師的

初始化回圈佇列

/*
初始化回圈佇列
*/
Status InitSeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return ERROR;
	}
	queue->front = queue->rear = 0;
	return OK;
}

清空對列

/*
清空佇列
*/
Status ClearSeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return ERROR;
	}
	queue->front = queue->rear = 0;
	return OK;
}

判斷佇列是否為空

/*
判斷回圈佇列是否為空
*/
Status EmptySeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return ERROR;
	}
	if (queue->front == queue->rear)
	{
		return TRUE;
	}
	return FALSE;
}

回圈佇列的長度

/*
回圈佇列的元素個數
*/
int LengthSeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return ERROR;
	}
	if (queue->front == queue->rear)
	{
		return 0;
	}
	//留的那個空單元不算做元素個數 
	return (queue->rear - queue->front + QUEUESIZE) % QUEUESIZE;
}

獲取隊頭元素

/*
獲取回圈佇列頭元素
*/
Status GetHead(SeqQueue* queue)
{
	if (!queue)
	{
		return ERROR;
	}
	if (queue->front == queue->rear)
	{
		return ERROR;
	}
	return queue->data[queue->front];
}

隊尾插入

*
往隊尾添加元素
*/
Status AddQueue(SeqQueue* queue, EleType e)
{
	//隊滿或空指標
	if (!queue)
	{
		return ERROR;
	}
	//剛好隊尾再走一個單元就到隊頭，說明堆疊滿了，
	if ((queue->rear + 1) % QUEUESIZE == queue->front)
	{
		return ERROR;
	}
	queue->data[queue->rear] = e;
	queue->rear = (queue->rear + 1) % QUEUESIZE;//若到隊尾轉到陣列頭部
	return OK;
}

隊頭洗掉

/*
隊頭洗掉元素
*/
Status DelQueue(SeqQueue* queue, EleType* e)
{
	//空指標
	if (!queue)
	{
		return ERROR;
	}
	//隊空
	if (queue->front == queue->rear)
	{
		return ERROR;
	}
	*e = queue->data[queue->front];
	queue->front = (queue->front + 1) % QUEUESIZE;//若到隊尾轉到陣列頭部
	return OK;
}

佇列列印

void PrintfQueue(SeqQueue* queue)
{
	//空指標
	if (!queue)
	{
		return;
	}
	//隊空
	if (queue->front == queue->rear)
	{
		return;
	}
	int begin = queue->front;
	while (begin != queue->rear)
	{
		printf("%d,", queue->data[begin]);
		if (begin < QUEUESIZE - 1)
		{
			begin++;
		}
		else
		{
			begin = begin + 1 - QUEUESIZE;
		}

	}
	printf("\n");
	return;
}