数据结构与算法(五)什么是队列

Posted on | In

队列

队列的概述

队列是一种先进先出 (First 10 First Out) 的线性表,简称 FIFO。允许插入的一 端称为队尾,允许删除的一端称为队头

队列

队列的顺序存储

  • 顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标0的一端即是队头.所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度O(1)

  • 与栈不同的是,队列元素的出列是在队头,即下标为队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public class QueueTest1<E> {

    private  Object[] elementData;
    //默认队列容量为10
    private final int DEFAULT_CAPACITY = 3;
    //容量
    private int capacity;
    //头指针 总是指向出队的索引
    private int front = 0;
    //尾指针 总是下一个插入元素的索引
    private int  rear = 0;

    //初始化队列
    public  QueueTest1(){
        this.capacity = DEFAULT_CAPACITY;
        elementData = new  Object[capacity];
    }

    public  QueueTest1(int initialCapacity){
        this.capacity = initialCapacity;
        elementData = new  Object[capacity];
    }

    //队列长度
    public int length(){
        return rear - front;
    }
    //判是否为空
    public boolean isEmpty(){
        return rear == front;
    }

    /**
     * 入队：
     * 队尾插入元素
     * @param e
     */
    public void add(E e){
        //判断当前尾指针索引是否大于队列的容量 下标从0开始 所以减1
        if(rear>capacity-1){
            System.out.println("插入元素："+e+" 时队列已满 ");
        }
        elementData[rear++]=e;
    }

    /**
     * 出队：
     *  总是队头删除元素
     * @return
     */
    public E deQueue(){
        //获取头指针的元素
        E  e= (E) elementData[front];
        /**
         * 改变头指针的索引自增加+1
         * 并把之前头指针指向的元素赋值null 以便垃圾回收
         * front++ 先执行赋值null  下次再进入之前fornt就是1
         */
        elementData[front++] = null;
        return e;
    }

    public static void main(String[] args) {
        QueueTest1 q=new QueueTest1();
        q.add(1);
        q.add(2);
        q.add(3);

        System.out.println("size:"+q.length());
        System.out.println(q.deQueue());
        System.out.println("deQueue->size:"+q.length());
        q.add(4);  //此时会发生下标越界。报异常 

    }
}

当我们采用顺序队列的时候，如果采用“元素不前移”的机制，
当尾指针到达上边界时，就会认为队列已满，但此时低端空间由于出队可能还有空闲空间。

循坏队列

  • 所以解决假溢出的办法就是后面满了 ,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 * 循坏队列
 *
 * 所以解决假溢出的办法就是后面满了 ,
 * 就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列
 * @author qinxuewu
 * @create 19/2/8上午11:14
 * @since 1.0.0
 */
public class QueueTest2<E> {
    private Object[] objs;
    private int front = 0;// 头指针
    private int rear = 0;// 尾指针
    private int size;// 空间大小
    private int length = 0;

    //初始化队列
    public  QueueTest2(int size){
        this.size = size;
        objs = new Object[size];
    }

    //判是否为空
    public boolean isEmpty(){
        return rear == front;
    }

    // 判满
    public boolean isFull() {
        if ((rear + 1) % size == front) {
            return true;
        }
        return false;
    }
    /**
     * 入队：
     * 队尾插入元素
     * @param e
     */
    public boolean add(E e){
        if (isFull()) {
            return false;
        }
        rear = (rear + 1) % size;
        objs[rear] = e;
        length++;
        return true;
    }

    /**
     * 出队：
     *  总是队头删除元素
     * @return
     */
    public Object deQueue(){
        Object n = null;
        if (!isEmpty()) {
            front = (front + 1) % size;
            n = objs[front];
            objs[front] = null;
            length--;
        }
        return n;
    }

    public static void main(String[] args) {
        QueueTest2 q=new QueueTest2(4);
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println("size:"+q.length);
        System.out.println(q.deQueue());
        System.out.println("1:deQueue->size:"+q.length);
        q.add(4);
        System.out.println("2:deQueue->size:"+q.length);
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
    }
}

队列的链式存储

  • 队列的链式存储结构,其实就是线性表的单链表,只不过它只能队尾进，队头出而已, 我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头结点。而队尾指针指向终端结点。

队列的链式存储结构

  • 人队操作时,其实就是在链表尾部插入结点
  • 出队操作时,就是头结点的(next指向)后继结点出队,将头结点的next改为当前出队结点的nextzhi指向的结点, 若链表除头结点外只剩一个元素时, 则需将rear指向头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class QueueTest3 {
    //头指针
    private Node head;
    //尾指针
    private Node rear;
    // 队列的长度
    private int length;


    private class Node {
        Object element; // 数据域
        Node next; // 指针域
        // 无参构造器
        public Node() {
        }
        public Node(Object element) {
            this.element=element;
        }
    }
    // 初始化队列，空头指针
    public QueueTest3() {
        this.head=new Node();
        this.rear=head; // 初始化时数据为空
        this.length=0;
    }
    // 初始化队列，有数据头指针
    public QueueTest3(Object obj) {
        head = new Node(obj);
        rear = head;
        length = 0;
    }

    /**
     * 入队：
     * 在链表尾部插入结点
     * @param obj
     * @throws Exception
     */
    public void add(Object obj){
        Node temp=new Node(obj);
        // 队列使用尾插法
        rear.next = temp; //修改尾指针的next指向新添加的结点
        rear = temp; //更新队首指针新结点
        this.length++;
    }

    /**
     *  出队：
     *
     *  出队操作时,就是头结点的后继结点出队,
     *  将头结点的后继改为它后面的结点,
     *  若链表除头结点外只剩一个元素时, 则需将 rear 指向头结点
     * @return
     */
    public Node deQueue(){
        Node temp;
        if(length==0){
            //无法删除
            temp=null;
        }else{
            if(length==1){

                //头结点的后继结点出队
                temp=head.next;
                //置空下一个节点就可以了
                head.next=null;
                //若链表除头结点外 只剩一个元素时, 则需将 rear 指向头结点
                this.rear=head;
                length--;
            }else{
                //头结点的后继结点出队
                temp= head.next;
                //将头结点的next, 改为出队结点它后面的结点
                this.head.next=this.head.next.next;
                length--;
            }
        }
        return  temp;
    }

    public static void main(String[] args) {
        QueueTest3 q=new QueueTest3();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println("init: "+q.length);
        System.out.println("deQueue: "+q.deQueue().element);
        System.out.println("deQueue: "+q.deQueue().element);
        System.out.println("deQueue: "+q.deQueue().element);
        System.out.println("deQueue->size: "+q.length);

    }

}

循环队列与链队列的比较

  • 从时间上,其实它们的基本操作都是常数时间,即都为0(1)的,不过循环队列是先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存在一些时间开销。
  • 对于空间上来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题,尽管它需要一个指针域, 会产生 一些空间上的开销,但也可以接受 。所以在空间上,链队列更加灵活。
  • 总的来说,在可以确定队列长度最大值的情况下 ,建议用循环队列,如果你无法预估队列的长度时,则用链队列。

觉得本文不错的话，分享一下给小伙伴吧~