【数据结构 四】---队列

下午的时候全面总结了栈的两种实现方式和基本原理，然后晚上来做以下关于队列的基本总结，今天的工作就算结束了。代码实现是我用java完成的，实现过程中参照了以下两篇博客http://blog.csdn.net/wuwenxiang91322/article/details/12259099和
http://www.cnblogs.com/CherishFX/p/4608880.html在这里注明出处，时间是2017.8.2晚上。

队列简介

队列的特点

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾，每次离开的成员总是队列头上的（不允许中途离队）。

队列的相关概念

1，队头下标（Front）
2，队尾下标（Rear）

队列的基本运算

1，判断队列是否为空（isEmpty）：队空的条件是front=rear
2, 返回队首元素，但不删除（peek）
3，入队（add）
4，出队（del）
5，队列长度（length）

队列的实现方式

队列接口实现队列

package queue;

import java.util.LinkedList;

/*add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常 *remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常 *element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常 *offer 添加一个元素并返回true 如果队列已满，则返回false *poll 移除并返问队列头部的元素 如果队列为空，则返回null *peek 返回队列头部的元素 如果队列为空，则返回null *put 添加一个元素 如果队列满，则阻塞 *take 移除并返回队列头部的元素 如果队列为空，则阻塞 */
public class Queue {
    public static void main(String[] args) {
        java.util.Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println("队列大小" + queue.size());
        System.out.println("队头元素" + queue.peek());
        System.out.println("移除并返回队头元素" + queue.poll());
        System.out.println("队头元素" + queue.peek());
        System.out.println("打印队列" + queue);
    }
}

测试结果

队列大小4
队头元素1
移除并返回队头元素1
队头元素2
打印队列[2, 3, 4]

队列的顺序数组实现（数组）

队列的数组实现

package queue;

public class MyQueueArray<T> {
    public int initalSize; // 队列的初始化容量
    public int curSize; // 队列的当前大小
    public T[] array; // 用于存放数据的数组
    public int front; // 队头下标
    public int rear; // 队尾下标

    public MyQueueArray() {
        this(5);
    }

    @SuppressWarnings("unchecked")
    public MyQueueArray(int Size) {
        if (Size >= 0) {
            initalSize = Size;
            array = (T[]) new Object[Size];
            front = 0;
            rear = 0;
            curSize = 0;
        }
    } // 两个构造函数，用于初始化队列
        // 判断队列是否为空

    public boolean isEmpty() {
        return rear == front;
    }

    // 入队列:rear向后移动
    public void add(T data) {
        if (curSize == initalSize) {
            throw new RuntimeException("队列已满，无法插入新的元素！");
        }
        array[rear] = data;
        rear++;
        curSize++;

    }

    // 返回队头元素
    public T peek() {
        if (isEmpty()) {
            System.out.println("队列为空");
        }
        return array[front];
    }

    // 出队列:front向后移动
    public T del() {
        if (isEmpty()) {
            System.out.println("队列为空");
        }
        T deldata = array[front];
        array[front++] = null; //
        curSize--;
        return deldata;
    }

    // 队列长度
    public int length() {
        return rear - front; // 理论上应该与curSize大小相同，为什么不是rear-front+1,因为每次存入一个元素后，rear移动到了下一个没有元素的位置了。
    }

}

测试代码

package queue;

public class QueneArrayTest {

    public static void main(String[] args) {
          MyQueueArray<Integer> t = new MyQueueArray<Integer>();
          t.add(5);
          t.add(4);
          t.add(3);
          t.add(2);
          t.add(1);
          System.out.println("队列的长度是"+ t.curSize);
          System.out.println("队列的长度是"+ t.length());
          System.out.println("队头元素是"+ t.peek());
          t.del();
          System.out.println("队列的长度是"+ t.length());
          System.out.println("队头元素是"+ t.peek());
          t.add(0);
          System.out.println("队列的长度是"+ t.length());
          t.add(1);
          System.out.println("队列的长度是"+ t.length());


    }

}

测试结果

队列的长度是5
队列的长度是5
队头元素是5
队列的长度是4
队头元素是4
报错，数组溢出  // 虽然之前的队头元素被删除了，但是队列的总空间还是被占用了，再往后加进来就会报错。

循环队列的数组实现（数组）

循环队列的实现方式其实也就是顺序实现方式的防溢出形式。

由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素，它们的初值在队列初始化时均应置为0。

入队时：将新元素插入rear所指的位置的后一位。
出队时：删去front所指的元素，然后将front加1并返回被删元素。

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

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

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

循环链表实现队列

package queue;

public class LoopQueue<T> {

    public int initalSize; // 队列的初始化容量
    public int curSize; // 队列的当前大小
    public T[] array; // 用于存放数据的数组
    public int front; // 队头下标
    public int rear; // 队尾下标

    public LoopQueue() {
        this(5);
    }

    @SuppressWarnings("unchecked")
    public LoopQueue(int Size) {
        if (Size >= 0) {
            initalSize = Size;
            array = (T[]) new Object[Size];
            front = 0;
            rear = 0;
            curSize = 0;
        }
    } // 两个构造函数，用于初始化队列

    // 判断队列是否为空
    public boolean isEmpty() {
        return curSize==0;
    }
    // 判断队列是否为满
    public boolean isFull() {
        if ((rear + 1) % initalSize == front)  //该条件可以判断队列是否已满
            return true;
        return false;
    }

    // 入队列:rear向后移动
    public void add(T data) {
        if (curSize == initalSize) {   //这里之所以可以用curSize判断是否为满，就是因为该队列是循环队列
            throw new RuntimeException("队列已满，无法插入新的元素！");
        }
        array[rear] = data;
        rear = (rear + 1) % initalSize;  //循环到下一个位置
        curSize++;

    }

    // 返回队头元素
    public T peek() {
        if (isEmpty()) {
            System.out.println("队列为空");
        }
        return array[front];
    }

    // 出队列:front向后移动
    public T del() {
        if (isEmpty()) {
            System.out.println("队列为空");
        }
        T deldata = array[front];
        front = (front+1)%initalSize;
        curSize--;
        return deldata;
    }


}

测试代码

package queue;

public class QueneLoopTest {

    public static void main(String[] args) {
          LoopQueue<Integer> t = new LoopQueue<Integer>();
          t.add(5);
          t.add(4);
          t.add(3);
          t.add(2);
          t.add(1);
          System.out.println("队列的长度是"+ t.curSize);
          System.out.println("队头元素是"+ t.peek());
          t.del();
          System.out.println("队头元素是"+ t.peek());
          t.add(0);
          System.out.println("队列的长度是"+ t.curSize);
          t.del();
          t.add(9);
          System.out.println("队列的长度是"+ t.curSize);


    }


}

测试结果

队列的长度是5
队列的长度是5
队头元素是5
队列的长度是4
队头元素是4    //这里可以看到，队列可以反复的增加和删除而没有影响。

链式队列的实现（单链表）

节点代码实现：

package queue;

public class Node<T> {
    public T val;
    public Node<T> next = null;

    public Node(T val, Node<T> next) {   //构造方法，创建一个新节点
        this.val = val;
        this.next = next;
    }

}

队列的链式结构实现

package queue;

public class MyQueneList<T> {
    public int curSize; // 队列的当前大小
    public Node<T> front; // 队头下标
    public Node<T> rear; // 队尾下标

    // 判断队列是否为空
    public boolean isEmpty() {
        return curSize == 0; // 注意这里一定不能用rear==font,因为链表而言，rear指向的节点是有元素的，
    }

    // 入队列:rear向后移动
    public void add(T data) {
        if (isEmpty()) {
            Node<T> head = new Node<T>(data, null);
            front = head;
            rear = head;
        } else {
            Node<T> newNode = new Node<T>(data, null);
            rear.next = newNode;
            rear = newNode;
        }
        curSize++;

    }

    // 返回队头元素
    public T peek() {
        if (isEmpty()) {
            System.out.println("队列为空");
        }
        return front.val;
    }

    // 出队列:front向后移动
    public T del() {
        if (isEmpty()) {
            System.out.println("队列为空");
        }
        Node<T> delNode = front;
        front = front.next;
        delNode.next = null; // 释放原队列头元素的next引用
        curSize--;
        return delNode.val;
    }

}

测试代码

package queue;

public class QueneListTest {

    public static void main(String[] args) {
        MyQueneList<Integer> t = new MyQueneList<Integer>();
        t.add(5);
        t.add(4);
        t.add(3);
        t.add(2);
        t.add(1);
        System.out.println("队列的长度是" + t.curSize);
        System.out.println("队头元素是" + t.peek());
        t.del();
        System.out.println("队头元素是" + t.peek());
        t.add(0);
        t.add(1);
        System.out.println("队列的长度是" + t.curSize);

    }

}

测试结果

队列的长度是5
队头元素是5
队头元素是4
队列的长度是6

linkedList实现队列

/** * 使用java.util.Queue接口,其底层关联到一个LinkedList（双端队列）实例. */
import java.util.LinkedList;
import java.util.Queue;

public class QueueList<E> {
    private Queue<E> queue = new LinkedList<E>();

    // 将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，
    //如果当前没有可用的空间，则抛出 IllegalStateException。
    public boolean add(E e){
        return queue.add(e);
    }

    //获取，但是不移除此队列的头。
    public E element(){
        return queue.element();
    }

    //将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，
    //此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。
    public boolean offer(E e){
        return queue.offer(e);
    }

    //获取但不移除此队列的头；如果此队列为空，则返回 null
    public E peek(){
        return queue.peek();
    }

    //获取并移除此队列的头，如果此队列为空，则返回 null
    public E poll(){
        return queue.poll();
    }

    //获取并移除此队列的头
    public E remove(){
        return queue.remove();
    }

    //判空
    public boolean empty() {
        return queue.isEmpty();
    }
}