数据结构队列
首先明确一下队列的概念.
队列是一种有序列表,使用数组的结构来存储队列的数据.
队列是一种先进先出的算法.由前端加入,由后端输出.
如下图:
第一个图 第二个图 第三个图
这就是队列的形状.
他的本体是一个空空的数组(Queue)加上两个指在同一个位置的指针(rear,front).
这个数组有长度的限制(因为是java算法,所以数组长度有限制,必须在声明时就写出他的大小.)
于是我们看到了上面的情况,如果要加入元素就移动后面的指针(rear),如果要获取(退出)元素就把前面的指针移动(front).
于是我们可以产生这样的一个思路.
- front永远指向队列中第一个值
- rear永远指向队列中最后一个值
- 当rear==front的时候队列为空(理解不了就看一眼第一个图)
- 移动front是从队中删除元素
- 移动rear是从队中添加元素
由此我们可以写出代码:
第一部分是创建一个队列.(与稀疏数组一样,第一步都是创建这个数据结构)
class ArrayQueue{
private int maxSize;//表示数组的最大容量
private int front;//队列头
private int rear;//队列尾
private int arr[];//该数据用于存放数据，模拟队列
}
如上几个就是构建队列所需要的资源
但是这个资源有一个值必须由外部来给定,那就是maxSize.
所以构造函数如下:
//创建队列的构造器
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr=new int[maxSize];
front=-1;//只想对队列头部，分析出front是指向队里的头的*前一个位置*
rear=-1;//指向队列尾的数据（即就是队列最后的一个数据）
}
由此我们就可以构建出一个队列了
但是一个队列并没有什么用,我们还要操作这个家伙.
如果我们要构造加入队列的功能,思路一般是构造一个循环,而这个循环的停止条件则是应该是队列满
就必须要有判断队列是否满的功能.
ISFULL
//看图就知道,当rear指到最后一个的时候合格就无法继续添加了
public boolean isFull() {
return rear==maxSize-1;
}
addQueue:加入队列功能.根据上面说过的内容,rear指针向后移动就是像队列中加入元素.
如果满了,就必须阻止这个加入步骤.
public void addQueue(int a){
//判断队列不为空
if(isFull()){
System.out.println("队列满，不能加入数据");
return;
}
//加入数据
rear++;//让rear后移
arr[rear]=a;//赋值
}
构建完了增加模块,我们就要构造获取模块了.
和增加模块一样,获取模块也准备由两个函数构成.
我们也要担心一下这个是不是空的,要组织获取不存在得数值.
我们知道,当rear==front的时候,这个队列就回到了最初的状态,里面为空.
ISEMPTY
public boolean isEmpty(){
return rear==front;
}
由此我们就只要构建一个获取模块函数可以了,用ISEMPTY来阻止取出不存在的值
public int getQueue(){
if (isEmpty()){
System.out.println("栈空了！");
// return -1;这个不行，因为这样的话，只能返回-1
throw new RuntimeException("队列空。");
}
front++;
return arr[front];
}
这就是队列的主要功能了.
但是要想观察整个队列中有的元素,总不能挨个退出来之后再挨个加上去吧!
那就必须重写一个函数了.
正好,因为队列是数组,所以我们只要遍历数组就能得到其中全部的数据,当然这个只是为了让你搞清楚这个队列的结构以及其中的内容,看一下即可.因为它会将队列用过的所有结点都打印出来.
//显示队列的所有数据
public void showQueue(){
if (isEmpty()){
System.out.println("队列是空的。");
}
for (int i = 0; i <arr.length ; i++) {
System.out.printf("arr[%d]=%d
",i,arr[i]); //这个要学习一下。
//标准化输出解决输出的值是空值的问题。
}
}
还有一个办法,就是发现头节点.
//显示队列头数据，注意不是取出数据
public int headQueue(){
if (isEmpty()){
System.out.println("队列空的，没有数据");
throw new RuntimeException("队列是空的");
}
return arr[front+1];//因为队列头front永远指的是队列中的第一个数的前面一个
}
下面是全部得代码
package queue;
//import jdk.nashorn.internal.parser.Scanner;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//测试一下
//创建一个队列
ArrayQueue arrayQueue = new ArrayQueue(3);
char key=' ';//接受用户的输入
Scanner scanner = new Scanner(System.in);
boolean loop=true;
//输出一个菜单
while(loop){
System.out.println("s:显示队列");
System.out.println("e:退出程序");
System.out.println("a：添加数据到队列");
System.out.println("g：从队列取出数据");
System.out.println("h：查看队列头的数据");
// System.out.println("s:显示队列");
key=scanner.next().charAt(0);
switch (key){
case 's':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value=scanner.nextInt();
arrayQueue.addQueue(value);
arrayQueue.showQueue();
break;
case 'g'://取出数据
try {
int res=arrayQueue.getQueue();
System.out.printf("取出的数据是%d
,",res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h'://查看队列头的数据
try {
System.out.println( arrayQueue.headQueue());
}catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e'://退出
scanner.close();
loop=false;
break;
default:
break;
}
}
System.out.println("程序退出~~~时");
}
}
//编写一个叫做ArrayQueue的类
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;//只想对队列头部，分析出front是指向队里的头的*前一个位置*
rear=-1;//指向队列尾的数据（即就是队列最后的一个数据）
}
//判断队列是否满
public boolean isFull() {
return rear==maxSize-1;
}
//判断队列是否为空
public boolean isEmpty(){
return rear==front;
}
//添加数据到队列
public void addQueue(int a){
//判断队列不为空
if(isFull()){
System.out.println("队列满，不能加入数据");
return;
}
//加入数据
rear++;//让rear后移
arr[rear]=a;//赋值
}
//获取队列的值
public int getQueue(){
if (isEmpty()){
System.out.println("栈空了！");
// return -1;这个不行，因为这样的话，只能返回-1
throw new RuntimeException("队列空。");
}
front++;
return arr[front];
}
//显示队列的所有数据
public void showQueue(){
if (isEmpty()){
System.out.println("队列是空的。");
}
for (int i = 0; i <arr.length ; i++) {
System.out.printf("arr[%d]=%d
",i,arr[i]); //这个要学习一下。
//标准化输出解决输出的值是空值的问题。
}
}
//显示队列头数据，注意不是取出数据
public int headQueue(){
if (isEmpty()){
System.out.println("队列空的，没有数据");
throw new RuntimeException("队列是空的");
}
return arr[front+1];//因为队列头front永远指的是队列中的第一个数
}
}