队列Queue(Java)

快来打我* 2023-06-30 14:59 25阅读 0赞

# 队列Queue #

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

*  队列是一种线性结构
 *  相比数组，队列相应的操作是数组的子集
 *  只能从队尾添加元素，只能从队首取出元素

下述队列是以动态数组为底层实现  
**动态数组[动态数组及均摊复杂度与防止复杂度震荡][Link 1]**

//动态数组
    public class Arr<E> {
        
    	private E[] data;// 创建一个数组
    	private int size;// 数组中元素个数
    
    	// 自定义构造器初始化数组 capacity数组的长度
    	public Arr(int capacity) {
        
    		// TODO Auto-generated constructor stub
    		data = (E[]) new Object[capacity];
    		size = 0;
    	}
    
    	// 默认构造方法 capacity数组的长度=10
    	public Arr() {
        
    		// TODO Auto-generated constructor stub
    		this(10);
    	}
    
    	// 获取数组个数
    	public int getSize() {
        
    		return size;
    	}
    
    	// 获取数组长度
    	public int getCapacity() {
        
    		return data.length;
    	}
    
    	// 判断数组是否为空
    	public boolean isEmpty() {
        
    		return size == 0;
    	}
    
    	// 数组中添加元素 index是插入元素的位置，e是插入的元素，时间复杂度为O(n)
    	public void add(int index, E e) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("数组排列要求不能有空");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		// 数组扩容
    		if (size == data.length) {
        
    			try {
        
    				resize(2 * data.length); // 这里是扩容为原数组的2倍，Arraylist是扩容1.5倍
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		for (int i = size - 1; i >= index; i--) {
        
    			data[i + 1] = data[i];
    		}
    		data[index] = e;
    		size++;
    	}
    
    	// 数组扩容或者缩容,时间复杂度为O(n)
    	private void resize(int newcapcatity) {
        
    		// TODO Auto-generated method stub
    		E[] newData = (E[]) new Object[newcapcatity];
    		for (int i = 0; i < size; i++) {
        
    			newData[i] = data[i];
    		}
    		data = newData;
    	}
    
    	// 在数组末尾添加元素,时间复杂度为O(1)
    	public void addLast(E e) {
        
    		add(size, e);
    	}
    
    	// 在数组首部添加元素,时间复杂度为O(n)
    	public void addFirst(E e) {
        
    		add(0, e);
    	}
    
    	// 重写toString 使用字符串拼接
    	@Override
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append(String.format("Array:size = %d, capacity = %d\n", size, data.length));
    		res.append('[');
    		for (int i = 0; i < size; i++) {
        
    			res.append(data[i]);
    			if (i != size - 1) {
        
    				res.append(',');
    			}
    		}
    		res.append(']');
    		return res.toString();
    	}
    	
    	//获取最后一个元素
    	public E getLast() {
        
    		return get(size - 1);
    	}
    
    	//获取第一个元素
    	public E getFirst() {
        
    		return get(0);
    	}
    
    	// 获取index位置的数组元素,时间复杂度为O(1)
    	E get(int index) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		return data[index];
    	}
    
    	// 修改数组元素,时间复杂度为O(1)
    	void set(int index, E e) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e3) {
        
    				// TODO Auto-generated catch block
    				e3.printStackTrace();
    			}
    		}
    		data[index] = e;
    	}
    
    	// 查询是否包含数组元素e,时间复杂度为O(n)
    	public boolean contains(E e) {
        
    		for (int i = 0; i < size; i++) {
        
    			if (data[i].equals(e))
    				return true;
    		}
    		return false;
    	}
    
    	// 查找数组元素e,时间复杂度为O(n)
    	public int find(E e) {
        
    		for (int i = 0; i < size; i++) {
        
    			if (data[i].equals(e))
    				return i;// 返回元素e的位置
    		}
    		return -1;// 找不到元素e，返回-1
    	}
    
    	// 删除指定位置index的数组元素,时间复杂度为O(n)
    	public E remove(int index) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e3) {
        
    				// TODO Auto-generated catch block
    				e3.printStackTrace();
    			}
    		}
    		// 缩容
    		if (size == data.length / 2) {
        
    			resize(data.length / 2);
    		}
    		E ret = data[index];
    		for (int i = index + 1; i < size; i++) {
        
    			data[i - 1] = data[i];
    		}
    		size--;
    		data[size] = null;
    		return ret;// 返回删除的元素
    	}
    
    	// 数组删除首个元素,时间复杂度为O(n)
    	public E removeFirst() {
        
    		return remove(0);
    	}
    
    	// 数组删除最后一个元素,时间复杂度为O(1)
    	public E removeLast() {
        
    		return remove(size - 1);
    	}
    
    	// 数组删除元素e,时间复杂度为O(n)
    	public void removeElement(E e) {
        
    		int index = find(e);
    		if (index != -1) {
        
    			remove(index);
    		} else {
        
    			System.out.println("数组中没有元素e");
    		}
    	}
    }

**对列接口Queue**

public interface Queue<E> {
        
    	
    	void enqueue(E e);//入队
    	E dequeue();//出队
    	E getFront();//获取队首元素
    	int getSize();//获取队列中元素个数
    	boolean isEmpty();//判断队列是否为空
    }

**队列ArrayQueue**

public class ArrayQueue<E> implements Queue<E>  {
        
    	
    	private Arr<E> array;
    	public ArrayQueue(int capacity) {
        
    		// TODO Auto-generated constructor stub
    		array = new Arr<>(capacity);
    	}
    	public ArrayQueue() {
        
    		// TODO Auto-generated constructor stub
    		array = new Arr<>();
    	}
    	@Override
    	public void enqueue(E e) {
        
    		// TODO Auto-generated method stub
    		array.addLast(e);
    	}
    
    	@Override
    	public E dequeue() {
        
    		// TODO Auto-generated method stub
    		return array.removeFirst();
    	}
    
    	@Override
    	public E getFront() {
        
    		// TODO Auto-generated method stub
    		return array.getFirst();
    	}
    
    	@Override
    	public int getSize() {
        
    		// TODO Auto-generated method stub
    		return array.getSize();
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		// TODO Auto-generated method stub
    		return array.isEmpty();
    	}
    	
    	public int getCapacity() {
        
    		return array.getCapacity();
    	}
    	
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append("Queue：");
    		res.append("front [");
    		for (int i = 0; i < array.getSize(); i++) {
        
    			res.append(array.get(i));
    			if(i != array.getSize()-1)
    				res.append(",");
    		}
    		res.append("] tail");
    		return res.toString();
    	}
    }

**测试**

public class Test02 {
        
    	public static void main(String[] args) {
        
    		ArrayQueue<Integer> queue = new ArrayQueue<>();
    		for (int i = 0; i < 5; i++) {
        
    			queue.enqueue(i);
    			System.out.println(queue);
    		}
    		queue.dequeue();
    		System.out.println(queue);
    		System.out.println("队首元素为："+queue.getFront());
    	}
    }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]  
**数组对列复杂度分析**

*  void enqueue(E) 均摊复杂度O(1)
 *  E dequeue() 均摊复杂度O(n)
 *  E front() 复杂度O(1)
 *  int getSize() 复杂度O(1)
 *  boolean isEmpty() 复杂度O(1)

[Link 1]: https://blog.csdn.net/weixin_44190113/article/details/103978491
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200118121738539.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70