5、队列的顺序存储结构:循环队列、两种方法

队列的ADT:

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
package ren.laughing.datastructure.base;
 
import ren.laughing.datastructure.exception.QueueEmptyException;
 
/**
 * 队列Queue的ADT:先进先出
 * 在队列中把插入数据元素的一端称为 队尾(rear), 删除数据元素
 * 的一端称为 队首(front)。向队尾插入元素称为 进队或入队,
 * 新元素入队后成为新的队尾元素;从队列中删除元素称为 离队或出队,
 * 元素出队后,其后续元素成为新的队首元素。
 * @author Laughing_Lz
 * @time 2016年4月7日
 */
public interface Queue {
    //返回队列的大小
    public int getSize();
    //判断队列是否为空
    public boolean isEmpty();
    //数据元素 e 入队
    public void enqueue(Object e);
    //队首元素出队
    public Object dequeue() throws QueueEmptyException;
    //取队首元素
    public Object peek() throws QueueEmptyException;
    }

循环队列的顺序存储实现,采用少一存储空间的方法:

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
package ren.laughing.datastructure.baseImpl;
 
import ren.laughing.datastructure.base.Queue;
import ren.laughing.datastructure.exception.QueueEmptyException;
/**
 * 队列Queue的顺序存储,此处使用循环队列,逆时针,方法一
 * ★循环队列:难点在于如何判断队空和队满
 * 方法一:★少使用一个存储空间,即:当队尾指针的下一指针指向队首指针时,就停止入队。
 * 判决:队空:rear=front,队满:(rear+1)%capacity = float
 * 方法二:★增设一个标志size,以size?=MAX区别队满队空
 * 判决:队空:size = 0,队满:size = capacity
 * @author Laughing_Lz
 * @time 2016年4月7日
 */
public class QueueArray implements Queue{
    private static final int CAP=7;//队列默认容量大小
    private Object[] elements;
    private int capacity;//数组的实际大小 elements.length
    private int front;
    private int rear;
 
    public QueueArray() {
        this(CAP);
    }
    public QueueArray(int cap) {
        this.elements = new Object[capacity];
        this.capacity = cap+1;//这里数组实际大小capacity比队列容量cap大1
        this.front = 0;
        this.rear = 0;
    }
    //获取队列的容量
    @Override
    public int getSize() {
        return (rear-front+capacity)%capacity;//返回队列的实际容量,小于等于capacity-1
    }
    //判断是否队空
    @Override
    public boolean isEmpty() {
        if(rear == front){
            return true;
        }else{
            return false;
        }
    }
    //入队:相当于在insertAfter队尾
    @Override
    public void enqueue(Object e) {
//        if(getSize()==capacity-1){//同下,判断队列容量是否已满
        if((rear+1)%capacity == front){//判断是否队满
            expandSpace();//扩充队列的容量
        }
        elements[rear] = e;
        rear = (rear+1)%capacity;//rear有可能从capacity-1移动到0
    }
    //出队:相当于在remove队首
    @Override
    public Object dequeue() throws QueueEmptyException {
        if(rear == front){//判断是否队空
            throw new QueueEmptyException("错误:队列已空");
        }
        Object obj = elements[front];
        elements[front] = null;//置空
        front = (front+1)%capacity;//front有可能从capacity-1移动到0
        return obj;
    }
    //获取队首数据元素
    @Override
    public Object peek() throws QueueEmptyException {
        if(rear == front){//判断是否队空
            throw new QueueEmptyException("错误:队列已空");
        }
        return elements[front];
    }
    /**
     * ★扩充数组长度
     */
    private void expandSpace() {
        Object[] a = new Object[elements.length * 2];
        int i = front;
        int j = 0;
        while(i!=rear){//将从 front 开始到 rear 前一个存储单元的元素复制到新数组
            a[j++] = elements[i];
            i = (i+1)%capacity;
        }
        elements = a;
        capacity = elements.length;
        front  = 0;
        rear = j;//重新设置新的队首队尾指针
    }
}

循环队列的顺序存储实现,采用加标志size的方法:

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
package ren.laughing.datastructure.baseImpl;
 
import ren.laughing.datastructure.base.Queue;
import ren.laughing.datastructure.exception.QueueEmptyException;
/**
 * 队列Queue的顺序存储,此处使用循环队列,逆时针,方法一
 * ★循环队列:难点在于如何判断队空和队满
 * 方法一:★少使用一个存储空间,即:当队尾指针的下一指针指向队首指针时,就停止入队。
 * 判决:队空:rear=front,队满:(rear+1)%capacity = float
 * 方法二:★增设一个标志size,以size?=MAX区别队满队空
 * 判决:队空:size = 0,队满:size = capacity
 * @author Laughing_Lz
 * @time 2016年4月7日
 */
public class QueueArray implements Queue{
    private static final int CAP=7;//队列默认容量大小
    private Object[] elements;
    private int capacity;//数组的实际大小 elements.length
    private int front;
    private int rear;
 
    public QueueArray() {
        this(CAP);
    }
    public QueueArray(int cap) {
        this.elements = new Object[capacity];
        this.capacity = cap+1;//这里数组实际大小capacity比队列容量cap大1
        this.front = 0;
        this.rear = 0;
    }
    //获取队列的容量
    @Override
    public int getSize() {
        return (rear-front+capacity)%capacity;//返回队列的实际容量,小于等于capacity-1
    }
    //判断是否队空
    @Override
    public boolean isEmpty() {
        if(rear == front){
            return true;
        }else{
            return false;
        }
    }
    //入队:相当于在insertAfter队尾
    @Override
    public void enqueue(Object e) {
//        if(getSize()==capacity-1){//同下,判断队列容量是否已满
        if((rear+1)%capacity == front){//判断是否队满
            expandSpace();//扩充队列的容量
        }
        elements[rear] = e;
        rear = (rear+1)%capacity;//rear有可能从capacity-1移动到0
    }
    //出队:相当于在remove队首
    @Override
    public Object dequeue() throws QueueEmptyException {
        if(rear == front){//判断是否队空
            throw new QueueEmptyException("错误:队列已空");
        }
        Object obj = elements[front];
        elements[front] = null;//置空
        front = (front+1)%capacity;//front有可能从capacity-1移动到0
        return obj;
    }
    //获取队首数据元素
    @Override
    public Object peek() throws QueueEmptyException {
        if(rear == front){//判断是否队空
            throw new QueueEmptyException("错误:队列已空");
        }
        return elements[front];
    }
    /**
     * ★扩充数组长度
     */
    private void expandSpace() {
        Object[] a = new Object[elements.length * 2];
        int i = front;
        int j = 0;
        while(i!=rear){//将从 front 开始到 rear 前一个存储单元的元素复制到新数组
            a[j++] = elements[i];
            i = (i+1)%capacity;
        }
        elements = a;
        capacity = elements.length;
        front  = 0;
        rear = j;//重新设置新的队首队尾指针
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注