学会一种数据结构二：队列的数组实现和链表实现

àì夳堔傛蜴生んèń 2022-06-04 07:29 122阅读 0赞

上一篇文章了解了队列的概念和一些特性，并用java简单实现一个队列。今天就实现队列两种最常见的实现  
数组实现和链表实现。

### 队列的数组实现 ###

代码：

public class CustomArrayQueue<E> {
    
    
        private int tail; //尾元素的位置
    
        private int head; //头元素的位置
    
        private float factory = 0.75F; //数组的扩容因子
    
        private Object[] table;//用于存放数据的数组
    
        private int default_lenght = 10; //数组的初始长度
    
        private int length; //当前数组的长度
    
        private int size = 0; //当前的数据量
    
        public CustomArrayQueue() { // 队列初始化，数组默认长度为10
            this.table = new Object[default_lenght];
            this.head = 0;
            this.tail = 0;
        }
    
        // 队列初始化，数组默认长度为传入的值，当<=0时，采用默认长度
        public CustomArrayQueue(int capacity) {
    
            this.head = 0;
            this.tail = 0;
            if (capacity <= 0) {
                this.table = new Object[default_lenght];
            } else {
                this.table = new Object[capacity];
            }
        }
    
    
        /** * 新增一个元素 * 判断当前容量是否达到扩音的条件，如果达到扩容的条件，就在原来的长度上增加10个位置 * 否则不扩容 * 把新增的元素放到为元素的后一位 * @param e * @return */
        public Object add(E e) {
    
            int tempLenght = table.length;
            BigDecimal tempBig = new BigDecimal(tempLenght);
            BigDecimal tailBig = new BigDecimal(tail);
            float tempFactory = tailBig.divide(tempBig, 2, BigDecimal.ROUND_UP).floatValue();
            if (tempFactory >= factory) {
                table = Arrays.copyOf(table, tempLenght + 10);
            }
    
            table[tail] = e;
            tail++;
            size++;
            return e;
        }
    
        //获取队列元素的数量
        public int size() {
            return size;
        }
    
        // 获取队列的长度
        public int length() {
    
            return table.length;
        }
    
        public E pop() {
            E e;
            if (size == 0) {
                return null;
            } else {
                e = (E)table[head];
                head++;
                size--;
                return e;
            }
        }
    }

上面简单实现一个基于数组的队列，实现了几个简单的方法。

测试代码：

public class QueueTest {
    
    
        public static void main (String[] args) {
            //CustomQueue<String> queue = new CustomQueue<String>();
            CustomArrayQueue<String> queue = new CustomArrayQueue<>();
            queue.add("123");
            queue.add("456");
            queue.add("789");
            queue.add("147");
    
            System.out.println("数量=" + queue.size());
            System.out.println("取出第一个" + queue.pop());
            System.out.println("取出第二个" + queue.pop());
            System.out.println("取出第三个" + queue.pop());
            System.out.println("取出第四个" + queue.pop());
            System.out.println("取出第五个" + queue.pop());
            System.out.println("取出第六个" + queue.pop());
        }
    
    }

输出结果：

数量=4
    取出第一个123
    取出第二个456
    取出第三个789
    取出第四个147
    取出第五个null
    取出第六个null

数组的实现的逻辑非常的简单，第一，数组是有序的，第二，数组的下标处理起来非常的简单。

但是这里是有问题，主要问题是：  
1、容易产生冗余数据；  
2、边界问题；

第一个冗余数据的问题，如下例子：  
***数组的容量为100，已经取出了98个元素，当前head为98,0-97位的数据已经被取走，这些位置已经空了，但是数组还在使用，如果新加元素只能继续扩容，继续往后面加，导致大量的位置空闲。***  
这种现象被称为“假上溢”现象；  
这是使用数组实现必须解决的问题；；

第二个边界问题，如下例子：  
***当前内容只能分配100个元素的空间，无法扩容了，继续添加元素，这时没办法添加了。***

这种现象被称为“真上溢”现象。

“真上溢”暂时没办法解决，但是“假上溢”现象是可以解决的；  
下面是在自己实现的队列中解决“假上溢”问题。

解决“假上溢”有两种解决方法：  
– 利用数组扩容方法；空余位置达到临界点时，就利用数组扩容方法新建一个数组，把原来的数据复制到新数据的0位。  
– 采用循环队列的方式存储数据

#### 数组扩容解决方案 ####

代码：

/** * 新增一个元素 * 判断当前容量是否达到扩音的条件，如果达到扩容的条件，就在原来的长度上增加10个位置 * 否则不扩容 * 把新增的元素放到为元素的后一位 * 当空余余位置大于10时，触发解决假上溢代码 * @param e * @return */
        public Object add(E e) {
    
            int tempLenght = table.length;
            BigDecimal tempBig = new BigDecimal(tempLenght);
            BigDecimal tailBig = new BigDecimal(tail);
            float tempFactory = tailBig.divide(tempBig, 2, BigDecimal.ROUND_UP).floatValue();
            if (tempFactory >= factory) {
                table = Arrays.copyOf(table, tempLenght + 10);
            }
    
            table[tail] = e;
            tail++;
            size++;
            //当空余位置大于10时，触发解决假上溢代码
            if (head >= 10) {
                table = Arrays.copyOf(table, table.length + 10);
                head = 0;
                tail = tail - head;
            }
    
            return e;
        }

#### 循环队列解决方案 ####

代码：

/** * 新增一个元素 * 判断当前容量是否达到扩音的条件，如果达到扩容的条件，就在原来的长度上增加10个位置 * 否则不扩容 * 把新增的元素放到为元素的后一位 * 采用循环队列解决假上溢问题 * @param e * @return */
        public Object add(E e) {
    
            int tempLenght = table.length;
            BigDecimal tempBig = new BigDecimal(tempLenght);
            BigDecimal tailBig = new BigDecimal(tail);
            float tempFactory = tailBig.divide(tempBig, 2, BigDecimal.ROUND_UP).floatValue();
            if (tempFactory >= factory) {
                table = Arrays.copyOf(table, tempLenght + 10);
            }
    
            int realIndex = tail/table.length;
    
            if (realIndex == head && tail > head) {
                //这是已经没有位置存放了，触发了真上溢问题，完整实现时，此时应该抛出异常
            }
    
            table[realIndex] = e;
            tail++;
            size++;
            当空余位置大于10时，触发解决假上溢代码
            //if (head >= 10) { 
            // table = Arrays.copyOf(table, table.length + 10);
            // head = 0;
            // tail = tail - head;
            //}
    
            return e;
        }

#### 总结 ####

以上就是队列的基本实现，主要是要理解先入先出的特性，还要明白这种实现的溢出问题。

### 队列的链表实现 ###

在上一篇学习队列特性中写的一个简单实现，就是基于链表的队列实现，这里就不重复描述了，主要是需要对链表有一定的了解。  
另外，这种实现发方式不存在“假上溢”的现象。

### 总结 ###

上面描述队列的数组实现和链表实现，都是简单的实现，没有实现完成的代码，如果一个完整的实现，应该把通用方法提出来作为接口使用，数组实现和链表实现实现这个接口。

另外，文中并没有涉及队列遍历的问题，要实现一个可用的队列，必须实现遍历，一般情况下是实现匿名的Iterator子类。

还有并发安全的问题，并发安全有两种实现方法  
– 用synchronized修饰所有操作数据的方法  
– 用lock安全操作所有的数据

java源码中采用的就是ReentrantLock来解决线程安全的问题的。