数据结构作业之链队列和循环队列

队列 (Queue)是一种先进先出(first in first out : FIFO)的线性表。它只允许在表的一端进行插入，在另一端进行删除元素。这和我们平时战队买票很一样。最早进入队列的元素最先离开，在队列中，允许插入的一端叫做队尾(rear),允许删除的一段则称为队头(front).示意图如下：

队列主要分为两类：

• 链式队列：链式队列即用链表实现的队列
• 顺序队列：顺序队列是用数组实现的队列，顺序队列通常必须是循环队列

#include 
#include 

 
typedef struct LinkNode{
	int data;
	struct LinkNode* next;
}*LinkNodePtr;
 
typedef struct LinkQueue{
	LinkNodePtr front;
	LinkNodePtr rear; 
}*LinkQueuePtr; 

这里要在第一个结构体的next前加上struct。

LinkQueuePtr initQueue(){
	LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(LinkQueuePtr));
	LinkNodePtr headerPtr=(LinkNodePtr)malloc(sizeof(LinkNodePtr));
	headerPtr->next=NULL;
	
	resultPtr->front=headerPtr;
	resultPtr->rear=headerPtr;
	
	return resultPtr;
} 

void outputLinkQueue(LinkQueuePtr paraQueuePtr){
	LinkNodePtr tempPtr=paraQueuePtr->front->next;
	while(tempPtr!=NULL){
		printf("%d ",tempPtr->data);
		tempPtr=tempPtr->next;
	}
	printf("rn");
} 

void enqueue(LinkQueuePtr paraQueuePtr,int paraElement){
	// Step 1. 创建一个空节点
	LinkNodePtr tempNodePtr=(LinkNodePtr)malloc(sizeof(LinkNodePtr));
	tempNodePtr->data=paraElement;
	tempNodePtr->next=NULL;
	
	// Step 2. 链接节点
	paraQueuePtr->rear->next=tempNodePtr;
	
	// Step 3. 队列尾部更新
	paraQueuePtr->rear=tempNodePtr; 
} 


int dequeue(LinkQueuePtr paraQueuePtr){
	int resultValue;
	LinkNodePtr tempNodePtr;
	
	// Step 1. 判断队列是否为空
	if(paraQueuePtr->front==paraQueuePtr->rear){
		printf("The queue is empty.rn");
		return -1;
	} 
	
	// Step 2. 改变队列
	tempNodePtr=paraQueuePtr->front->next;
	resultValue=tempNodePtr->data;
	paraQueuePtr->front->next=tempNodePtr->next;
	
	if(paraQueuePtr->rear==tempNodePtr){
		paraQueuePtr->rear=paraQueuePtr->front;
	} 
	
	// Step 3. 释放空间
	free(tempNodePtr);
//	tempNodePtr=NULL;
	
	// Step 4. Return
	return resultValue; 
} 

释放空间的两行代码都可以同时起到释放tempNodePtr的效果。

void testLinkQueue(){
	LinkQueuePtr tempQueuePtr;
	tempQueuePtr=initQueue();
	enqueue(tempQueuePtr,10);
	enqueue(tempQueuePtr,30);
	enqueue(tempQueuePtr,50);
	
	outputLinkQueue(tempQueuePtr);
	
	printf("dequeue gets %drn",dequeue(tempQueuePtr));
	printf("dequeue gets %drn",dequeue(tempQueuePtr));
	printf("dequeue gets %drn",dequeue(tempQueuePtr));
	printf("dequeue gets %drn",dequeue(tempQueuePtr));
	
	enqueue(tempQueuePtr,8);
	outputLinkQueue(tempQueuePtr);
}
 
int main(){
	testLinkQueue();
	return 0;
}

测试结果

10 30 50       
dequeue gets 10
dequeue gets 30
dequeue gets 50
The queue is empty.
dequeue gets -1
8

#include 
#include 

#define TOTAL_SPACE 5


typedef struct CircleIntQueue{
	int data[TOTAL_SPACE];
	
	int head;
	
	int tail;
}*CircleIntQueuePtr;

CircleIntQueuePtr initQueue(){
	CircleIntQueuePtr resultPtr=(CircleIntQueuePtr)malloc(sizeof(CircleIntQueuePtr));
	resultPtr->head=0;
	resultPtr->tail=0;
	
	return resultPtr;
} 

void enqueue(CircleIntQueuePtr paraPtr, int paraValue){
	if((paraPtr->tail+1)%TOTAL_SPACE==paraPtr->head){
		printf("Queue full.rn");
		return;
	}
	
	paraPtr->data[paraPtr->tail%TOTAL_SPACE]=paraValue;
	paraPtr->tail++;
}


int dequeue(CircleIntQueuePtr paraPtr){
	int resultValue;
	if(paraPtr->head==paraPtr->tail){
		printf("No element int the queue.rn");
		return -1;
	}
	
	resultValue=paraPtr->data[paraPtr->head%TOTAL_SPACE];
	paraPtr->head++;
	
	return resultValue;
}

void outputLinkQueue(CircleIntQueuePtr paraPtr){
	int i;
	if(paraPtr->head==paraPtr->tail){
		printf("Empty queue.");
		return;
	}
	
	printf("Elements in the queue: ");
	for(i=paraPtr->head;itail;i++){
		printf("%d, ",paraPtr->data[i%TOTAL_SPACE]);
	}
	
	printf("rn");
}

void testLinkQueue(){
	int i = 10;
	CircleIntQueuePtr tempPtr=initQueue();
	for(;i<16;i++){
		enqueue(tempPtr,i);
	}
	
	outputLinkQueue(tempPtr);
	
	for(i=0;i<6;i++){
		printf("dequeue gets %drn",dequeue(tempPtr));
	}
	
	enqueue(tempPtr,8);
	outputLinkQueue(tempPtr);
} 
 

int main(){
	testLinkQueue();
	return 0;
}

测试结果

Queue full.
Queue full.
Elements in the queue: 10, 11, 12, 13,
dequeue gets 10
dequeue gets 11
dequeue gets 12
dequeue gets 13
No element int the queue.
dequeue gets -1
No element int the queue.
dequeue gets -1
Elements in the queue: 8,

队列主要应用在和时间有关的操作。

常见的例子如现实生活中排队买票，银行排队处理事情。再如操作系统中执行队列，等待队列。又如我们在编写程序过程中的多线程编程，也需要通过队列来管理线程的访问顺序等。