c語言實作資料結構----隊列

隊列

像棧一樣，隊列也是資料結構中一種受限制的線性表，它是一種先進先出的資料結構，就和我們現實生活中的排隊一樣。

接下來我們一起來實作雙向隊列的一些方法

雙向隊列的線性存儲

雙向隊列的類型定義

typedef struct Deque{
	int *vect;	//存儲元素的位置
	size_t size;	//隊列可存儲元素的個數
	size_t cnt;		//目前元素個數
	size_t front;	//隊列頭位置
	//隊列尾位置可以通過頭位置+元素個數即front+cnt獲得	
}Deque;
           

雙向隊列的初始化

void deque_init(Deque *que,size_t size){
	que->vect = malloc(size*sizeof(int));
	if(que->vect == NULL){
		return;
	}
	que->size = size;
	que->cnt = 0;
	que->front = 0;
}
           

銷毀一個雙向隊列

void deque_destroy(Deque *que){
	free(que->vect);
	que->vect = NULL;
}
           

判斷隊列是否為空

bool deque_is_empty(Deque *que){
	return que->cnt == 0;
}
           

判斷隊列是否滿

bool deque_is_full(Deque *que){
	return que->cnt == que->size;
}
           

隊首入隊

void deque_push_front(Deque *que,int data){
	if(deque_is_full(que)){
		return;
	}
	que->front = que->front == 0?que->size-1:que->front+1;
	que->vect[que->front] = data;
	que->cnt++;
}
           

隊尾入隊

void deque_push_tail(Deque *que,int data){
	if(deque_is_full(que)){
		return;
	}
	que->vect[(que->cnt++ +que->front)%que->size] = data;
}
           

隊首出隊

int deque_pop_front(Deque *que){
	if(deque_is_empty(que)){
		return;
	}
	int data = que->vect[que->front];
	que->cnt--;
	que->front = (que->front+1)%que->size;
	return data;
}
           

隊尾出隊

int deque_pop_tail(Deque *que){
	if(deque_is_empty(que)){
		return;
	}
	int data = que->vect[(que->front+que->cnt-1)%que->size];
	que->cnt--;
	retur data;	
}
           

檢視隊首元素

int deque_peek_front(Deque *que){
	return que->vect[que->front];
}
           

檢視隊尾元素

int deque_peek_tail(deque *que){
	return que->vect[(que->front+que->cnt-1)%que->size];
}
           

周遊隊列

void deque_foreach(Deque *que,void(*func)(int)){
	size_t i;
	for(i=que->front;i<que->cnt+que->front;i++){
		func(que->vect[(que->cnt+que->front-1+i)%que->size]);
	}
}