队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
链式：用链表定义队列，头节点进入，末节点出队，实现先进先出。
图样： 代码实现： 1）定义队列这样俩个struct 有利于封装队列。
typedef struct LinkNode {
int data;
struct LinkNode* next;
}*LinkNodePtr;
typedef struct LinkQueue{
LinkNodePtr front;
LinkNodePtr rear;
}*LinkQueuePtr;
2）初始化队列
LinkQueuePtr initQueue(){
LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(LinkQueue));
//The header, the data is not uesful.
LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(LinkNode));
headerPtr->next = NULL;
resultPtr->front = headerPtr;
resultPtr->rear = headerPtr;
return resultPtr;
}
3）入队
void enqueue(LinkQueuePtr paraQueuePtr, int paraElement) {
//Step 1.Creat a new node
LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(LinkNode));
tempNodePtr->data = paraElement;
tempNodePtr->next = NULL;
//Step 2.Link to the existing rear
paraQueuePtr->rear->next = tempNodePtr;
//Step 3.It is the new rear.
paraQueuePtr->rear = tempNodePtr;
}
4）出队
int dequeue(LinkQueuePtr paraQueuePtr) {
int resultValue;
LinkNodePtr tempNodePtr;
//Step 1.Is the queue empty?
if (paraQueuePtr->front == paraQueuePtr->rear) {
printf("The queue is empty.n");
return -1;
}
//Step 2.Change the queue.
tempNodePtr = paraQueuePtr->front->next;
resultValue = tempNodePtr->data;
paraQueuePtr->front->next = tempNodePtr->next;
if (paraQueuePtr->rear == tempNodePtr) {
paraQueuePtr->rear = paraQueuePtr->front;
}
//Step 3.Free space.
free(tempNodePtr);
tempNodePtr = NULL;
//Step 4.Return.
return resultValue;
}//Of enqueue
5）测试代码
void testLinkQueue() {
LinkQueuePtr tempQueuePtr;
tempQueuePtr = initQueue();
enqueue(tempQueuePtr, 10);
enqueue(tempQueuePtr, 30);
enqueue(tempQueuePtr, 50);
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));
outputLinkQueue(tempQueuePtr);
}//Of test.
6）总代码
#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(LinkQueue)); //The header, the data is not uesful. LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(LinkNode)); headerPtr->next = NULL; resultPtr->front = headerPtr; resultPtr->rear = headerPtr; return resultPtr; }//Of initQueue void outputLinkQueue(LinkQueuePtr paraQueuePtr){ LinkNodePtr tempPtr = paraQueuePtr->front->next; if (tempPtr == NULL) { printf("The link queue is emptyrn"); return; } while (tempPtr != NULL) { printf("%d ", tempPtr->data); tempPtr = tempPtr->next; }//Of while printf("rn"); }//Of outputLinkQueue. void enqueue(LinkQueuePtr paraQueuePtr, int paraElement) { //Step 1.Creat a new node LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(LinkNode)); tempNodePtr->data = paraElement; tempNodePtr->next = NULL; //Step 2.Link to the existing rear paraQueuePtr->rear->next = tempNodePtr; //Step 3.It is the new rear. 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.n"); return -1; } //Step 2.Change the queue. tempNodePtr = paraQueuePtr->front->next; resultValue = tempNodePtr->data; paraQueuePtr->front->next = tempNodePtr->next; if (paraQueuePtr->rear == tempNodePtr) { paraQueuePtr->rear = paraQueuePtr->front; } //Step 3.Free space. free(tempNodePtr); tempNodePtr = NULL; //Step 4.Return. return resultValue; }//Of enqueue void testLinkQueue() { LinkQueuePtr tempQueuePtr; tempQueuePtr = initQueue(); enqueue(tempQueuePtr, 10); enqueue(tempQueuePtr, 30); enqueue(tempQueuePtr, 50); 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)); outputLinkQueue(tempQueuePtr); }//Of test. int main(void){ testLinkQueue(); return 0; }
用数组实现队列，用除余（%）实现循环，也是先进先出。
图样：这里附上满队和空对的图，说明满队所存放的不是数组的长度，为了区分满队和空对的判断。
及满队：(rear+1)%max = head
空对： rear%max = head
代码实现： 1）定义队列typedef struct CircleIntQueue {
int data[TOTAL_SPACE];
int head;
int tail;
}*CircleIntQueuePtr;
2）初始化队列
CircleIntQueuePtr initQueue() {
CircleIntQueuePtr resultPtr = (CircleIntQueuePtr)malloc(sizeof(CircleIntQueue));
resultPtr->head = 0;
resultPtr->tail = 0;
return resultPtr;
}
3）入队
void enqueue(CircleIntQueuePtr paraPtr, int paraValue) {
//Step 1.Is full
if ((paraPtr->tail + 1) % TOTAL_SPACE == paraPtr->head) {
printf("Queue is full.n");
return;
}
//Step 2.add
paraPtr->data[paraPtr->tail % TOTAL_SPACE] = paraValue;
paraPtr->tail ++;
}
4）出队
int dequeue(CircleIntQueuePtr paraPtr) {
int resultValue;
//Step 1.is empty
if (paraPtr->head == paraPtr->tail) {
printf("No element in the queue.n");
return -1;
}//Of if
//Step 2.get and change
resultValue = paraPtr->data[paraPtr->head % TOTAL_SPACE];
paraPtr->head++;
return resultValue;
}
5）测试代码
void testLinkQueue() {
int i = 10;
CircleIntQueuePtr tempPtr = initQueue();
for (;i < 16; i++) {
enqueue(tempPtr, i);
}//Of i
outputLinkQueue(tempPtr);
for (i = 0; i < 6; i++) {
printf("dequeue gets %dn", dequeue(tempPtr));
}//Of i
enqueue(tempPtr, 8);
outputLinkQueue(tempPtr);
}
6）总代码
#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(CircleIntQueue)); resultPtr->head = 0; resultPtr->tail = 0; return resultPtr; }//Of CircleIntQueuePtr. void enqueue(CircleIntQueuePtr paraPtr, int paraValue) { //Step 1.Is full if ((paraPtr->tail + 1) % TOTAL_SPACE == paraPtr->head) { printf("Queue is full.n"); return; } //Step 2.add paraPtr->data[paraPtr->tail % TOTAL_SPACE] = paraValue; paraPtr->tail ++; }//Of enqueue int dequeue(CircleIntQueuePtr paraPtr) { int resultValue; //Step 1.is empty if (paraPtr->head == paraPtr->tail) { printf("No element in the queue.n"); return -1; }//Of if //Step 2.get and change 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.n"); return; }//Of if printf("Element in the queue: "); for (i = paraPtr->head; i < paraPtr->tail; i++) { printf("%d ", paraPtr->data[i % TOTAL_SPACE]); }//Of for i printf("rn"); }//Of output. void testLinkQueue() { int i = 10; CircleIntQueuePtr tempPtr = initQueue(); for (;i < 16; i++) { enqueue(tempPtr, i); }//Of i outputLinkQueue(tempPtr); for (i = 0; i < 6; i++) { printf("dequeue gets %dn", dequeue(tempPtr)); }//Of i enqueue(tempPtr, 8); outputLinkQueue(tempPtr); }//Of test int main(void) { testLinkQueue(); return 0; }
我们可以看到循环链表大小固定，而链表式是可以一直增加的。
他们用于不同场景，列入餐厅就餐我们就用循环式，位置是有限的。
而在排队取餐时用的链表式。
回答老师的问题：
1）数组变量的空间分配是连续的
2）局部变量在该局部（该函数）中可以重复使用，一旦出了该函数，该变量被销毁，便不能再使用。
3）指针的地址，我理解为存储该指针的存储空间的名字（编号）;而指针的值，是指针所指向的变量的存储空间的名字（编号）。‘*’是取指针所指的空间所存储的值。
