Java数据结构与算法-队列

àì夳堔傛蜴生んèń 2021-11-17 10:32 397阅读 0赞

参考《算法》（第四版）

# 一、队列的作用 #

队列是基于先进先出（FIFO）的集合。现实中类似的场景有在银行大厅排队、汽车过收费站排队等。队列的作用在于1）将数据保存在容器中，2）同时还保存了元素间相对顺序。

比如一个从文件中读取整数，并返回int数组的实现就可以用到队列，这样就不必提前知道文件大小：

1 public static int[] readInts(String name){
     2     In in = new In(Name);
     3     Queue<Integer> q = new Queue<Integer>();
     4     while(!in.isEmpty()) {
     5         q.enqueue(in.readInt());
     6     }
     7     
     8     int N = q.size();
     9     int[] a = new int[N];
    10     for(int i =0; i < N; i++) {
    11         a[i] = q.dequeue();
    12     }
    13     return a;
    14 }

# 二、队列的实现 #

队列可以用1）链表 2）数组 来实现。

## 1、链表实现： ##

algs4中实现方法：

1 public class Queue<Item> implements Iterable<Item> {
     2     private Node<Item> first;    // 指向对首
     3     private Node<Item> last;     // 指向队尾
     4     private int n;               // 元素数量
     5 
     6     // 静态内部类存储元素，及链表指针
     7     private static class Node<Item> {
     8         private Item item;
     9         private Node<Item> next;
    10     }
    11 
    12     public Queue() {
    13         first = null;
    14         last  = null;
    15         n = 0;
    16     }
    17 
    18     public boolean isEmpty() {
    19         return first == null;
    20     }
    21 
    22     public int size() {
    23         return n;
    24     }
    25 
    26     // 返回对首
    27     public Item peek() {
    28         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    29         return first.item;
    30     }
    31 
    32     //入队
    33     public void enqueue(Item item) {
    34         Node<Item> oldlast = last;
    35         last = new Node<Item>();
    36         last.item = item;
    37         last.next = null;
    38         if (isEmpty()) first = last;
    39         else           oldlast.next = last;
    40         n++;
    41     }
    42     //出队
    43     public Item dequeue() {
    44         if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    45         Item item = first.item;
    46         first = first.next;
    47         n--;
    48         if (isEmpty()) last = null;   // to avoid loitering
    49         return item;
    50     }
    51 
    52 
    53     public Iterator<Item> iterator()  {
    54         return new ListIterator<Item>(first);  
    55     }
    56 
    57     
    58     private class ListIterator<Item> implements Iterator<Item> {
    59         private Node<Item> current;
    60 
    61         public ListIterator(Node<Item> first) {
    62             current = first;
    63         }
    64 
    65         public boolean hasNext()  { return current != null;                     }
    66         public void remove()      { throw new UnsupportedOperationException();  }
    67 
    68         public Item next() {
    69             if (!hasNext()) throw new NoSuchElementException();
    70             Item item = current.item;
    71             current = current.next; 
    72             return item;
    73         }
    74     }
    75 }

## 2、数组实现： ##

参考ArrayQueue实现，利用环形数组，（数组长度取模）：

注意：

1）head，tail含义，head：队首；tail队尾可加入的空位。

2）有意保留一个空单元

1 public class ArrayQueue<T> extends AbstractList<T> {
     2     public ArrayQueue(int capacity) {
     3         this.capacity = capacity + 1;
     4         this.queue = newArray(capacity + 1);
     5         this.head = 0;
     6         this.tail = 0;
     7     }
     8 
     9     public void resize(int newcapacity) {
    10         int size = size();
    11         if (newcapacity < size)
    12             throw new IndexOutOfBoundsException("Resizing would lose data");
    13         newcapacity++;
    14         if (newcapacity == this.capacity)
    15             return;
    16         T[] newqueue = newArray(newcapacity);
    17         for (int i = 0; i < size; i++)
    18             newqueue[i] = get(i);
    19         this.capacity = newcapacity;
    20         this.queue = newqueue;
    21         this.head = 0;
    22         this.tail = size;
    23     }
    24 
    25     @SuppressWarnings("unchecked")
    26     private T[] newArray(int size) {
    27         return (T[]) new Object[size];
    28     }
    29 
    30     public boolean add(T o) {
    31         queue[tail] = o;
    32         int newtail = (tail + 1) % capacity;
    33         if (newtail == head)
    34             throw new IndexOutOfBoundsException("Queue full");
    35         tail = newtail;
    36         return true; // we did add something
    37     }
    38 
    39     public T remove(int i) {
    40         if (i != 0)
    41             throw new IllegalArgumentException("Can only remove head of queue");
    42         if (head == tail)
    43             throw new IndexOutOfBoundsException("Queue empty");
    44         T removed = queue[head];
    45         queue[head] = null;
    46         head = (head + 1) % capacity;
    47         return removed;
    48     }
    49 
    50     public T get(int i) {
    51         int size = size();
    52         if (i < 0 || i >= size) {
    53             final String msg = "Index " + i + ", queue size " + size;
    54             throw new IndexOutOfBoundsException(msg);
    55         }
    56         int index = (head + i) % capacity;
    57         return queue[index];
    58     }
    59 
    60     public int size() {
    61         // Can't use % here because it's not mod: -3 % 2 is -1, not +1.
    62         int diff = tail - head;
    63         if (diff < 0)
    64             diff += capacity;
    65         return diff;
    66     }
    67 
    68     private int capacity;
    69     private T[] queue;
    70     private int head;
    71     private int tail;
    72 }

size() 计算：

初始化capacity的设定

判满条件：

tail + 1 == head,(注意：tail表示当前空位，tail + 1当前空位再往后一个，就是整个capacity不填满的)

head > tail 的时候，

转载于:https://www.cnblogs.com/mysqlstudygroup/p/10952377.html