[数据结构与算法]【数据结构笔记】数据结构基础—队列

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;
}