数据结构之数组队列

Bertha 。 2022-05-25 09:54 114阅读 0赞

**队列的特性：**  
1.队列是一种线性数据结构，与数组相比，队列的方法是数组的子集；  
2.向队列中添加元素只能在队尾进行，在队首删除元素；  
3.队列是一种先进先出的数据结构；  
**队列的方法：**  
1.void enqueue(E e);向队列中添加元素；  
2.E dequeue();从队列中删除元素；  
3.int getSize();获取队列的大小；  
4.E setFront();获取队首元素；  
5.boolean isEmpty();判断队列是否为空；

**数组的底层·代码实现：**

package cn.DataStructures.ArrayQueue;
    /** * 在数组中添加元素 * 1.在末尾位置添加元素 * 2.在数组元素中任意位置添加元素 * @author Administrator * */
    public class Array <E> {
        private E [] data;
        private int size;
        //有参构造，确定数组容量为capacity
        public Array(int capacity){
            data=(E[])new Object[capacity];
            size=0;
        }
        //无参构造，默认数组容量为10；
        public Array(){
            this(10);
        }
        //获取数组容量
        public int getCapacity(){
            return data.length;
        }
        //获取数组中元素的个数
        public int getSize(){
            return size;
        }
        //判断数组是否为空
        public boolean isEmpty(){
            return size==0;
        } 
        //在元素的最后位置添加元素
        public void addLast(E e){
            add(size,e);
        }
        //在数组的第一个位置上添加元素
        public void addFirst(E e){
            add(0,e);
        }
        //在数组中的任意位置添加元素
        public void add(int index,E e){
    
            if(index<0 || index>size){
                throw new IllegalArgumentException("该索引位置不可以插入元素！");
            }
            if(size==data.length){
                resize(2*data.length);//数组如果不够用，则扩容
            }
            for(int i=size-1;i>=index;i--){
                data[i+1]=data[i];
    
            }
            data[index]=e;
            size++;
    
        }
        //更改对应索引上的元素
        public void set(int index,E e){
            if(index<0|| index>=size){
                throw new IllegalArgumentException("该索引不合法！");
            }
            data[index]=e;
        }
        //获取对应索引位置上的元素
        public E get(int index){
            if(index<0|| index>=size){
                throw new IllegalArgumentException("该索引不合法！");
            }
            return data[index];
        }
        //获取数组中第一个元素
        public E getFirst(){
            return get(0);
        }
        //获取数组中最后一个元素
        public E getLast(){
            return get(size-1);
        }
        //显示数组中的元素
        public String toString(){
            StringBuilder sb=new StringBuilder();
            sb.append(String.format("Array: size=%d, capacity=%d\n", size,data.length));
            sb.append("[");
            for(int i=0;i<size;i++){
                sb.append(data[i]);
                if(i!=size-1){
                    sb.append(", ");
                }
    
            }
            sb.append("]");
            return sb.toString();
    
        }
        //判断数组中是否有元素e
        public boolean  contains(E e){
            for(int i=0;i<size;i++){
                if(data[i].equals(e)){
                    return true;
                }
    
            }
            return false;
        }
        //找出对应元素对应的索引
        public int find(E e){
            for(int i=0;i<size;i++){
                if(data[i].equals(e)){
                    return i;
                }
            }
            return -1;
        }
        //删除元素，并返回删除的元素
        public E remove(int index){
            if(index<0||index>=size){
                throw new IllegalArgumentException("该索引不合法！");
            }
            E res=data[index];
            for(int i=index+1;i<size;i++){
                data[i-1]=data[i];
            }
            size--;
            if(size==data.length/4&&data.length/2!=0){
                resize(data.length/2);//当数组中的元素个数小于等于数组容量的一般时，则动态的减少数组容量，将数组的容量变为原来的一半
            }
            return res;
        }
        //删除数组第一个元素,并返回删除的元素
        public E removeFirst(){
            return remove(0);
        }
        //删除数组最后一个元素,并返回删除的元素
        public E removeLast(){
            return remove(size-1);//在调用remove方法时会帮我们判断数组是否为空
        }
        //查找元素e，如果找到则删除
        public void removeElement(E e){
       //用户在删除指定元素后就已经知道元素了，所以不用返回值返回具体的删除的元素
            int index=find(e);//找到要删除的元素的对应的索引
            if(index!=-1){
                remove(index);
            }
        }
        //对数组进行扩容，动态数组
        private void resize(int newCapacity){
                E [] newdata=(E[])new Object[newCapacity];
                for(int i=0;i<size;i++){
                    newdata[i]=data[i];
                }
                data=newdata;
        }
    }

**创建队列接口：**

package cn.DataStructures.ArrayQueue;
    
    public interface Queue <E>{
        public void enqueue(E e);
        public E dequeue();
        public int getSize();
        public E setFront();
        public boolean isEmpty();
    
    }

**数组队列的代码实现：**

package cn.DataStructures.ArrayQueue;
    //构造方法，并实现接口
    public class ArrayQueue <E> implements Queue<E>{ 
        private Array<E> array;
        public ArrayQueue(int capacity){
            array=new Array<>(capacity);
        }
        public ArrayQueue(){
            array=new Array<>();
        }
        @Override
        public void enqueue(E e){
            array.addLast(e);
        }
        @Override
        public E dequeue(){
            return array.removeFirst();
        }
        @Override
        public int getSize(){
            return array.getSize();
        }
        @Override
        public boolean isEmpty(){
            return array.isEmpty();
        }
        @Override
        public E setFront(){
            return array.getFirst();
        }
        public String toString(){
            StringBuilder res=new StringBuilder();
            res.append("queue:").append("Front：[");
            for(int i=0;i<array.getSize();i++){
                res.append(array.get(i));
                if(i!=array.getSize()-1){
                    res.append(", ");
                }
            }
            res.append("]").append("tail");
            return res.toString();
        }
        public static void main(String[] args) {
            ArrayQueue<Integer> array=new ArrayQueue<>();
            for(int i=0;i<10;i++){
                array.enqueue(i);
                System.out.println(array);
                if(i%3==2){
                    array.dequeue();
                }
                System.out.println(array);
            }
            array.setFront();
        }
    
    }

**数组队列的时间复杂度分析：**  
对于队列的添加enqueue(E e)、队首的查询setFront()、获取队列大小getSize()、判断isEmptty()操作，每一次只对队列的一个元素进行一次操作，所以时间复杂度为：O(1)  
对于队列的删除操作dequeue()，因为每次从队列的首部删除一个元素时，后面的元素都要向前挪动一个位置，所以删除操作时是对整个队列元素进行操作，所以此时时间复杂度是：O(n)