数据结构第七天——队列，循环队列

一、队列

#include
#include


 
typedef struct LinkNode{
	int data;
	struct LinkNode *next;
} *LinkNodePtr;


 
typedef struct LinkQueue{
	LinkNodePtr front;
	LinkNodePtr rear;
} *LinkQueuePtr; 


 
LinkQueuePtr initQueue() {
	LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(struct LinkQueue));
	LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(struct LinkNode));
	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("n");
}


 
void enqueue(LinkQueuePtr paraQueuePtr, int paraElement) {
	LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(struct LinkNode));
	tempNodePtr->data = paraElement;
	tempNodePtr->next = NULL;
	
	paraQueuePtr->rear->next = tempNodePtr;
	
	paraQueuePtr->rear = tempNodePtr;
}


 
int dequeue(LinkQueuePtr paraQueuePtr) {
	int resultValue;
	LinkNodePtr tempNodePtr;
	
	if (paraQueuePtr->front == paraQueuePtr->rear) {
		printf("The queue is emptyn");
		return -1;
	}
	
	tempNodePtr = paraQueuePtr->front->next;
	resultValue = tempNodePtr->data;
	paraQueuePtr->front->next = paraQueuePtr->front->next->next;
	
	if (paraQueuePtr->rear == tempNodePtr) {
		paraQueuePtr->rear = paraQueuePtr->front;
	}
	
	return resultValue;
}

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

插入图示

删除图示

运行结果

二、循环队列

#include
#include


 
typedef struct circleIntQueue{
	int data[5];
	int head;
	int tail;
} *CircleIntQueuePtr;


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


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


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


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

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 %dn", dequeue(tempPtr));
	}
	
	enqueue(tempPtr, 8);
	outputLinkQueue(tempPtr);
}

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

 运行结果

 总结

1、free只能释放用malloc一类申请的空间，不要混淆了

2、循环队列，为了方便使用，选择空一个，用以区分队列满或者空的情况，如果（rear+1）==front，那么就是队列满，如果rear==front，那就是空

3、数组空间的内存分配时连续的

4、指针的地址，我的理解是指针的地址值，因为指针也是一个变量，所以指针的地址应该是存储该指针变量的地址，而指针的值应该是指针指向的变量的地址

5、局部变量的空间我觉得可以重复利用，首先C语音里，C语言对局部变量的分配机制是采用栈的方式，那么也就是说，如果一个变量，被编译器释放内存后，即出栈，再次进入时，重新申请，也就是入栈，那么其实空间地址是不变的，这里给出大佬链接，解答了疑惑https://blog.csdn.net/qq135595696/article/details/119655346