1.顺序队列的原理
????????队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”，当线性表中没有元素时，称为“空队”，特点 ：先进先出（FIFO）。
typedef int datatype;
#define N 128
// 当front和rear的值相同时，表示队列为空，但对于循环队列来讲，满队时，front和rear的值也相同
// 所以对于队列来说，当队列只剩下一个空位置时，即视为满队，即，当(rear+1)%N 等于front时，视为满队
typedef struct {
datatype data[N];
int front; // 队头元素的下标
int rear; // 队尾元素的下一个位置的下标（待存入值的位置）
}sequeue;规定：
????????1.front指向队头元素的位置; rear指向队尾元素的下一个位置。
????????2.在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。
????????3.为区别空队和满队，满队元素个数比数组实际能容纳的个数少1。
2.顺序队列的实现
创建队列与释放队列
sequeue * queue_create() {
sequeue *sq;
if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL) {
printf("malloc failed\n");
return NULL;
}
memset(sq->data, 0, sizeof(sq->data));
sq->front = sq->rear = 0; // rear指向待插入位置，front指向当前首位置
return sq;
}sequeue * queue_free(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return NULL;
}
free(sq); // 如果sq中的data用的是指针，那么data需要在创建时申请内存，在此时释放内存
sq = NULL;
return NULL;
}入队与出队
int enqueue(sequeue *sq, datatype x) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
// 当队列只剩下一个空位置时，即视为满队，此时rear指向最后一个空位置，
// 若队尾在内存的末端，则此时(rear+1)%N 等于front，若队尾在内存的中间（循环队列），则rear+1等于front
// 即，当(rear+1)%N 等于front时，视为满队
if ((sq->rear + 1) % N == sq->front) {
printf("sequeue is full\n");
return -1;
}
sq->data[sq->rear] = x;
// 这里对N取余是为了应对这种情况：循环队列，rear指向内存末端
// 同时front指向内存中间，内存的前端还有空余，此时rear+1就超出内存范围了
// 对N取余后，就会利用上内存前端的空间，构成循环队列
sq->rear = (sq->rear + 1) % N;
return 0;
}datatype dequeue(sequeue *sq) {
datatype ret; // 用于返回出队的值
ret = sq->data[sq->front];
// 队首到队尾索引从低到高，所以这里是+1不是-1
sq->front = (sq->front + 1) % N; // 同时，对N取余也是为了适应循环队列
return ret;
}判断空队与满队
int queue_empty(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
return (sq->front == sq->rear ? 1 : 0);
}int queue_full(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
if ((sq->rear + 1) % N == sq->front) {
return 1;
}
else {
return 0;
}
}清空队列
int queue_clear(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
sq->front = sq->rear = 0;
return 0;
}3.链式队列的原理与实现
????????插入操作在队尾进行，删除操作在队头进行，由队头指针和队尾指针控制队列的操作。
typedef int data_t;
typedef struct node {
data_t data;
struct node_t *next;
} listnode, *linklist;
typedef struct {
linklist_t front, rear; // 这里front和rear还是对应位置的索引，不过是以指针的形式，指向节点类型的变量
} linkqueue; 
创建和释放队列
linkqueue * queue_create() {
linkqueue *lq;
if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {
printf("malloc linkqueue failed\n");
return NULL;
}
// 创建时，front和rear都指向同一个节点，即头节点，而不是队头节点
lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
if (lq->front == NULL) {
printf("malloc node failed\n");
return NULL;
}
lq->front->data = 0;
lq->front->next = NULL; //此时rear也指向头节点，而不是头节点中的next，这两句话用lq->rear代替lq->front依然正确
return lq;
}linkqueue * queue_free(linkqueue *lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return NULL;
}
while (lq->front) { // 和清空队列的不同之处在于，头指针也释放
p = lq->front;
lq->front = p->next;
printf("free:%d\n", p->data);
free(p);
}
free(lq); // 和清空队列的不同之处在于，用于描述队列信息的结构体也被释放
lq = NULL;
return NULL;
}入队和出队
int enqueue(linkqueue *lq, datatype x) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
// 先新建一个节点：1.申请内存 2.初始化data和*next
if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
printf("malloc node failed\n");
return -1;
}
p->data = x;
p->next = NULL;
lq->rear->next = p; // 连上
lq->rear = p; // 移动指针
return 0;
}datatype dequeue(linkqueue *lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
// 这里涉及到一个思想，因为链式队列涉及到头节点，和队头可能冲突
// 出队其实出的应该是队头，不应该出头节点，这里出队时，出的是头节点
// 思想就是：出了头节点后，认为队头就是新的头节点，队列中的第二个元素成为新的队头
// 如此一来，就相当于把队头出掉了，真实情况是队头被当作了新的头节点，它的data值也就每人在乎了
p = lq->front;
lq->front = p->next; // 队头成为新的头节点
free(p);
p = NULL;
return (lq->front->data);
}队列是否为空
int queue_empty(linkqueue *lq) {
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
return (lq->front == lq->rear ? 1 : 0); // front和rear指向的节点相同，视为空
}清空队列
// 由于这是链式队列，所以清空队列应该是把头节点外的所有节点都释放
int queue_clear(linkqueue *lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
while (lq->front->next) { // 这里保留了头节点，从队头开始释放
p = lq->front;
lq->front = p->next;
printf("clear free:%d\n", p->data);
free(p);
p = NULL;
}
return 0;
}4.栈和队列的应用
球钟问题
工作原理
问题
?为什么队列中球数为27：小时容器11个 + 5分钟容器11个 + 1分钟容器4个 = 26个，第27个球的作用很特殊，作用是把这26个清空，实现11:59到00:00的转变。
?容器：是栈，有最大容量，故选择顺序栈。
?由于循环队列涉及到取余操作，链式队列用起来相对简单，故选择链式队列。
#include <stdio.h>
#include "linkqueue.h"
#include "sqstack.h"
int check(linkqueue * lq);
int main(int argc, const char *argv[])
{
linkqueue *lq; // 描述链式队列的结构体，里面有front，rear
sqstack *s_hour, *s_five, *s_min; // 定义了3个结构体指针，指向顺序栈对象
int value;
int i, min = 0;
if ((lq = queue_create()) == NULL) { // 创建链式队列
return -1;
}
for (i = 1; i <= 27; i++) { // 将27个球入队
enqueue(lq, i);
}
if ((s_hour = stack_create(11)) == NULL) { // 创建特定容量的顺序栈
return -1;
}
if ((s_five = stack_create(11)) == NULL) {
return -1;
}
if ((s_min = stack_create(4)) == NULL) {
return -1;
}
while (1) {
min++; // 这里记录次数，因为题目问的就是min有多少次
if (!queue_empty(lq)) { // 如果队列还有数
value = dequeue(lq); // 出队一个数给value，利用value将这个数送入栈
if (!stack_full(s_min)) {
stack_push(s_min, value); // 后面代码不再执行
} else { // 此时value中的球还没入栈，else执行，说明min栈满了，这个球会在后面给到5min栈
while (!stack_empty(s_min)) {
enqueue(lq, stack_pop(s_min)); //*将min栈出栈 同时入队到队列，直到栈空为止
}
if (!stack_full(s_five)) { // 这里注意括号，这个if是在else里面的，即此时min栈满了，但又被清空了
stack_push(s_five, value); // min栈满了，清空min栈后，5min栈入栈一元素，后面代码不再执行
} else { // else执行，说明min栈、5min栈都满了
while (!stack_empty(s_five)) { // while循环，开始清理5min栈
enqueue(lq, stack_pop(s_five)); // 出栈后入队
}
if (!stack_full(s_hour)) {
stack_push(s_hour, value); // 之前的5min栈满了，小时栈自然要push一个值，后面不再执行
} else { // 此时的value是第27个球，else执行，说明min栈、5min栈、小时栈都满了
while (!stack_empty(s_hour)) {
enqueue(lq, stack_pop(s_hour)); // 清空小时栈后入队
}
enqueue(lq, value); // 这个第27个球，不会入栈，在外边溜达一圈后直接归队
//上面语句执行完后，27个球全部归队，时间置为00:00
if (check(lq) == 1) {
break; // 这个break跳出的是while(1)循环，其他while循环均不在break外层
}
}
}
}
}
} // while(1)的回括号
printf("total:%d\n", min);
printf("dequeue:");
while (!queue_empty(lq))
printf("%d ", dequeue(lq));
puts("");
return 0;
} // main的回括号
// 检查传入的链式队列，是否为升序，若是返回1，不是返回0
int check(linkqueue * lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
p = lq->front->next; // p指向队头
while (p && p->next) { // 队头和队头后面一个元素均非空时
if (p->data < p->next->data) {
p = p->next;
} else {
return 0;
}
}
return 1;
}