Java数据结构-线性表之队列

左手的ㄟ右手 2022-08-02 13:34 286阅读 0赞

队列(Queue)的定义：只允许在一端进行插入另一端进行删除操作的线性表。允许插入的一端称为队尾(rear) ，允许删除的一端称为队头(front)。 具有“先进先出”特点。

队列也是线性表，所以也存在顺序结构和链式结构。

**顺序队列：**

对于队列，入队操作的解释为：  
(是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为0(1)。)

1.  判断队列是否已满；
2.  如果没满则先给队尾元素赋值;
3.  然后将队尾指针后移一位（对队尾指针赋值，Q->rear = Q->rear+1 )。

出队操作解释为：  
(队列中的所有元素都得向前移动，以保证队列的队头（也就是下标为0的位置）不为空，此时的时间复杂度为0(n)。)

1.  判断队列是否为空；
2.  若不为空则将对首元素取出用来返回；
3.  然后将对首指针后移一位（对队首指针赋值，Q->front = Q->front+1 )。
4.  队列是否为空判断：队首指针和队尾指针进行判断是否相等。

队列的实际长度：队尾指针-对首指针；也可以通过设定一个变量来进行存储。

下面是我的顺序队列的Java实现：

package com.phn.queue;
    /**
     * @author 潘海南
     * @Email 1016593477@qq.com
     * @TODO 顺序队列
     * @date 2015年7月20日
     */
    public class FOArrayQueue<E> {
        //默认队列容量
        private static final int DEFUALT_CAPACITY = 100;
        //队列存储数据元素的数组
        private Object[] data = null;
        //队列的实际大小
        private int size;
        //队列的对首索引
        private int front;
        //队列的队尾索引
        private int rear;
        //队列的实际容量
        private int capacity;
        /**
         * @TODO 无参构造函数，初始化队列
         */
        public FOArrayQueue() {
            this(DEFUALT_CAPACITY);
        }
        /**
         * @param initialCapacity 队列初始化容量
         */
        public FOArrayQueue(int initialCapacity) {
            this.data = new Object[initialCapacity];
            this.front = 0;
            this.rear = 0;
            this.size = 0;
            this.capacity = initialCapacity;
        }
        /**
         * @TODO 队列入队操作
         * @param e 需要入队的数据元素
         * @return true
         */
        public boolean enQueue(E e){
            if(this.isFull()){
                throw new RuntimeException("队列已满！最大容量="+this.capacity);
            }
            this.data[this.rear] = e;
    //      this.rear = (this.rear+1)%(this.capacity);
            this.rear = this.rear+1;
            this.size++;
            return true;
        }
        /**
         * @TODO 队列的出队操作
         * @return e 位于对首的数据元素
         */
        public E deQueue(){
            if(this.isEmpty()){
                throw new RuntimeException("队列为空！");
            }
            E e = (E)this.data[this.front];
    //      this.front = (this.front+1)%(this.capacity);
            this.front = this.front+1;
            this.size--;
            return e;
        }
        /**
         * @TODO 判断队列是否为空
         * @return true空 or false不为空
         */
        public boolean isEmpty(){
            if(this.front==this.size){
                return true;
            }
            return false;
        }
        /**
         * @TODO 判断队列是否已满
         * @return true满 or false未满
         */
        public boolean isFull(){
            //这里不能用size来进行判断，用size会出现假溢出的情况
            if(this.rear==this.capacity-1){
                return true;
            }
            return false;
        }
        /**
         * @TODO 获取队列的长度
         * @return size
         */
        public int size(){
            return this.size;
        }
        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer("[");
            if(this.data[this.front]!=null){
                sb.append(this.data[this.front]);
                for (int i = this.front+1; i < this.rear; i++) {
                    sb.append(", "+this.data[i]);
                }
            }
            sb.append("]");
            return sb.toString();
        }
    }

下面是我的测试代码：

public static void main(String[] args) {
        FOArrayQueue<String> foaq = new FOArrayQueue<String>();
        for (int i = 1; i <= 6; i++) {
            foaq.enQueue("元素"+i);
        }
        System.out.println(foaq);
        System.out.println(foaq.size());
        System.out.println(foaq.deQueue());;
        System.out.println(foaq);
        System.out.println(foaq.size());
    }

测试截图：  
![1.png][]

由于队列的入队和出队操作的结果导致队列容易出现“假溢出”，于是乎出现了循环队列。

循环队列需要注意的地方如下：

*  执行入队操作后，队尾指针的变化：Q->rear = (Q->rear+1)% capacity。
 *  执行出队操作后，对首指针的变化：Q->front= (Q->front+1)% capacity。
 *  判断是否为空的情况：Q->front=Q->rear。
 *  判断队列是否为满的情况，需要放弃队列一个位置来区分开来队列是否为空是否为满，这样判断条件为：Q->front= (Q->rear + 1)% capacity。
 *  队列实际长度：（队尾指针-对首指针+数组长度）% 数组长度；或者可以通过设定一个变量来进行存储；或者都通过Q->front=Q->rear外加一个flag变量进行判断。

好了，循环队列也就介绍这些。

**链队列：**  
定义：队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。  
  为了方便操作，将队头指针指向链队列的头结点，而队尾指针指向终端结点。  
  当队列为空时，front和rear都指向头结点。

正如链队就类似于单链表，这里链队的入队、出队、判断为空等操作也基本类似，这里就不描述了，详情请参考之前的单链表。

其实看了之前的再看这里其实很容易的，不懂的话还可以参考这个网址：[http://www.nowamagic.net/librarys/veda/detail/2357][http_www.nowamagic.net_librarys_veda_detail_2357]

循环队列和链队列的比较。

1.  时间上：它们的基本操作都是常数时间O(1)，这里还有点细微的差别（循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异）。
2.  空间上：循环队列的长度固定，因此有了空间浪费的问题；而链队列不存在这个问题，但是每个节点需要一个指针域，这是需要消耗一定的空间。相对来说，链队列更加灵活。

总结：  
  在确定队列长度最大值的情况，建议使用循环队列；否则请使用链队列。“循环队列”最大优点就是节省空间和少分配空间，而链队列多了一点点地址存储开销。

[1.png]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/队列1.png
[http_www.nowamagic.net_librarys_veda_detail_2357]: http://www.nowamagic.net/librarys/veda/detail/2357