目录
1.1 特性
1.2 循环队列
1.3 链式队列
1.1 特性
队列是只允许再两端进行插入和删除操作的线性表，在队尾插入，在队头删除，插入的一段被称为“队尾”，删除的一端被称为“队头”。队列包括顺序队列(循环队列)、链式队列。
结构：先进先出FIFO
操作：创建、入列、出列、判空和满、清空
注意：为了避免假溢出问题，即队列前面还有空闲，但是队尾已经出现越界，所以在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进，需要引入循环队列。
循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。
1.2 循环队列
逻辑结构：线性结构
存储结构：顺序存储结构
操作：创建、入列、出列、判空、判满、清空
typedef int datatype;
typedef struct sequeue
{datatype data[N]; //循环队列的数组int rear; //入队端int front; //出队端
}sequeue_t;创空：
入列：
出列：
#include <stdio.h>
#include <stdlib.h>#define N 5
typedef int datatype;
typedef struct sequeue
{datatype data[N]; //循环队列的数组int rear; //入队端int front; //出队端
} sequeue_t;//创建一个空的队列
sequeue_t *createEmptySequeue()
{//1.开辟结构体大小空间sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));if (NULL == p){perror("p malloc err");return NULL;}//2.初始化p->front = 0; //使用的时候都是数组的下标p->rear = 0;return p;
}//判断队列是否为满
int isFullSequeue(sequeue_t *p)
{//思想上，舍去数组上的一个存储位置,用于判断队列是否为满(否则和判空区分不了)//先判断rear的下一个位置是否等于frontreturn (p->rear + 1) % N == p->front;
}//入列 data代表入列的数据
int inSequeue(sequeue_t *p, datatype data)
{//1. 判满if (isFullSequeue(p)){printf("is full\n");return -1;}//2. 将数据入列p->data[p->rear] = data;//3. 将尾向后移动一个单位p->rear = (p->rear + 1) % N; //0 1 2 3 4循环
}//判断队列是否为空
int isEmptySequeue(sequeue_t *p)
{return p->rear == p->front;
}//出列
datatype outSequeue(sequeue_t *p)
{//1.判空if (isEmptySequeue(p)){printf("isEmptySequeue\n");return -1;}//2.设临时变量保存队头数据datatype temp = p->data[p->front];//3.将队头向后移动一个单位p->front = (p->front + 1) % N;//4.返回刚才保存的要出列的数据return temp;
}//求队列的长度
int lengthSequeue(sequeue_t *p)
{//长度情况分为 rear >= front 和 rear < front//rear == front 就是空队列长度为0// if (p->rear >= p->front)// return p->rear - p->front;// else// return p->rear - p->front + N;return (p->rear - p->front + N) % N;
}//清空队列函数
void clearSequeue(sequeue_t *p)
{//思想：只要不为空就出列while (!isEmptySequeue(p))printf("%d ", outSequeue(p)); printf("\n");
}int main(int argc, char const *argv[])
{sequeue_t *p = createEmptySequeue();for (int i = 0; i < 5; i++)inSequeue(p, i);//最后一个元素装不进，会满clearSequeue(p); //0 1 2 3return 0;
}循环队列，如果数组的元素个数为N，那么队列中最多能够存储的数据数的多少？N-1 个
为什么？
答：rear后面队尾插入的时候，需要先判满：用rear的后一个元素和front判断如果相等就是满。也就是用队尾的后一个和头去做判断，用于判满，这样会造成一个空间的浪费。
1.3 链式队列
逻辑结构：线性结构
存储结构：链式存储
操作：创建、入列、出列、判空、清空
typedef int datatype;
typedef struct node
{datatype data;struct node *next;
}link_node_t,*link_node_p;//将队列头指针和尾指针封装到一个结构体里
typedef struct queue
{link_node_p front; //相当于队头的指针link_node_p rear; //相当于队尾的指针
}linkqueue_t;
//有了头尾指针就可以操作这个链表了，并且记录头和尾就可以实现队列的功能。创空：
入列：
#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node
{datatype data;struct node *next;
} link_node_t, *link_node_p;//将队列头指针和尾指针封装到一个结构体里
typedef struct queue
{link_node_p front; //相当于队头的指针link_node_p rear; //相当于队尾的指针
} linkqueue_t;
//有了头尾指针就可以操作这个链表了，并且记录头和尾就可以实现队列的功能。//创建一个空的队列，用有头链表。
linkqueue_t *createEmptyLinkQueue()
{//1.申请队列结构体空间linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));if (NULL == p){perror("p malloc err");return NULL;}//2. 初始化，将头尾指针指向头节点。p->front = p->rear = (link_node_p)malloc(sizeof(link_node_t));if (NULL == p->front) //用任意一个做判断就可以，因为他俩都指向头节点{perror("p->front malloc err");return NULL;}//3. 初始化头节点p->front->next = NULL; //注意：先用头或尾指针找到头节点，再找头节点中的指针域nextreturn p;
}//入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p, datatype data)
{//1.创建一个新节点link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));if (NULL == pnew){perror("pnew malloc err");return -1;}//2.初始化新节点pnew->data = data;pnew->next = NULL;//3.链接新节点到链表尾巴p->rear->next = pnew;//4.移动尾指针到新节点p->rear = pnew; //rear保证一直指向当前链表的尾巴return 0;
}//判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p)
{return p->front == p->rear;
}//出列
//思想：每次释放front所指节点，然后移动front到后一个节点返回当前节点数据
datatype outLinkQueue(linkqueue_t *p)
{//1.判空if (isEmptyLinkQueue(p)){printf("isEmptyLinkQueue\n");return -1;}//2.定义指针pdel指向当前p->front所指节点link_node_p pdel = p->front;//3.将front 向后移动一个单位，去做新的头节点p->front = p->front->next;//4.释放pdelfree(pdel);//5.将当前front所指节点中数据出列，那此时这个节点为新的头节点，因为数据域无效。return p->front->data;return 0;
}//清空
void clearLinkQueue(linkqueue_t *p)
{while (!isEmptyLinkQueue(p))printf("%d ", outLinkQueue(p));printf("\n");
}//求队列长度的函数
int lengthLinkQueue(linkqueue_t *p)
{int len = 0;link_node_p h = p->front;while (h->next != NULL){len++;h = h->next;}return len;
}int main(int argc, char const *argv[])
{linkqueue_t *p = createEmptyLinkQueue();for (int i = 1; i <= 5; i++)inLinkQueue(p, i);printf("len=%d\n", lengthLinkQueue(p));while (!isEmptyLinkQueue(p))printf("%d ", outLinkQueue(p)); //1 2 3 4 5printf("\n");return 0;
}用两个栈实现一个队列的功能？简述算法和思路
思路：设两个栈，一个用于in一个用于out
实现入队: 如果in栈没满直接入栈，如果满了出栈之后入out栈，这样先入栈的会在out栈的栈顶。
实现出列: 如果out栈不为空直接让数据出栈，如果为空则把in栈的数据依次出栈入out栈， 这样先入栈的数据会在out栈顶。然后再把数据出out栈，来实现出列功能。
这样可以实现队列的先入先出顺序功能。
