1 稀疏数组
1.1 实际需求
二维数组的很多值是默认值 0 ，记录了很多没有意义的数据，可以将其转为稀疏数组进行存储。



1.2 稀疏数组应用实例


原始数组转换成稀疏数组（代码）

//测试代码
class Demo{
	public static void main(String[] args){
		//创建一个11*11的二维数组
		// 0: 表示没有棋子， 1 表示 黑子 2 表蓝子
		int[][] array = new int[11][11];
		array[1][2] = 1;//黑子位置
		array[2][3] = 2;//蓝子位置
		
		System.out.println("打印原始数组：");
		PrintArray.printArray(array);
		
		//调用转换成稀疏数组的方法
		int[][] arr = SparseArray.sparseArray(array);
		//打印稀疏数组
		System.out.println("打印稀疏数组：");
		PrintArray.printArray(arr);
		
		//调用还原成原始数组的方法
		int[][] yArr = FanSparseArray.fanSparseArray(arr);
		//打印稀疏数组
		System.out.println("打印原始数组：");
		PrintArray.printArray(yArr);
	}
}

class SparseArray{
	//将原始数组转换成稀疏数组
	public static int[][] sparseArray(int[][] arr){
		//1.先遍历原始数组，得到有效数据个数
		int sum = 0;
		for(int i = 0; i < arr.length; i++){
			for(int j = 0; j < arr[i].length; j++){
				if(arr[i][j] != 0){
					sum++;
				}
			}
		}
		
		//2.根据有效数据个数创建稀疏数组
		int[][] sparseArr = new int[sum+1][3];
		
		//3.将原始数组中的有效数据存入稀疏数组
		//稀疏数组第一行存放原始数组行数，列数，有效数据个数
		sparseArr[0][0] = arr.length;
		sparseArr[0][1] = arr[0].length;
		sparseArr[0][2] = sum;
		//稀疏数组从第二行开始存放：有效数据的行数，列数，数值
		int count = 0;//定义有效数据的个数
		for(int i = 0; i < arr.length; i++){
			for(int j = 0; j < arr[i].length; j++){
				if(arr[i][j] != 0){
					count++;
					sparseArr[count][0] = i;
					sparseArr[count][1] = j;
					sparseArr[count][2] = arr[i][j];
				}
			}
		}
		return sparseArr;
	}
}

class FanSparseArray{
	//将稀疏数组还原成原始数组
	public static int[][] fanSparseArray(int[][] arr){
	//1.先读取稀疏数组的第一行，创建原始数组
	int[][] yArray = new int[arr[0][0]][arr[0][1]];
	
	//2.读取稀疏数组后n行数据，赋值给原始二维数组
	for(int i =1; i <= arr[0][2]; i++){
			int row = arr[i][0];
			int col = arr[i][1];
			yArray[row][col] = arr[i][2];
		}
	return yArray;
	}
}

//打印二维数组(循环嵌套)
class PrintArray{
	public static void printArray(int[][] arr){
		for(int i = 0; i < arr.length; i++){
			for(int j = 0; j < arr[i].length; j++){
				System.out.print(arr[i][j]+"\t");
			}

			System.out.println();
		}
	}
}


结果截图


2 队列（Queue）




2.1 概述

队列是一种特殊的线性表，可以用数组或者链表实现。尾部添加，头部删除，FIFO。



2.2 数组模拟队列

队列容量：maxSize
队列判空：front == rear
队列判满：rear == （maxsize - 1）
队列元素个数：rear - front
元素入队列条件：队列没满
元素出队列条件：队列没空

代码实现
package com.tony.queue;

public class ArrayQueue {
	private int maxSize;// 表示数组的最大容量
	private int front; // 表示队列头
	private int rear; // 表示队列尾
	private int[] arr; // 该数组用于存放数据，模拟队列

	// 队列的构造函数
	public ArrayQueue(int maxSize) {
		this.maxSize = maxSize;
		arr = new int[maxSize];
		front = -1;
		rear = -1;
	}
	
	// 判断队列是否满
	public boolean isFull() {
		return rear == maxSize - 1;
	}

	// 判断队列是否为空
	public boolean isEmpty() {
		return rear == front;
	}
	
	// 添加数据到队列
	public void addQueue(int n) {
		// 判断队列是否满
		if (isFull()) {
			System.out.println("队列满，不能加入数据~");
			return;
		}
		rear++; // 让rear后移
		arr[rear] = n;
	}
	
	// 获取队列的数据, 出队列
	public int getQueue(){
		//判断队列是否为空
		if(isEmpty()){
			//通过抛出异常
			throw new RuntimeException("队列空 ，不能取数据");
		}
		front++;
		return arr[front];
	}
	
	// 显示队列的所有数据
	public void showQueue(){
		//判空
		if (isEmpty()) {
			System.out.println("队列空的，没有数据~~");
			return;
		}
		//遍历
		for(int i = front + 1; i <= rear; i++){
			System.out.println("arr["+i+"]="+arr[i]);
		}
	}
	
	// 显示队列的头数据， 注意不是取出数据
	public int headQueue(){
		//判空
		if(isEmpty()){
			System.out.println("队列为空，没有数据");
		}
		return arr[front + 1];
	}
}


import java.util.Scanner;
class ArrayQueueDemo{
	public static void main(String[] args){
		//创建一个队列
		ArrayQueue queue = new ArrayQueue(3);
		String key = "";
		//键盘输入
		Scanner sc = new Scanner(System.in);
		//循环标志
		boolean loop = true;
		
		while(loop){
			System.out.println("show: 显示队列");
			System.out.println("exit: 退出程序");
			System.out.println("add: 添加数据到队列");
			System.out.println("get: 从队列取出数据");
			System.out.println("head: 查看队列头的数据");
			key = sc.nextLine();	//接收一个字符串
			
			switch(key){
				case"show":
					queue.showQueue();
					break;
				case"add":
					System.out.println("请输入一个数:");
					int value = sc.nextInt();
					queue.addQueue(value);
					break;
				case"get":
					try{
						int res = queue.getQueue();
						System.out.println("取出的数据是"+res);
					}catch(Exception e){
						System.out.println(e.getMessage());
					}
					break;
				case "head":
					try{
						int res = queue.headQueue();
						System.out.println("队列头的数据是"+res);
					}catch(Exception e){
						System.out.println(e.getMessage());
					}
					break;
				case "exit":
					sc.close();
					loop = false;
					break;
				default:
					break;
			}
		}
		System.out.println("程序退出~~");
	}
}



目前数组只能使用一次，没有达到复用的效果，造成了空间的浪费。

2.3 数组模拟环形队列

front指向队列头的位置，即arr[front]是队列的第一个元素，front初始值为0
rear指向队列尾的后一个位置。rear初始值为0
队列满的条件：(rear + 1)%maxSize == front
队列空的条件：rear == front
队列中有效数据个数：(rear + maxSize - front)%maxSize
队列容量：maxSize - 1


队列判满：

　　为何要在 rear 之后，front 之前空出一个元素的空间？因为如果不空出一个元素，队列判空条件为：front == rear ，队列判满的条件也是：front == rear ，有歧义！

　　队列容量：因为空出了一个元素，所以队列容量就变成了 (maxSize - 1)

　　当空出一个元素的空间，如何判满？当还剩一个元素时，队列就已经满了，所以判断条件为 (rear + 1) % maxSize == front
队列元数个数：

　　计算公式：(rear + maxSize - front) % maxSize ，这样来思考：

　　当 rear 比 front 大时，即 (rear -front) > 0 ，这时还没有形成环形结构，(rear -front) 即是队列元素个数

　　当 rear 比 front 小时，即 (rear -front) < 0 ，这时已经形成了环形结构，(rear -front) 表示数组还差多少个元素存满（负数），(rear + maxSize - front) 即是队列元素个数

　　综上：(rear + maxSize - front) % maxSize
队列入队：

　　首先，队列不满才能入队

　　由于 rear 指向队列尾部元素的后一个元素，所以直接设置即可： arr[rear] = value

　　接下来，rear 应该向后移动一个位置：rear = (rear + 1) % maxSize

　　取模是为了防止数组越界，让指针从新回到数组第一个元素
队列出队：

　　首先，队列不空才能出队

　　由于 front 直接指向队列头部元素，所以直接返回该元素即可：int value = arr[front ]

　　接下来，front 应该向后移动一个位置：front = (front + 1) % maxSize

　　取模是为了防止数组越界，让指针从新回到数组第一个元素

class CircleArray{
	private int maxSize; // 表示数组的最大容量
	// front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
	// front 的初始值 = 0
	private int front;
	// rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
	// rear 的初始值 = 0
	private int rear; // 队列尾
	private int[] arr; // 该数据用于存放数据, 模拟队列
	
	//构造方法
	public CircleArray(int maxSize) {
		this.maxSize = maxSize;
		arr = new int[maxSize];
	}
	
	// 判断队列是否满
	public boolean isFull(){
		return (rear + 1)%maxSize == front;
	}
	
	// 判断队列是否为空
	public boolean isEmpty(){
		return rear == front;
	}
	
	// 添加数据到队列
	public void addQueue(int n) {
		// 判断队列是否满
		if (isFull()) {
			System.out.println("队列满，不能加入数据~");
			return;
		}
		// 直接将数据加入
		arr[rear] = n;
		// 将 rear 后移, 这里必须考虑取模
		rear = (rear + 1) % maxSize;
	}
	
	// 获取队列的数据, 出队列
	public int getQueue() {
		// 判断队列是否空
		if (isEmpty()) {
			// 通过抛出异常
			throw new RuntimeException("队列空，不能取数据");
		}
		// 这里需要分析出 front是指向队列的第一个元素
		// 1. 先把 front 对应的值保留到一个临时变量
		// 2. 将 front 后移, 考虑取模
		// 3. 将临时保存的变量返回
		int temp = arr[front];
		front = (front + 1) % maxSize;
		return temp;
	}
	
	// 显示队列的所有数据
	public void showQueue(){
		// 遍历
		if (isEmpty()){
			System.out.println("队列空的，没有数据~~");
			return;
		}
		// 思路：从front开始遍历，front + size()次
		for (int i = front; i < front + size(); i++) {
			System.out.println("arr["+i%maxSize+"]="+arr[i % maxSize]);
		}
	}
	
	// 求出当前队列有效数据的个数
	public int size(){
		return (rear + maxSize - front) % maxSize;
	}
	
	// 显示队列的头数据， 注意不是取出数据
	public int headQueue() {
		// 判断
		if (isEmpty()) {
			throw new RuntimeException("队列空的，没有数据~~");
		}
		return arr[front];
	}
}

import java.util.Scanner;
public class CircleArrayQueueDemo {
	public static void main(String[] args) {
		//测试一下
		System.out.println("测试数组模拟环形队列的案例~~~");
		
		// 创建一个环形队列
		CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3
		String key = ""; // 接收用户输入
		Scanner scanner = new Scanner(System.in);//
		boolean loop = true;
		// 输出一个菜单
		while (loop) {
			System.out.println("show: 显示队列");
			System.out.println("exit: 退出程序");
			System.out.println("add: 添加数据到队列");
			System.out.println("get: 从队列取出数据");
			System.out.println("head: 查看队列头的数据");
			key = scanner.nextLine();		// 接收一个字符
			switch (key) {
			case "show":
				queue.showQueue();
				break;
			case "add":
				System.out.println("输出一个数");
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case "get": // 取出数据
				try {
					int res = queue.getQueue();
					System.out.printf("取出的数据是%d\n", res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case "head": // 查看队列头的数据
				try {
					int res = queue.headQueue();
					System.out.printf("队列头的数据是%d\n", res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case "exit": // 退出
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println("程序退出~~");
	}
}

参考：数据结构与算法分析 --C语言描述

队列的实现有很多种，但是只要我们保证函数调用的效果相同那么怎么实现都无所谓。
front和rear指针指向的问题


队列有两个指针，头指针front和尾指针rear。
使用数组实现队列的时候

可以让front指向队列的第一个元素，rear指向队列的最后一个元素的下一个位置；
也可以让front指向第一个位置的前一个位置，rear指向最后一个位置；
也可以让front指向第一个位置，rear指向最后一个位置

使用前两种方法可以使用front == rear确定队列是否为空，第三种可以使用rear + 1 = front 的来确定队列为空
使用循环队列
从上面的图可以看到，出队时front向后移动，那么前面空出的数组空间就无法得到利用，所以我们要使rear指针可以回到数组的开始位置。


如何判断队列的空，满
我使用的front和rear指向是第三种。那么当队列为空时有front == （rear+1）%Maxsize，队列为满时这个条件同时成立，怎么判断队列的空，满呢？

有三种方法：

添加变量size标识队列的大小
使用tag标签，当入队时tag设置为1，出队时设为0，所以队满时tag总是为1
在数组中预留一个空间，如果使用front指向第一个位置，rear指向最后一个位置，那么队空：front == （rear+1）%Maxsize， 队满时front  ==（rear+2）%Maxsize。

针对第三种情况，当front指向第一个位置，rear指向最后一个位置的下一个位置时，盗用网上的一张图来理解：


代码
本次使用循环队列，front指向第一个位置，rear指向最后一个位置，通过size来判断队列的空满。
queue.h
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

typedef int ElementType;

struct QueueRecord;
typedef struct QueueRecord *Queue;

int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);		//销毁队列
void MakeEmpty(Queue Q);	//使队列为空
void Enqueue(Queue Q,ElementType X);
void Dequeue(Queue Q);
ElementType Front(Queue Q);		//返回队列的队首元素
ElementType FrontAndDequeue(Queue Q);	//返回队首元素并出队

#endif // QUEUE_H_INCLUDED


queue.c
#include"..\fatal.h"
#include"queue.h"
#include<stdio.h>
#include<stdlib.h>

#define MinQueueSize (5)


struct QueueRecord{
    int Capacity;		//容量
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
};

int IsEmpty(Queue Q){
    return Q->Size == 0;
}

int IsFull(Queue Q){
    return Q->Size == Q->Capacity;
}

Queue CreateQueue(int MaxElements){
    Queue Q;

    if(MaxElements < MinQueueSize)
        Error("Queue size is too small");

    Q = malloc(sizeof(struct QueueRecord));
    if(Q == NULL)
        FatalError("Out of space!!");

    Q->Array = malloc(sizeof(ElementType) * MaxElements);
    if(Q->Array == NULL)
        FatalError("Out of space!!");

    Q->Capacity = MaxElements;
    MakeEmpty(Q);

    return Q;
}

void MakeEmpty(Queue Q){
    Q->Size = 0;
    Q->Front = 1;
    Q->Rear = 0;
}

void DisposeQueue(Queue Q){
    if(Q != NULL){
        free(Q->Array);
        free(Q);
    }
}

static int Succ(int value, Queue Q){
    if( ++value == Q->Capacity)
        value = 0;
    return value;
}

void Enqueue(Queue Q, ElementType X){
    if(IsFull(Q))
        Error("Full queue");
    else{
        Q->Size++;
        Q->Rear = Succ(Q->Rear, Q);
        Q->Array[Q->Rear] = X;
    }
}

ElementType Front(Queue Q){
    if(IsEmpty(Q))
        Error("Empty queue");
    else
        return Q->Array[Q->Front];
}

void Dequeue(Queue Q){
    if(IsEmpty(Q))
        Error("Empty queue");
    else{
        Q->Front = Succ(Q->Front, Q);
        Q->Size --;
    }
}

ElementType FrontAndDequeue(Queue Q){
    ElementType X;
    if(IsEmpty(Q))
        Error("Empty queue");
    else{
        X = Q->Array[Q->Front];
        Q->Front = Succ(Q->Front, Q);
        Q->Size --;
    }
    return X;
}

int main(){

    Queue Q;

    Q = CreateQueue(10);
    Enqueue(Q, 1);
    Enqueue(Q, 2);
    Dequeue(Q);
    printf("%d\n",Front(Q));
    printf("%d\n",FrontAndDequeue(Q));
    printf("%d",IsEmpty(Q));
    DisposeQueue(Q);

    return 0;

}

队列是一种先进先出的思想。（First In First Out)

关于队列的定义就不叙述了，百度比我讲的详尽的多，在这里说一下用数组实现队列的思想，并附上代码。

我们身边的与队列相关实例很多，火车站排队买票或是买饭是排队，都是队列。因此我们很容易想到，队列是有一个头一个尾的，新来的总是在尾，最先来的总是最先买票或是吃饭，当然，像插队一类的我们不做考虑，相信我们都不会喜欢这些的。

队列的成员的进出我们已经知道了，总是队头出、队尾进，观看我们身边的实例，我们可以看到，排队时，卖饭的阿姨或是卖票的售票员都是不会移动的，移动的都是成员，那么在代码中，我们也需要这样做吗？每出队一位就让剩下的全体成员集体前移一位，未免太累了。因此我们可以很自然的想到，让卖饭阿姨或是售票员来移动，成员们保持不动，已经买到饭或是买到票的成员就直接离开。可是我们又有一个疑问，在空间有限的情况下（即队列长度有限），当卖饭阿姨移动到队尾给最后一个成员打完饭，队列是不是就没有位置了呢？联系实际我们可以很自然的想到，前面的成员离开了，那么前面的位置就空出来了啊，再有成员进入队列就可以去前面的位置啊，只需要让阿姨在回到最前面重新打饭就可以了啊。这就是队列的思想。

将上述思想化为代码就简单多了。

首先，在有五个位置的队列中，当没有成员进入队列时，队头和队尾显然都在第一个位置。

然后，当有成员进入队列时，阿姨还没有开始打饭，队头显然还是在第一个位置，而第一个进入队列后，下一个成员进入队列应该到哪个位置呢？显然是第二个位置，因此，当队列有一个成员时，队尾在第一个成员的后面，也就是说，队尾总是在最后一个成员的后面。

接着，很快队列就满了，五个位置都有了成员，显然不能有成员再进队列了，这时阿姨开始打饭，给第一个成员打完饭，阿姨就走向第二个成员，也就是说，当第一个成员出去后，队头就到了第二个成员，因此，队头总是在队列的第一个成员。

当阿姨给三个人打完饭后，只有第四第五个位置有人了，又有新的成员想进队打饭，这时他们就会自然而然地走向前面的位置，因为他们知道阿姨打完饭后就会回到第一个位置给他们打饭，这是队尾依然是最后一个进队的成员的后面，只不过这个成员的位置编号在队头前面。

同理，阿姨在给第五个位置的成员打完饭就会回到第一个位置给同学打饭。

队列的思想就是这些了，在用数组实现时，有以下几个地方需要注意：

1、队列的长度就是数组的长度

2、没有成员时，队头队尾都指向第一个位置，即下标为0

3、队头始终指向队列中最先进队的成员，队尾始终指向队列中最后进队的成员的后面下一个位置

3、当队头与队尾的下标相同时，队列为空，因此队尾在指向第四个位置即下标为3时，就应该算队满，否则当队头下标为0时，最后一个位置即第五个位置也有成员，此时队尾下标为0，按照上面的思想应该算队列为空，与实际不符。因此队列的实际容量始终为数组容量减一。

4、按照上面的思想，队头和队尾下标表示应该为（当前下标+1）%数组容量，在第一圈为0，1，2，3，4，第二圈时继续自加明显不合适，因为下标因该为0，因此在自加后对数组容量取余

代码如下：

#include<iostream>
using namespace std;
#define MAXSIZE 10
class queue
{
public:
        queue();
        bool IsFull();
        bool IsEmpty();
        bool EnQueue(int);
        bool DeQueue(int&);
private:
        int buf[MAXSIZE];
        int rear;
        int front;
};
queue::queue()
{
        this->rear=0;
        this->front=0;
}
bool queue::IsEmpty()
{
        if(this->rear==this->front)
                return true;
        else
                return false;
}
bool queue::IsFull()
{
        if((this->rear+1)%MAXSIZE==this->front)
                return true;
        else
                return false;
}
bool queue::EnQueue(int data)
{
        if(IsFull())
                return false;
        this->buf[this->rear]=data;
        this->rear=(this->rear+1)%MAXSIZE;
        return true;
}
bool queue::DeQueue(int& data)
{
        if(IsEmpty())
                return false;
        data=this->buf[this->front];
        this->front=(this->front+1)%MAXSIZE;
}
int main()
{
        queue q;
        int i=0;
        while(i<20)
        {
                if(q.EnQueue(i))
                        cout<<"success "<<i<<endl;
                else
                        cout<<"fail "<<i<<endl;
                i++;
        }
        while(q.DeQueue(i))
                cout<<i<<" ";
        cout<<endl;
        return 0;
}


 

理论知识
由于顺序存储的队列会产生“假溢出的情况”，我们可以将队列的存储结构臆想为一个闭合的环状结构，这便是我们所说的循环队列，如下图所示。

循环队列的逻辑结构

但是循环队列中，判断队空和堆满的条件都是Q.rear = Q.front,这给我们的编程实现带来了很多麻烦，这样我们会有三种处理方法，

1.牺牲一个存储单元，入队的时候将队头指针在队尾指针的下一位置最为队列满的条件

这是判断队空的条件仍然是：Q.rear = Q.front

但是判断队满的条件变为：(Q.rear+1)%MAXSIZE = Q.front

队列中元素的个数为:(Q.rear-Q.front+MAXSIZE)%MAXSIZE

2.在结构体的定义中增加表示元素个数的成员

队空：Q.size = 0

队满：Q.size = MAXSIZE

队列元素个数：Q.size

3.第一种情况牺牲的存储空间利用起来，当flag = 0时，因为删除发生了Q.rear = Q.front 则表示队空，当flag = 1时，因为增加导致了Q.rear = Q.front 则表示队满
以下使用第一种方法进行代码实现
存储结构
typedef struct {
	int data[MAXSIZE];
	int front,rear;
}Quene;

初始化
//初始化
void initQuene(Quene &Q){
	Q.rear = Q.front = 0;
}

判空
bool isEmpty(Quene &Q){
	if((Q.rear+1)%MAXSIZE == Q.front){
		cout<<"队列已满"<<endl;
		return true;
	}
	return false;
}

入队
//入队
bool push(Quene &Q,int e){
	if(!isEmpty(Q)){
		Q.data[Q.rear] = e;
		Q.rear = (Q.rear+1) % MAXSIZE;
		return true; 
	}
	return false;
}

出队
//出队
bool pop(Quene &Q){
	if(Q.rear == Q.front){
		return false;
	}else{
		Q.data[Q.front] = -1;
		Q.front = (Q.front+1)%MAXSIZE;
		return true;
	}
}

整合测试
#include<iostream>
using namespace std;
#define MAXSIZE 4
typedef struct {
	int data[MAXSIZE];
	int front,rear;
}Quene;
//初始化
void initQuene(Quene &Q){
	Q.rear = Q.front = 0;
}
//判空 
bool isEmpty(Quene &Q){
	if((Q.rear+1)%MAXSIZE == Q.front){
		cout<<"队列已满"<<endl;
		return true;
	}
	return false;
}
//入队
bool push(Quene &Q,int e){
	if(!isEmpty(Q)){
		Q.data[Q.rear] = e;
		Q.rear = (Q.rear+1) % MAXSIZE;
		return true; 
	}
	return false;
}
//出队
bool pop(Quene &Q){
	if(Q.rear == Q.front){
		return false;
	}else{
		Q.data[Q.front] = -1;
		Q.front = (Q.front+1)%MAXSIZE;
		return true;
	}
}
int main()
{
	Quene Q;
	initQuene(Q);
	push(Q,1);
	cout << Q.data[Q.rear-1] << endl;
	push(Q,2);
	cout << Q.data[Q.rear-1] << endl;
	push(Q,3);
	cout << Q.data[Q.rear-1] << endl;
	push(Q,4);
	cout << Q.data[Q.front] << endl;
	pop(Q);
	cout << Q.data[Q.front] << endl;
	pop(Q);
	cout << Q.data[Q.front] << endl;
	return 0;
 }