投稿
  1. 首页
  2. 随笔

Java数据结构之队列详解

一键清除系统垃圾 • 2022-12-17 • 随笔 • 阅读 56

Java数据结构之队列详解,第1张

Java数据结构之队列详解 前言

        介绍队列的定义，队列的构造与方法实现，循环队列以及双端队列的分别手撕实现；

队列定义：

        队列是一种比较特殊的线性结构。它只允许在表的前端（front）进行删除 *** 作，而在表的后端（rear）进行插入 *** 作。进行插入 *** 作的端称为队尾，进行删除 *** 作的端称为队头。
队列中最先插入的元素也将最先被删除，对应的最后插入的元素将最后被删除。因此队列又称为“先进先出”（FIFO—first in first out）的线性表，与栈(FILO-first in last out)刚好相反，队列（Queue）是先进先出（FIFO）的，并且我们可以用数组、链表还有 List 的方式来实现自定义队列。

Queue的源码以及注释： 
public interface Queue extends Collection {
    
    boolean add(E e);

    
    boolean offer(E e);

    
    E remove();

    
    E poll();

    
    E element();

    
    E peek();
}

        Queue接口与List、Set同一级别，都是继承了Collection接口。linkedList实现了Queue接 口。Queue接口窄化了对linkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 linkedList的非Queue的方法），以使得只有恰当的方法才可以使用。

Queue简单实现接口及其方法：

        先进者先出，这就是典型的“队列”。(First In, First Out，FIFO)。

        我们知道，栈支持两个基本 *** 作：入栈push()和出栈pop()。队列跟栈非常相似，支持的 *** 作也很有限，最基本的 *** 作也是两个：入队和出队。入队 enqueue()，让一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。队列跟栈一样，也是一种 *** 作受限的线性表数据结构。跟栈类似，用数组实现的队列叫做顺序队列.用链表实现的队列叫做链式队列

public interface Queue extends Iterable {
    public void offer(E element);   //入队
    public E poll();    //出队
    public E element();    //查看队首元素
    public boolean isEmpty();    //判空
    public void clear();    //清空
    public int size();      //返回元素个数
}
import p1.接口.Queue;
import java.util.Iterator;

public class ArrayQueue implements Queue {
    private ArrayList list;    //通过ArrayList实现Queue
    //构造
    public ArrayQueue() {
        list = new ArrayList<>();
    }
    //offer方法
    @Override
    public void offer(E element) {
        list.add(list.size(), element);
    }
    //poll方法
    @Override
    public E poll() {
        return list.remove(0);
    }
    //element方法
    @Override
    public E element() {
        return list.get(0);
    }
    //isEmpty方法
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
    //clear方法
    @Override
    public void clear() {
        list.clear();
    }
    //size方法
    @Override
    public int size() {
        return list.size();
    }
    //迭代
    @Override
    public Iterator iterator() {
        return list.iterator();
    }
    //toString方法
    @Override
    public String toString() {
        return list.toString();
    }
    //equals方法
    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayQueue) {
            ArrayQueue other = (ArrayQueue) o;
            return list.equals(other.list);
        }
        return false;
    }
}

     Arraylist简易写法，用ArrayList 实现Queue可以进行参考；（代码如下：）

List接口：

import java.util.Comparator;
//线性表接口定义
public interface List extends Iterable  {
    //默认在表尾添加一个元素
    public void add(E element);
    //在指定角标处添加元素
    public void add(int index, E element);
    //删除指定元素
    public void remove(E element);
    //删除指定角标处的元素 并返回原先的值
    public E remove(int index);
    //获取指定角标处的元素
    public E get(int index);
    //修改指定角标index处的值为element 并返回原先的值
    public E set(int index, E element);
    //获取线性表中的元素个数
    public int size();
    //查看元素第一次出现的角标位置（从左到右）
    public int indexOf(E element);
    //判断是否包含元素
    public boolean contains(E element);
    //判断线性表是否为空
    public boolean isEmpty();
    //清空线性表
    public void clear();
    //按照比较器的内容进行排序
    public void sort(Comparator c);
    //获取子线性表 原线性表中[fromIndex, toIndex]这个部分
    public List subList(int fromIndex, int toIndex);
}

ArrayList实现：

import java.util.Iterator;
import java.util.List;
public class ArrayList implements List {

    private E[] data;

    private int size;

    private static int DEFAULT_CAPACITY = 10;

    public ArrayList() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    public ArrayList(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must > 0");
        }
        DEFAULT_CAPACITY = capacity;
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    public ArrayList(E[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr can not be null");
        }
        data = (E[]) new Object[DEFAULT_CAPACITY];
        for (int i = 0; i < arr.length; i++) {
            add(arr[i]);
        }
    }

    @Override
    public void add(E element) {
        add(size, element);
    }

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index out of range");
        }
     
        if (size == data.length) {
            resize(2 * data.length);
        }
    
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
      
        data[index] = element;
        size++;
    }


    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    @Override
    public void remove(E element) { 
        int index = indexOf(element);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove index out of range");
        }
        
        E ret = data[index];

        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;

        if (size == data.length / 4 && data.length > DEFAULT_CAPACITY) {
            resize(data.length / 2);
        }
        return ret;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get index out of range");
        }
        return data[index];
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("set index out of range");
        }
        E ret = data[index];
        data[index] = element;
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    private int getCapacity() {
        return data.length;
    }

    @Override
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    @Override
    public void sort(Comparator c) {
        if (c == null) {
            throw new IllegalArgumentException("comparator can not be null");
        }
        for (int i = 1; i < size; i++) {
            E e = data[i];
            int j = 0;
            for (j = i; j > 0 && c.compare(data[j - 1], e) > 0; j--) {
                data[j] = data[j - 1];
            }
            data[j] = e;
        }
    }

    @Override
    public List subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
            throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");
        }
        ArrayList list = new ArrayList<>();
        for (int i = fromIndex; i <= toIndex; i++) {
            list.add(data[i]);
        }
        return list;
    }

    @Override
    public boolean equals(Object o) {
      
        if (o == null) {
            return false;
        }
    
        if (this == o) {
            return true;
        }
     
        if (o instanceof ArrayList) {

            ArrayList other = (ArrayList) o;
         
            if (size != other.size) {
                return false;
            }
      
            for (int i = 0; i < size; i++) {
                if (!data[i].equals(other.data[i])) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
        } else {
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                if (i == size - 1) {
                    sb.append(']');
                } else {
                    sb.append(',');
                    sb.append(' ');
                }
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator iterator() {
        return new ArrayListIterator();
    }

    class ArrayListIterator implements Iterator {
        private int cur = 0;

        @Override
        public boolean hasNext() {
            return cur < size;
        }

        @Override
        public E next() {
            return data[cur++];
        }
    }
}

        根据先前博客中的栈，以及本次的队列会发现二者有相似之处，即可以通过栈来实现队列；具体实现代码如下；

import 接口.Queue;

import java.util.Iterator;

//栈实现队列
public class StackToQueue {
    public static void main(String[] args) {
        QueueImplByStack queue = new QueueImplByStack<>();
        for (int i = 1; i <= 5; i++) {
            queue.offer(i);
        }
        System.out.println(queue);
        System.out.println(queue.poll());
        System.out.println(queue);
    }
}
class QueueImplByStack implements Queue {
    private ArrayStack stackA;
    private ArrayStack stackB;
    public QueueImplByStack() {
        stackA = new ArrayStack<>();
        stackB = new ArrayStack<>();
    }

    @Override
    public void offer(E element) {
        stackA.push(element);
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        while (stackA.size() != 1) {
            stackB.push(stackA.pop());
        }
        E ret = stackA.pop();

        while (!stackB.isEmpty()) {
            stackA.push(stackB.pop());
        }
        return ret;
    }

    @Override
    public E element() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        while (stackA.size() != 1) {
            stackB.push(stackA.pop());
        }
        E ret = stackA.peek();

        while (!stackB.isEmpty()) {
            stackA.push(stackB.pop());
        }
        return ret;
    }

    @Override
    public boolean isEmpty() {
        return stackA.isEmpty();
    }

    @Override
    public void clear() {
        stackA.clear();
    }

    @Override
    public int size() {
        return stackA.size();
    }

    @Override
    public Iterator iterator() {
        return stackA.iterator();
    }

    @Override
    public String toString() {
        return stackA.toString();
    }
}
使用Queue实现文件夹遍历： 
import java.io.File;
//遍历文件
public class CheckFiles {
	public static void main(String[] args) {
		File dir = new File("C:\Users\Administrator\Desktop");
		ArrayQueue queue = new ArrayQueue<>();
		queue.offer(dir);
		while(!queue.isEmpty()) {
			File file = queue.poll();
			System.out.println("{" + file.getName() + "}");
			File[] files = file.listFiles();
			
			for(File f : files) {
				if(f.isFile()) {
					System.out.println( f.getName());
				}else {
					queue.offer(f);
				}
			}
		}
	}
}

 对队列进行优化：

 元素添加进来后，rear左移；如下图

 从头部删除时，元素出对，front右移；如下图

 

 然后再front 与rear的一直遍历下出现了下图所示：

 这个时候，rear已经达到了队列的底部，我们会发现在队列前面有大量空出的位置，对队列的空间并没有完整的利用起来；造成了空间的大量浪费。那除了这样的方法之外，还有没有别的方法？答案是有，下面的情况就是一种。我们引出了循环队列的概念。

循环队列：

        与队列相同，循环队列也是先进新出，但是在java中，给定义一定大小的数组，当在队列中进行删除时，再从队尾进行添加时造成大量空间的浪费，为了减少队列中空间的浪费，我们给定循环队列来，即队列的尾部与队列的前端相连，形成一个类似环的队列。

        简单来说：队尾的下一跳指向了队首。

 从下标为0的地方新增一个元素入队；rear往右走，来到了队首

 从原本的front的位置出队 *** 作时候，front往右移动一位；

 在0的位置新增一个元素，rear从7移动到了0号位置；

 

 在3的地方进行删除，front从3移动到4号位置；

对队列一直进行添加，知道满足下面的情况，我们会发现，rear+1 =front；

 同时当删除到下图的时候，front=rear的位置；整个队列为空

 奇怪的是，当我们的front移动到rear的左边时。同样会出现rear+1=front

 

 列空和列满的条件竟然相同，这不就是逻辑bug嘛？

为了解决这个bug，我们给定一个null空间，让最后近乎满队的时候，rear指向那个null空间；

 队列满时，（rear+1）% length =front；

 

 

 队列空时，front==rear，此时就解决了刚刚的bug；

       其中关于循环队列注意的事情：

当初始化队列为空时，front = rear = 0；入队，rear+1，指向队尾的下一个存储单元，为了实现循环利用取模运算：rear = (rear+1) % max;出队，front+1，指向下一个队首，实现循环：front = (front+1) % max;判断队满，(rear+1) % length == front

Queue接口实现：

public interface Queue extends Iterable {
    public void offer(E element); 
    public E poll();    
    public E element();    
    public boolean isEmpty();
    public void clear();
    public int size();
}
import p1.Queue;
import java.util.Iterator;
//循环队列
public class ArrayLoopQueue implements Queue {
    private E[] data;   //存储数据的容器
    private int front;  //队首指针(实际上就是数组中的索引角标)
    private int rear;   //队尾指针
    private int size;   //元素的个数 (f < r  r-f ; r < f  r+L-f)
    private static int DEFAULT_CAPACITY = 10;   //默认容量
    public ArrayLoopQueue() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }
    @Override
    public void offer(E element) {
      
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }
    @Override
    public E poll() {
        
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        int index = 0;
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            newData[index++] = data[i];
        }
        data = newData;
        front = 0;
        rear = index;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        return data[front];
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
        front = 0;
        rear = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if ((i + 1) % data.length == rear) {
                sb.append(']');
            } else {
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayLoopQueue) {
            ArrayLoopQueue other = (ArrayLoopQueue) o;
            if (size != other.size) {
                return false;
            }
            int i = front;
            int j = other.front;
            while (i != rear) {
                if (!data[i].equals(other.data[j])) {
                    return false;
                }
                i = (i + 1) % data.length;
                j = (j + 1) % other.data.length;
            }
            return true;
        }
        return false;
    }

    @Override
    public Iterator iterator() {
        return new ArrayLoopQueueIterator();
    }

    class ArrayLoopQueueIterator implements Iterator {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}
双端队列：

         一种可以在表头和表尾进行出队和入队的线性表，具有队列的性质，也可以理解为栈结构的变种。双端队列或 Deque 扩展队列以允许元件从两端插入和移除。Deque 类的实例表示双端队列，Deque 接口扩展了 Queue 接口，它声明了方便所有 *** 作的其他方法对于头部以及尾部的队列。它可以用作FIFO队列或LIFO队列。ArrayDeque 和 linkedList类是Deque接口的两个实现类。ArrayDeque 类由数组支持，而 linkedList 类由链表支持。如果您使用Deque作为堆栈，则应该使用 ArrayDeque 作为 Deque 实现。如果使用 Deque 作为FIFO队列， 可以使用linkedList。

 

 

 同样的，双端队列很类似于我们的循环队列；此时

public interface Queue extends Iterable {
    public void offer(E element);  
    public E poll();    
    public E element();    
    public boolean isEmpty();
    public void clear();
    public int size();
}
public interface Dequeue extends Queue {
	 	public void addFirst(E element);
	    public void addLast(E element);
	    public E removeFirst();
	    public E reomveLast();
	    public E getFirst();
	    public E getLast();
}
import 接口.Dequeue;
import 接口.Stack;
import java.util.Iterator;
public class ArrayDeque implements Dequeue, Stack {
    private E[] data;
    private int front;
    private int rear;
    private int size;
    private static int DEFAULT_CAPACITY = 10;
    public ArrayDeque() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }
    @Override
    public void addFirst(E element) {
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        front = (front - 1 + data.length) % data.length;
        data[front] = element;
        size++;
    }

    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        int index = 0;
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            newData[index++] = data[i];
        }
        data = newData;
        front = 0;
        rear = index;
    }

    @Override
    public void addLast(E element) {
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

    @Override
    public E removeFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return null;
    }

    @Override
    public E reomveLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        rear = (rear - 1 + data.length) % data.length;
        E ret = data[rear];
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E getFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        return data[front];
    }

    @Override
    public E getLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        return data[(rear - 1 + data.length) % data.length];
    }

    @Override
    public void offer(E element) {
        addLast(element);
    }

    @Override
    public E poll() {
        return removeFirst();
    }

    @Override
    public E element() {
        return getFirst();
    }

    @Override
    public E peek() {
        return getLast();
    }

    @Override
    public boolean isEmpty() {
        return size == 0 && front == rear;
    }

    @Override
    public void push(E element) {
        addLast(element);
    }

    @Override
    public E pop() {
        return reomveLast();
    }

    @Override
    public void clear() {
        E[] data = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if ((i + 1) % data.length == rear) {
                sb.append(']');
            } else {
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator iterator() {
        return new ArrayDequeIterator();
    }

    class ArrayDequeIterator implements Iterator {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}

基于数组实现的双端队列（Deque）就可以解决上面这些问题，它让我们在数组开头结尾进行插入、删除元素时，平均时间复杂度做到 O(1)。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5707726.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
一键清除系统垃圾 一键清除系统垃圾 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存