博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
[数据结构] 队列
阅读量：6831 次
发布时间：2019-06-26

本文共 14398 字，大约阅读时间需要 47 分钟。

队列

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

队列中没有元素时，称为空队列。在队列这种中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。

队列空的条件：front=rear

队列满的条件： rear = MAXSIZE

顺序队列

　　建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置．

　　这里写图片描述

顺序队列中的溢出现象：

  • 下溢：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。　

  • 真上溢：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。　

  • 假上溢：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。

java中Queue

　　Queue继承于Collection，除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。

　　这里写图片描述

  • add()和offer()都是将指定的元素插入队列 

    add() 在成功时返回 true，如果当前没有可用的空间，则抛出 　　IllegalStateException。 
    offer()当使用有容量限制的队列时,无法插入元素，而只是抛出一个异常。

  • element() 和 peek() 返回但不移除队列的头，如果队列为空，peek()返回 null，element()抛出异常。

  • remove() 和 poll() 方法可移除和返回队列的头，它们仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。

一般使用：

public class TestQueue  {
          /**      * @param args      * @author JavaAlpha      * Info 测试队列      */      public static void main(String[] args)      {          Queue
    
      queue = new LinkedList
     
      ();          queue.offer("1");//插入元素          queue.offer("2");          queue.offer("3");          //打印元素个数          System.out.println("queue.size()"+queue.size());          //遍历打印所有的元素（按插入顺序）        for (String string : queue)          {              System.out.println(string);          }      }  }

结果：

queue.size()3  1  2  3

　　JDK中包含了 双向顺序队列ArrayDeque、双向链式队列LinkedList和PriorityQueue优先队列。 

ArrayDeque包括顺序栈和顺序队列，LinkedList包含链式栈和链式队列。ArrayDeque和LinkedList都是线程不安全的。

顺序队列的实现：

package lang;import java.io.Serializable;import java.util.Arrays;public class ArrayQueue
    
      implements Serializable{
    private static final long serialVersionUID = 7333344126529379197L;  private int DEFAULT_SIZE = 10;  private int capacity;//保存数组的长度  private Object[] elementData;//定义一个数组用于保存顺序队列的元素  private int front = 0;//队头  private int rear = 0;//队尾  //以默认数组长度创建空顺序队列  public ArrayQueue() {    capacity = DEFAULT_SIZE;    elementData = new Object[capacity];  }  //以一个初始化元素来创建顺序队列  public ArrayQueue(T element) {    this();    elementData[0] = element;    rear++;  }  public ArrayQueue(int initSize) {    elementData = new Object[initSize];  }  /**   * 以指定长度的数组来创建顺序队列   * @param element 指定顺序队列中第一个元素   * @param initSize 指定顺序队列底层数组的长度   */  public ArrayQueue(T element, int initSize) {    this.capacity = initSize;    elementData = new Object[capacity];    elementData[0] = element;    rear++;  }  /**   * @Title: size        * @Description: 获取顺序队列的大小       * @return   */  public int size() {    return rear - front;  }  /**   * @Title: offer        * @Description: 入队       * @param element   */  public void offer(T element) {    ensureCapacity(rear + 1);    elementData[rear++] = element;  }  private void ensureCapacity(int minCapacity) {    //如果数组的原有长度小于目前所需的长度    int oldCapacity = elementData.length;    if (minCapacity > oldCapacity) {      int newCapacity = (oldCapacity * 3) / 2 + 1;      if (newCapacity < minCapacity)        newCapacity = minCapacity;      // minCapacity is usually close to size, so this is a win:      elementData = Arrays.copyOf(elementData, newCapacity);    }  }  /**   * @Title: poll        * @Description: 出队       * @return   */  public T poll() {    if (isEmpty()) {      throw new IndexOutOfBoundsException("空队列异常");    }    //保留队列的front端的元素的值    T oldValue = (T) elementData[front];    //释放队列的front端的元素    elementData[front++] = null;    return oldValue;  }  /**   * @Title: peek        * @Description: 返回队列顶元素，但不删除队列顶元素       * @return   */  public T peek() {    if (isEmpty()) {      throw new IndexOutOfBoundsException("空队列异常");    }    return (T) elementData[front];  }  /**   * @Title: isEmpty        * @Description: 判断顺序队列是否为空队列       * @return   */  public boolean isEmpty() {    return rear == front;  }  /**   * @Title: clear        * @Description: 清空顺序队列   */  public void clear() {    //将底层数组所有元素赋为null    Arrays.fill(elementData, null);    front = 0;    rear = 0;  }  public String toString() {    if (isEmpty()) {      return "[]";    } else {      StringBuilder sb = new StringBuilder("[");      for (int i = front; i < rear; i++) {        sb.append(elementData[i].toString() + ", ");      }      int len = sb.length();      return sb.delete(len - 2, len).append("]").toString();    }  }}

java链式队列的实现

package lang;import java.io.Serializable;public class LinkQueue
    
      implements Serializable{
      private static final long serialVersionUID = -6726728595616312615L;  //定义一个内部类Node，Node实例代表链队列的节点。  private class Node {
        private T data;//保存节点的数据    private Node next;//指向下个节点的引用    //无参数的构造器    public Node() {    }    //初始化全部属性的构造器    public Node(T data, Node next) {      this.data = data;      this.next = next;    }  }  private Node front;//保存该链队列的头节点  private Node rear;//保存该链队列的尾节点  private int size;//保存该链队列中已包含的节点数  /**   * 
     
Title: LinkQueue 
        * 
     
Description: 创建空链队列 
    */  public LinkQueue() {    //空链队列，front和rear都是null    front = null;    rear = null;  }  /**   * 
     
Title: LinkQueue 
       * 
     
Description: 以指定数据元素来创建链队列，该链队列只有一个元素
    */  public LinkQueue(T element) {    front = new Node(element, null);    //只有一个节点，front、rear都指向该节点    rear = front;    size++;  }  /**   * @Title: size        * @Description: 获取顺序队列的大小       * @return   */  public int size() {    return size;  }  /**   * @Title: offer        * @Description: 入队       * @param element   */  public void offer(T element) {    //如果该链队列还是空链队列    if (front == null) {      front = new Node(element, null);           rear = front;//只有一个节点，front、rear都指向该节点    } else {           Node newNode = new Node(element, null);//创建新节点           rear.next = newNode;//让尾节点的next指向新增的节点           rear = newNode;//以新节点作为新的尾节点    }    size++;  }  /**   * @Title: poll        * @Description: 出队       * @return   */  public T poll() {    Node oldFront = front;    front = front.next;    oldFront.next = null;    size--;    return oldFront.data;  }  /**   * @Title: peek        * @Description: 返回队列顶元素，但不删除队列顶元素       * @return   */  public T peek() {    return rear.data;  }  /**   * @Title: isEmpty        * @Description: 判断顺序队列是否为空队列       * @return   */  public boolean isEmpty() {    return size == 0;  }  /**   * @Title: clear        * @Description: 清空顺序队列   */  public void clear() {    //将front、rear两个节点赋为null    front = null;    rear = null;    size = 0;  }  public String toString() {    //链队列为空链队列时    if (isEmpty()) {      return "[]";    } else {      StringBuilder sb = new StringBuilder("[");      for (Node current = front; current != null; current = current.next) {        sb.append(current.data.toString() + ", ");      }      int len = sb.length();      return sb.delete(len - 2, len).append("]").toString();    }  }  public static void main(String[] args) {    LinkQueue
     
       queue = new LinkQueue
      
       ("aaaa");    //添加两个元素    queue.offer("bbbb");    queue.offer("cccc");    System.out.println(queue);    //删除一个元素后    queue.poll();    System.out.println("删除一个元素后的队列：" + queue);    //再次添加一个元素    queue.offer("dddd");    System.out.println("再次添加元素后的队列：" + queue);    //删除一个元素后，队列可以再多加一个元素    queue.poll();    //再次加入一个元素    queue.offer("eeee");    System.out.println(queue);  }}

循环队列

　　为充分利用向量空间，克服”假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

循环队列的队空与队满的条件

初始化建空队时， front=rear=0 

当队空时：front=rear 
当队满时：front=rear 亦成立 
因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题：　

1、另设一个标志位以区别队列是空还是满。　2、少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：

队空时： front=rear 

队满时： (rear+1)%maxsize=front 
front指向队首元素，rear指向队尾元素的下一个元素（始终指向空）。　

　循环队列的Java实现:

package lang;import java.io.Serializable;import java.util.Arrays;public class LoopQueue
    
      implements Serializable{  private static final long serialVersionUID = -3670496550272478781L;  private int DEFAULT_SIZE = 10;  private int capacity;//保存数组的长度  private Object[] elementData;//定义一个数组用于保存循环队列的元素  private int front = 0;//队头  private int rear = 0;//队尾  //以默认数组长度创建空循环队列  public LoopQueue() {    capacity = DEFAULT_SIZE;    elementData = new Object[capacity];  }  //以一个初始化元素来创建循环队列  public LoopQueue(T element) {    this();    elementData[0] = element;    rear++;  }  /**   * 以指定长度的数组来创建循环队列   * @param element 指定循环队列中第一个元素   * @param initSize 指定循环队列底层数组的长度   */  public LoopQueue(T element, int initSize) {    this.capacity = initSize;    elementData = new Object[capacity];    elementData[0] = element;    rear++;  }  //获取循环队列的大小  public int size() {    if (isEmpty()) {      return 0;    }    return rear > front ? rear - front : capacity - (front - rear);  }  //插入队列  public void add(T element) {    if (rear == front && elementData[front] != null) {      throw new IndexOutOfBoundsException("队列已满的异常");    }    elementData[rear++] = element;    //如果rear已经到头，那就转头    rear = rear == capacity ? 0 : rear;  }  //移除队列  public T remove() {    if (isEmpty()) {      throw new IndexOutOfBoundsException("空队列异常");    }    //保留队列的rear端的元素的值    T oldValue = (T) elementData[front];    //释放队列的rear端的元素    elementData[front++] = null;    //如果front已经到头，那就转头    front = front == capacity ? 0 : front;    return oldValue;  }  //返回队列顶元素，但不删除队列顶元素  public T element() {    if (isEmpty()) {      throw new IndexOutOfBoundsException("空队列异常");    }    return (T) elementData[front];  }  //判断循环队列是否为空队列  public boolean isEmpty() {    //rear==front且rear处的元素为null    return rear == front && elementData[rear] == null;  }  //清空循环队列  public void clear() {    //将底层数组所有元素赋为null    Arrays.fill(elementData, null);    front = 0;    rear = 0;  }  public String toString() {    if (isEmpty()) {      return "[]";    } else {      //如果front < rear，有效元素就是front到rear之间的元素      if (front < rear) {        StringBuilder sb = new StringBuilder("[");        for (int i = front; i < rear; i++) {          sb.append(elementData[i].toString() + ", ");        }        int len = sb.length();        return sb.delete(len - 2, len).append("]").toString();      }      //如果front >= rear，有效元素为front->capacity之间、0->front之间的      else {        StringBuilder sb = new StringBuilder("[");        for (int i = front; i < capacity; i++) {          sb.append(elementData[i].toString() + ", ");        }        for (int i = 0; i < rear; i++) {          sb.append(elementData[i].toString() + ", ");        }        int len = sb.length();        return sb.delete(len - 2, len).append("]").toString();      }    }  }  public static void main(String[] args) {    LoopQueue
     
       queue = new LoopQueue
      
       ("aaaa", 3);    //添加两个元素    queue.add("bbbb");    queue.add("cccc");    //此时队列已满    System.out.println(queue);    //删除一个元素后，队列可以再多加一个元素    queue.remove();    System.out.println("删除一个元素后的队列：" + queue);    //再次添加一个元素，此时队列又满    queue.add("dddd");    System.out.println(queue);    System.out.println("队列满时的长度：" + queue.size());    //删除一个元素后，队列可以再多加一个元素    queue.remove();    //再次加入一个元素，此时队列又满    queue.add("eeee");    System.out.println(queue);  }}

阻塞队列（BlockingQueue）

几种主要的阻塞队列

　　自从Java 1.5之后，在java.util.concurrent包下提供了若干个阻塞队列，主要有以下几个：

　　ArrayBlockingQueue：基于数组实现的一个阻塞队列，在创建ArrayBlockingQueue对象时必须制定容量大小。并且可以指定公平性与非公平性，默认情况下为非公平的，即不保证等待时间最长的队列最优先能够访问队列。

　　LinkedBlockingQueue：基于链表实现的一个阻塞队列，在创建LinkedBlockingQueue对象时如果不指定容量大小，则默认大小为Integer.MAX_VALUE。

　　PriorityBlockingQueue：以上2种队列都是先进先出队列，而PriorityBlockingQueue却不是，它会按照元素的优先级对元素进行排序，按照优先级顺序出队，每次出队的元素都是优先级最高的元素。注意，此阻塞队列为无界阻塞队列，即容量没有上限（通过源码就可以知道，它没有容器满的信号标志），前面2种都是有界队列。

　　　DelayQueue：基于PriorityQueue，一种延时阻塞队列，DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取到该元素。DelayQueue也是一个无界队列，因此往队列中插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。

阻塞队列方法对比

　1.　非阻塞队列中的几个主要方法：

　　add(E e):将元素e插入到队列末尾，如果插入成功，则返回true；如果插入失败（即队列已满），则会抛出异常；

　　remove()：移除队首元素，若移除成功，则返回true；如果移除失败（队列为空），则会抛出异常；

　　offer(E e)：将元素e插入到队列末尾，如果插入成功，则返回true；如果插入失败（即队列已满），则返回false；

　　poll()：移除并获取队首元素，若成功，则返回队首元素；否则返回null；

　　peek()：获取队首元素，若成功，则返回队首元素；否则返回null

　　对于非阻塞队列，一般情况下建议使用offer、poll和peek三个方法，不建议使用add和remove方法。因为使用offer、poll和peek三个方法可以通过返回值判断操作成功与否，而使用add和remove方法却不能达到这样的效果。注意，非阻塞队列中的方法都没有进行同步措施。

2.　阻塞队列中的几个主要方法：

　　阻塞队列包括了非阻塞队列中的大部分方法，上面列举的5个方法在阻塞队列中都存在，但是要注意这5个方法在阻塞队列中都进行了同步措施。除此之外，阻塞队列提供了另外4个非常有用的方法：

　　put(E e)

　　take()

　　offer(E e,long timeout, TimeUnit unit)

　　poll(long timeout, TimeUnit unit)

　　put方法用来向队尾存入元素，如果队列满，则等待；

　　take方法用来从队首取元素，如果队列为空，则等待；

　　offer方法用来向队尾存入元素，如果队列满，则等待一定的时间，当时间期限达到时，如果还没有插入成功，则返回false；否则返回true；

　　poll方法用来从队首取元素，如果队列空，则等待一定的时间，当时间期限达到时，如果取到，则返回null；否则返回取得的元素；　

阻塞队列内部是通过Object.wait()、Object.notify()实现的，下面来看 

使用阻塞队列实现的生产者-消费者的例子：

public class Test {
        private static Integer count = 0;    final BlockingQueue
    
      bq = new ArrayBlockingQueue
     
      (5);//容量为5的阻塞队列  public static void main(String[] args)  {        Test t = new Test();        new Thread(t.new Producer()).start();        new Thread(t.new Consumer()).start();        new Thread(t.new Consumer()).start();        new Thread(t.new Producer()).start();    }    class Producer implements Runnable {
            @Override        public void run() {            for (int i = 0; i < 5; i++) {                try {                    Thread.sleep(1000);                } catch (Exception e) {                    e.printStackTrace();                }                try {                    bq.put(1);                    count++;                    System.out.println(Thread.currentThread().getName() + "produce:: " + count);                } catch (InterruptedException e) {                    // TODO Auto-generated catch block                    e.printStackTrace();                }            }        }    }    class Consumer implements Runnable {
            @Override        public void run() {            for (int i = 0; i < 5; i++) {                try {                    Thread.sleep(1000);                } catch (InterruptedException e1) {                    e1.printStackTrace();                }                try {                    bq.take();                    count--;                    System.out.println(Thread.currentThread().getName()+ "consume:: " + count);                } catch (Exception e) {                    // TODO: handle exception                    e.printStackTrace();                }            }        }    }}

参考：

　　 

 

原文地址：http://blog.csdn.net/amazing7/article/details/51362782

你可能感兴趣的文章
linux JVM内存分析（二） 实战JVM调优
查看>>
（三）spring cloud微服务分布式云架构 - Spring Cloud集成项目简介
查看>>
scrapy爬虫时HTTPConnectionPool（host:XX）Max retries exceeded with url 解决方法
查看>>
随机漫步
查看>>
解决vue在ie中不能使用的问题
查看>>
如何使用 CSS Grid 快速而又灵活的布局
查看>>
scrolltop的兼容问题
查看>>
磁盘格式化,磁盘挂载,手动增加swap空间
查看>>
2.23/2.24/2.25 find命令
查看>>
4.26 Alias 4.27-29 php编译安装 4.30 编译安装Nginx
查看>>
python函数相关
查看>>
芝麻HTTP：Python爬虫入门之Urllib库的高级用法
查看>>
nginx.conf配置文件的参数详解
查看>>
航空订票系统
查看>>
Zabbix 通过 SNMP 监控设备
查看>>
CRM和ERP的Sales Organization的映射关系
查看>>
Ubuntu12.04不能调节屏幕亮度的办法
查看>>
【Centos】在nginx服务器中配置php和mysql
查看>>
ETCgame再升级，焕然一新的界面，极尽舒适的体验！
查看>>
基本类型优于封装类型（49）
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-31 15:57:41   当前IP: 18.220.222.188   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我