数据结构队列Queue（3）

素颜马尾好姑娘i 2022-11-24 14:17 164阅读 0赞

### 队列 ###

#### 1、队列特点 ####

队列简称为队。也是一种受限的线性表，只允许在线性表的一端进行插入，而在表的另一端进行删除。（遵循：先进先出FIFO）

*  插入数据的一端为称为队尾（rear），删除数据的一端称为队首（front）

队列抽象对象类型定义：

数据对象：D=\{a0,a1…an,ai\}

数据关系R：\{<ai,ai+1>\}

数据操作：

*  getSize();返回元素个数
 *  isEmpty();//判断是否为空
 *  enQueue(e)；入队
 *  deQueue()；出队

#### 2、队列的顺序存储实现 ####

使用数组实现队列存储大致步骤：

*  1）需要定义一个数组
 *  2）给定数组一个大小
 *  3）队尾rear、队首front
 *  4）然后初始化数组
 *  5）编写实现方法

代码如下

public MyArrayQueue{ 
      private Object[] elements;//存储队列元素
      //初始化容量
      private static final int DEFAULT_CAPACITY = 8;
      private int front;//队首
      private int rear;//队尾
      private int size;//队列个数
      //初始化
      public MyArrayQueue(){ 
        elements = new Object[DEFAULT_CAPACITY];
      }
      //或者可以使用有参构造
      public MyArrayQueue(int initialCapacity){ 
        elements = new Object[initialCapacity];
      }
      //获取队元素个数
      public int getSize(){ 
        return size;
      }
      //判断队列是否为空
      public boolean isEmpty(){ 
        return size == 0;
      }
      //入队
      public void enQueue(Object e){ 
        //判断队列如果满了，需进行扩容
        if(size >= elements.length){ 
          expandQueue();//扩容核心方法
        }
        //如果没有满，则将需要添加元素加到队列的尾列rear
        elements[rear] = e;
        //rear指针后移动
        rear = (rear+1) % elements.length;//rear指针后移
        size++;
      }
      //出队
      public Object deQueue(){ 
        if(size <= 0){ 
          throw new RuntimeException("队列为空");
        }
        //队列不为空，把front指向的元素返回
        Object old = elements.length;
        //front后移
        front = (front + 1) % elements.length;
        size--;
      }
      //扩容方法
      private void expandQueue(){ 
        Object[] newElements = new Object[elements.length * 2];//以两倍扩容
        //然后把原来数组内容复制到新的数组中
        for(int i = 0; i < size; i++){ 
          newElements[i] = elements[fron];//新数组的0位置=原来数组的队首
          front = (font + 1) % elements.length;
        }
        //让旧的数组指向新的数组
        elements = newElements;
        fron = 0;
        rear = size;
      }
    }

#### 3、队列的链式存储实现 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C0F2Ss6y-1596697213039)(/Users/dimitri/Library/Application Support/typora-user-images/image-20200731144254820.png)\]

使用链表来实现队列的介绍

*  1）定义一个节点（e和next）
 *  2）定义队尾和队首变量及队元素个数
 *  3）编写核心方法
 *  4）入队方法：
    
     *  判断如果是第一个元素添加进行的话，则将rear&front指向新的节点
     *  如果不是第一个添加进来，则将新节点添加到链表的尾部即可（rear.next = newNodex&rear=newNode）

完整代码如下

public class MyLinkedQueue { 
        private Node front;//队首
        private Node rear;//队尾
        private int size;//元素个数
      //返回元素个数
        public int getSize() { 
            return size;
        }
        //判断队列是否为空
        public boolean isEmpty(){ 
            return size == 0;
        }
      //入队
      public void enQueue(Object e){ 
        Node newNode = new Node(e,null);
        if(rear == null){ 
          //添加进来，如果rear为空说明添加是第一个元素
          rear = newNode;
          front = newNode;
        } else { 
          //如果不是第一个添加那么把节点拉链到队列的尾部
          rear.next = newNode;
          rear = newNode;
        }
        size++;
      }
      //出队
      Node newNode = new Node(e,null);
    //通过内部类表示单链表的节点
        private class Node{ 
            Object elements;
            Node next;
            public Node(Object elements, Node next) { 
                this.elements = elements;
                this.next = next;
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]: /images/20221124/c25efb33b9684119a3ce2dbf4ceb6f72.png