目录

一、链队列

1.1 定义链表

1.2 定义队列

1.3 创建一个队列

1.4 打印队列

 1.5 进队列

1.6 出队列

1.7 测试函数

1.8 完整代码及运行结果

二、循环队列

2.1  定义循环队列

2.2 初始化

2.3 进队列

2.4 出队列

2.5 输出队列

2.6 测试函数

2.7完整代码及运行结果

队列的操作与栈的操作相似，但与栈不同的是，队列遵循的是先进先出原则而非先进后出 ，而且队列的删除（即出队）是在队头进行而非队尾。

一、链队列

链队列的图示如下：

1.1 定义链表

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

1.2 定义队列

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

1.3 创建一个队列

 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;
}// of initQueue

1.4 打印队列

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

 1.5 进队列

 void enqueue(LinkQueuePtr paraQueuePtr, int paraElement) {
 	// Step 1. Creat a new node.
 	LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(LinkNodePtr));
 	tempNodePtr->data = paraElement;
 	tempNodePtr->next = NULL;
 	
 	// Step 2. Link to the existing rear.
 	paraQueuePtr->rear->next = tempNodePtr;
 	paraQueuePtr->rear = tempNodePtr;
 }// of enqueue

1.6 出队列

 
  int dequeue(LinkQueuePtr paraQueuePtr) {
  	int resultValue;
  	LinkNodePtr tempNodePtr;
  	
  	//Step 1. Is the queue empty.
  	//判断是否为空 
	if (paraQueuePtr->front == paraQueuePtr->rear) {
		printf("The queue is empty.rn");
		return -1;
	}// of if
	
	//Step 2. Change the queue.
	tempNodePtr = paraQueuePtr->front->next;
	resultValue = tempNodePtr->data;
	paraQueuePtr->front->next = paraQueuePtr->front->next->next;
	
	if (paraQueuePtr->rear == tempNodePtr) {
		paraQueuePtr->rear = paraQueuePtr->front;
	}// of if
	
	//Step 3. Free space.
	free(tempNodePtr);
	tempNodePtr = NULL;
	
	//Step 4. Return.
	return resultValue;
  }// of dequeue

1.7 测试函数

 void testLinkQueue() {
 	LinkQueuePtr tempQueuePtr;
 	tempQueuePtr = initQueue();
 	
 	enqueue(tempQueuePtr, 10);
 	enqueue(tempQueuePtr, 30);
 	enqueue(tempQueuePtr, 50);
 	
 	outputQueue(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);
 	outputQueue(tempQueuePtr);
 }// of testLinkQueue

1.8 完整代码及运行结果

完整代码：

#include
#include


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


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


 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;
}// of initQueue

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

 void enqueue(LinkQueuePtr paraQueuePtr, int paraElement) {
 	// Step 1. Creat a new node.
 	LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(LinkNodePtr));
 	tempNodePtr->data = paraElement;
 	tempNodePtr->next = NULL;
 	
 	// Step 2. Link to the existing rear.
 	paraQueuePtr->rear->next = tempNodePtr;
 	paraQueuePtr->rear = tempNodePtr;
 }// of enqueue
 
 
  int dequeue(LinkQueuePtr paraQueuePtr) {
  	int resultValue;
  	LinkNodePtr tempNodePtr;
  	
  	//Step 1. Is the queue empty.
  	//判断是否为空 
	if (paraQueuePtr->front == paraQueuePtr->rear) {
		printf("The queue is empty.rn");
		return -1;
	}// of if
	
	//Step 2. Change the queue.
	tempNodePtr = paraQueuePtr->front->next;
	resultValue = tempNodePtr->data;
	paraQueuePtr->front->next = paraQueuePtr->front->next->next;
	
	if (paraQueuePtr->rear == tempNodePtr) {
		paraQueuePtr->rear = paraQueuePtr->front;
	}// of if
	
	//Step 3. Free space.
	free(tempNodePtr);
	tempNodePtr = NULL;
	
	//Step 4. Return.
	return resultValue;
  }// of dequeue


 void testLinkQueue() {
 	LinkQueuePtr tempQueuePtr;
 	tempQueuePtr = initQueue();
 	
 	enqueue(tempQueuePtr, 10);
 	enqueue(tempQueuePtr, 30);
 	enqueue(tempQueuePtr, 50);
 	
 	outputQueue(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);
 	outputQueue(tempQueuePtr);
 }// of testLinkQueue
 
 
  int main() {
  	testLinkQueue();
  	return 1;
  }// of main

运行结果： 

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

二、循环队列

因受队尾入队，队头出队的限制，在入队和出队的操作中可能会出现“假溢出”的现象，实际上这时候的真实可用空间并未占满，为了解决这个问题，就有了下面的循环队列。

“假溢出”图示：

循环队列图示：

 

2.1  定义循环队列

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

2.2 初始化

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

2.3 进队列

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

2.4 出队列

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

2.5 输出队列

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

2.6 测试函数

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

2.7完整代码及运行结果

完整代码： 

#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(struct CircleIntQueue));
	resultPtr->head = 0;
	resultPtr->tail = 0;
	
	return resultPtr;
 }// of initQueue
 
 //进队 
 void enqueue(CircleIntQueuePtr paraPtr, int paraValue) {
 	if ((paraPtr->tail + 1) % TOTAL_SPACE == paraPtr->head) {
 		printf("Queue full.rn");
 		return;
	 }// of if 
	 
	 paraPtr->data[paraPtr->tail % TOTAL_SPACE] = paraValue;
	 paraPtr->tail ++;
 }// of enqueue
 
 
 int dequeue(CircleIntQueuePtr paraPtr) {
 	int resultValue;
 	if (paraPtr->head == paraPtr->tail) {
 		printf("No element in the queue.rn");
 		return -1;
	 }// of if
	 
	 resultValue = paraPtr->data[paraPtr->head % TOTAL_SPACE];
	 paraPtr->head ++;
	 
	 return resultValue;
 }// of dequeue
 

 void outputLinkQueue(CircleIntQueuePtr paraPtr) {
 	int i;
 	if (paraPtr->head == paraPtr->tail) {
 		printf("Empty queue.");
 		return;
	 }// of if 
	 
	 printf("Elements in the queue: ");
	 for (i = paraPtr->head; i < paraPtr->tail; i ++) {
	 	printf("%d ", paraPtr->data[i % TOTAL_SPACE]);
	 }// of for i
	 
	 printf("rn");
 }// of outputLinkQueue
 
 
 void testLinkQueue() {
 	int i = 10;
 	CircleIntQueuePtr tempPtr = initQueue();
 	for (; i < 16; i ++) {
 		enqueue(tempPtr, i);
	 }// of for i
	 
	 outputLinkQueue(tempPtr);
	 
	 for(i = 0; i <6; i ++) {
	 	printf("dequeue gets %drn", dequeue(tempPtr));
	 }//of for i
	 
	 enqueue(tempPtr, 8);
	 outputLinkQueue(tempPtr);
 }// of testLinkQueue
 

 int main() {
 	testLinkQueue();
 	return 1;
 }// of main
 

运行结果：

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 in the queue.
dequeue gets -1
No element in the queue.
dequeue gets -1
Elements in the queue: 8