数据结构——队列

一、队列的顺序存储结构实现

public class Queue<E> { private Object[] data; // 默认容量 private int maxCapacity = 10; // 队头 private int font; // 队尾 private int rear; public Queue(int capacity) { if (capacity >= 0) { maxCapacity = capacity; data = new Object[maxCapacity]; font = 0; rear = 0; } else { throw new IllegalArgumentException("初始化大小不能小于0：" + capacity); } } // 入队 public boolean add(E e) { if (rear == maxCapacity) { throw new RuntimeException("队列已满，无法插入新的元素！"); } else { data[rear] = e; rear++; return true; } } // 出队 public E poll() { if (font == rear) { throw new RuntimeException("空队列异常！"); } else { E value = (E) data[font]; data[font] = null; font++; return value; } } // 返回队头元素 public E peek() { if (font == rear) { throw new RuntimeException("空队列异常！"); } else { return (E) data[font]; } } // 队列长度 public int length() { return rear - font; } // 队满 public boolean full() { return rear == maxCapacity; } // 队空 public boolean empty() { return font == rear; } // 清空队列 public void clear() { Arrays.fill(data, font, rear, null); font = 0; rear = 0; }

二、循环队列

public class LoopQueue<E> { private Object[] data; private int maxCapacity = 10; // 队头 private int font; // 队尾 private int rear; // 计数 private int count; public LoopQueue(int size) { if (size >= 0) { maxCapacity = size; data = new Object[maxCapacity]; font = 0; rear = 0; count = 0; } else { throw new RuntimeException("初始化大小不能小于0：" + size); } } public boolean add(E e) { if (count == maxCapacity) { throw new RuntimeException("队列已满，无法插入新的元素！"); } else { data[rear] = e; rear = (rear + 1) % maxCapacity; count++; return true; } } // 出队 public E poll() { if (font == rear) { throw new RuntimeException("空队列异常！"); } else { E value = (E) data[font]; data[font] = null; font = (font + 1) % maxCapacity; count++; return value; } } // 返回队头元素 public E peek() { if (font == rear) { throw new RuntimeException("空队列异常！"); } else { return (E) data[font]; } } // 队列长度 public int size() { return count; } // 队满 public boolean full() { return count == maxCapacity; } // 队空 public boolean empty() { return count == 0; } // 清空队列 public void clear() { Arrays.fill(data, font, rear, null); font = 0; rear = 0; count = 0; } }

三、以链表结构的形式实现

public class LinkedQueue<E> { private static class Node<E> { private Node<E> next; private E value; public Node(E value, Node<E> next) { this.next = next; this.value = value; } } private Node<E> font; private Node<E> rear; private int count; public LinkedQueue() { font = null; rear = null; } // 入队 public boolean add(E e) { if (count == 0) { font = new Node<E>(e, null); rear = font; } else { Node<E> newNode = new Node<E>(e, null); rear.next = newNode; rear = newNode; } count++; return true; } // 出队 public E poll() { if (count == 0) { throw new RuntimeException("空队列异常！"); } E value = font.value; font = null; count--; return value; } // 返回队头元素 public E peek() { if (count == 0) { throw new RuntimeException("空队列异常！"); } else { return font.value; } } public int size() { return count; } // 队空 public boolean empty() { return count == 0; }

四、总结

      队列顺序存储结构的不足:假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。

对于循环队列与链队列的比较，可以从两方面来考虑：       从时间上，其实它们的基本操作都是常数时间，即都为0(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。       对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

     总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。       用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据，可以有效的利用资源。但是用循环队列有个小麻烦，不好判断数列是为空还是为满；       链队列就不存在上面的问题。“循环队列”最大优点就是节省空间和少分配空间，而链队列多了一点点地址存储开销。