队列

队列（queue），是一种特殊的线性表，是运算受到限制的一种线性表，只允许在表的 一端进行插入，而在另一端进行删除元素的线性表。操作方式 先进先出

队尾： 队列进口 队头： 队列出口 进队： 插入队列 出队： 删除队列

队列的基本操作类型

初始化、入队、出队、清空队列、队列是否为空、获取队头元素、获取所有元素···等

例子：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

class MyQueue{
    //队列
    private List queue = null;
    //头索引
    private int Head;
    private final int MAX = 100;
    
    //初始化（1）
    public MyQueue(){
        queue = new ArrayList();
        this.Head = 0;
    }
    
    //入队（2）
    public boolean AddQueue(Object data){
        if (queue == null || queue.size() >= MAX){
            return false;
        }
        queue.add(data);
        return true;
    }
    
    //出队（3）
    public boolean DeQueue(){
        if (queue == null || queue.size() <= 0){
            return false;
        }
        //出队后置空
        queue.set(this.Head , null);
        this.Head++;
        return true;
    }
    
    //清空队列（4）
    public boolean DestoryQueue(){
        for (int i = 0; i < queue.size(); i++) {
            queue.remove(queue.get(this.Head));
        }
        System.gc();
        return true;
    }
    
    //队列是否为空（5）
    public boolean isEmpty(){
        return this.Head >= queue.size();
    }
    
    //获取队头元素（6）
    public Object GetHead(){
        return queue.get(this.Head);
    }
    
    //获取所有元素（7）
    public Object[] arrayQueue(){
        Object[] array = new Object[queue.size()];
        Iterator it = queue.iterator();
        int n = 0;
        while (it.hasNext()){
            Object tmp = it.next();
            if (tmp != null){
                array[n] = tmp;
                n++; }
        }
        //防空值
        Object[] array2 = new Object[n];
        for (int i = 0; i < n ; i++) {
            array2[i] = array[i];
        }
        return array2;
    }
    
}

public class Demo {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        
        //是否为空队
        System.out.println("队列是否为空："+queue.isEmpty());
        
        //入队
        System.out.println("\n=========入队数据···\n");
        queue.AddQueue(1);
        queue.AddQueue("Sanscan12");
        queue.AddQueue(22.3);
        queue.AddQueue(new Object());
        queue.AddQueue(555);
        
        //是否为空队
        System.out.println("队列是否为空："+queue.isEmpty());
        
        //获取队列
        System.out.println("\n=========遍历队列");
        for (Object tmp : queue.arrayQueue()){
            System.out.println(tmp);
        }
        
        //出队操作 X2
        System.out.println("\n=========出队操作 *2\n");
        queue.DeQueue();
        queue.DeQueue();
    
        //获取队列
        System.out.println("\n=========遍历队列");
        for (Object tmp : queue.arrayQueue()){
            System.out.println(tmp);
        }
        
        //获取队头元素值
        System.out.println("\n=========获取队头元素值");
        System.out.println(queue.GetHead());
    
        //清空队列
        System.out.println("\n=========清空队列\n");
        queue.DestoryQueue();
    
        //是否为空队
        System.out.println("队列是否为空："+queue.isEmpty());
        
    }
}


/**

队列是否为空：true

=========入队数据···

队列是否为空：false

=========遍历队列
1
Sanscan12
22.3
java.lang.Object@7cd84586
555

=========出队操作 *2


=========遍历队列
22.3
java.lang.Object@7cd84586
555

=========获取队头元素值
22.3

=========清空队列

队列是否为空：true

*/

循环队列

循环队列是将队 列头 和 尾 的位置连接起来形成空间循环，一旦队列满了，就不能插入元素，即使在队列前面仍有空间。重复利用空间

例子：

interface Method {
    //入队
    boolean Add(Object data);
    //出队
    boolean DeQueue();
    //是否为空
    boolean isEmpty();
    //获取头
    Object GetHeadvalue();
    int GetHead();
    //获取尾
    Object GetTailvalue();
    int GetTail();
    //总长
    int GetSize();
    //返回所有元素
    Object[] ArrayQueue();
}

class MyCircularQueue implements Method{
    private Object[] queue;
    private static int head , tail ,size;
    
    public MyCircularQueue(int max){
        queue = new Object[max+1];
        head = 0;
        tail = 0;
        size = 0;
    }
    
    //入队
    @Override
    public boolean Add(Object data){
        
        if ((tail+1)%queue.length == head){
            return false;
        }
        
        queue[tail] = data ;
        size++;
        tail = (tail + 1) % queue.length;
        
        return true;
    }
    
    //出队
    @Override
    public boolean DeQueue(){
        if (isEmpty()){
            return false;
        }
        
        queue[head] = null;
        head = (head + 1) % queue.length;
        size--;
        
        return true;
    }
    
    //判断是否为空
    @Override
    public boolean isEmpty(){
        if (head == tail){
            return true;
        }
        return false;
    }
    
    //判断是否为满
    public boolean isFull(){
        if(queue.length-1 == size){
            return true;
        }
        return false;
    }
    
    //获取头元素 。队列为空返回null
    @Override
    public Object GetHeadvalue(){
        return queue[head];
    }
    
    @Override
    public int GetHead() {
        return head;
    }
    
    //获取尾元素 。队列为空返回null
    @Override
    public Object GetTailvalue(){
        return queue[tail-1];
    }
    
    @Override
    public int GetTail() {
        return tail;
    }
    
    @Override
    public int GetSize(){
        return size;
    }
    
    @Override
    public Object[] ArrayQueue() {
        return queue;
    }
    
}

public class Demo2 {
    public static void main(String[] args) {
        MyCircularQueue queue = new MyCircularQueue(5);
    
        System.out.println("是否空？"+queue.isEmpty());
        
        System.out.println("入队 *5：");
        System.out.println(queue.Add(123));
        System.out.println(queue.Add(3.14));
        System.out.println(queue.Add(new Object()));
        System.out.println(queue.Add("Sanscan12"));
        System.out.println(queue.Add("2223333"));
        
        
        System.out.println("===================");
        System.out.println("遍历：");
        for(Object tmp : queue.ArrayQueue()){
            System.out.println(tmp);
        }
        System.out.println();
        System.out.println("队列是否空？"+queue.isEmpty());
        System.out.println("队列是否满？"+queue.isFull());
        System.out.println("队列总长："+queue.GetSize());
        System.out.println("头索引："+queue.GetHead()+"\t值："+queue.GetHeadvalue());
        System.out.println("尾索引："+queue.GetTail()+"\t值："+queue.GetTailvalue());
        
        System.out.println("===================");
    
        System.out.println("\n出队 *3\n");
        System.out.println(queue.DeQueue());
        System.out.println(queue.DeQueue());
        System.out.println(queue.DeQueue());
    
        System.out.println("\n入队 *5\n");
        System.out.println(queue.Add(1111));
    
        System.out.println(queue.Add(2222));
        System.out.println(queue.Add(3333));
        System.out.println(queue.Add(4444));
        System.out.println(queue.Add(5555));
    
        System.out.println("===================");
        System.out.println("遍历：");
        for(Object tmp : queue.ArrayQueue()){
            System.out.println(tmp);
        }
        System.out.println();
        System.out.println("队列是否空？"+queue.isEmpty());
        System.out.println("队列是否满？"+queue.isFull());
        System.out.println("队列总长："+queue.GetSize());
        System.out.println("头索引："+queue.GetHead()+"\t值："+queue.GetHeadvalue());
        System.out.println("尾索引："+queue.GetTail()+"\t值："+queue.GetTailvalue());
    
        System.out.println("===================");
        
    }
}


/**

是否空？true
入队 *5：
true
true
true
true
true
===================
遍历：
123
3.14
java.lang.Object@30dae81
Sanscan12
2223333
null

队列是否空？false
队列是否满？true
队列总长：5
头索引：0	值：123
尾索引：5	值：2223333
===================

出队 *3

true
true
true

入队 *5

true
true
true
false
false
===================
遍历：
2222
3333
null
Sanscan12
2223333
1111

队列是否空？false
队列是否满？true
队列总长：5
头索引：3	值：Sanscan12
尾索引：2	值：3333
===================

*/