資料結構-佇列(環狀佇列)－書籍分享天地

什麼是佇列?

名Queue，是一種串列，是先進先出(first in first out)，就跟排隊一樣。

什麼是環狀佇列?

就跟蛇一樣，嘴咬尾巴就是環狀，在搭配上佇列，這樣的用途是為了避免浪費空間。

實作環狀佇列

結構

這次一樣會用結構，然後有三個變數，

queue是存放數值的陣列，然後只要是空的都會是0，這個很重要，幾乎所有判斷都靠他。

front是第一個進來的數值(人)，沒有人會以-1表示。

tail是最後一個進來的數值(人), 同上。

環狀

要形成環狀的話，可以使用"%"取餘數，只要超過陣列大小就會變成0。

思路

我看書上的寫法在比較的時候都是使用front跟tail來比，但是我這樣寫的話會有一些問題，所以我就在陣列初始化的時候給予0，就把0當作空值，這樣子不管是列印、新增、刪除都會方便很多。

完整程式碼

#include<iostream>
#include<cstring>


#define Max 5

typedef struct Queue
{
	int queue[Max] = {0};
	int front=-1;
	int tail=-1;
} QUEUE;
	

void add_queue(Queue *qu, int data)
{
	if(qu->queue[(qu->tail+1)%Max] == 0)
	{
		qu->tail+=1;
		qu->tail%=Max;
		qu->queue[qu->tail] = data;
	}
	
}	


void bye_queue(Queue *qu)
{
	
	if(qu->queue[(qu->front+1)%Max] != 0)
	{
		
		qu->front+=1;
		qu->front%=Max;
		qu->queue[qu->front] =0;
		
	}
}
		

void check_queue(Queue *qu)
{
	for(int i=0;i<Max;i++)
		if(qu->queue[i] == 0)
			std::cout<<i<<":NULL"<<std::endl;
		else
			std::cout<<i<<":"<<qu->queue[i]<<std::endl;
		
	std::cout<<"front:"<<qu->front<<std::endl;
	std::cout<<"tail:"<<qu->tail<<std::endl;
}



int main()
{
	Queue *queue;
	
	queue = new Queue;
	
	add_queue(queue, 10);
	add_queue(queue, 20);
	add_queue(queue, 30);
	add_queue(queue, 40);
	add_queue(queue, 50);
	add_queue(queue, 60);
	
	bye_queue(queue);
	bye_queue(queue);
	bye_queue(queue);
	bye_queue(queue);
	add_queue(queue, 60);
	add_queue(queue, 70);
	bye_queue(queue);
	add_queue(queue, 80);
	add_queue(queue, 90);
	add_queue(queue, 100);

	bye_queue(queue);
	bye_queue(queue);
	check_queue(queue);
	
	return 0;
}