数据结构与算法(3): 线性结构-队列

发表于   |   分类于

队列：一种线性存储结构，和栈一样也是一种操作受限的表。

  • 队列中数据是按照”先进先出（FIFO）“方式进出队列的。
  • 队列只允许在”队首“删除，而在”队尾“插入。

顺序队列

  建立顺序队列结构必须为分配一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。

  每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。

问题: 当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

循环队列

  把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。
  在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。（从maxsize-1增加1变为0）

队列的实现方式

数组实现

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
/**
 * 顺序队列：数组实现
 */
public class SequenceArrayQueue<T> {
    private Object[] items;
    private int theSize;
    private int front;
    private int rear;
    public SequenceArrayQueue(int maxSize) {
        this.items = new Object[maxSize];
        this.theSize = 0;
        this.front = 0;
        this.rear = 0;
    }
    /**
     * 入队
     * @param t
     */
    public void enqueue(T t) throws Exception {
        if (isFull()){
            throw new Exception("顺序队列已满，不能入队");
        }
        items[rear++] = t;
        theSize++;
    }
    /**
     * 出队
     * @return
     * @throws Exception
     */
    @SuppressWarnings("unchecked")
    public T dequeue() throws Exception {
        if (isEmpty()){
            throw new Exception("顺序队列为空队列，不能出队");
        }
        T ele = (T) items[front];
        items[front] = null;
        front++;
        theSize--;
        return ele;
    }
    public int size(){
        return theSize;
    }
    public boolean isFull(){
        return items.length == rear;
    }
    public boolean isEmpty(){
        return theSize == 0;
    }
}
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
/**
 * 循环队列：数组实现
 */
public class CircularArrayQueue<T> {
    private Object[] items;
    private int theSize;
    private int front;
    private int rear;
    public CircularArrayQueue(int maxSize) {
        this.items = new Object[maxSize];
        this.theSize = 0;
        this.front = 0;
        this.rear = 0;
    }
    /**
     * 入队
     *
     * @param t
     */
    public void enqueue(T t) throws Exception {
        if (isFull()) {
            throw new Exception("循环队列已满，不能入队");
        }
        // 注意
        rear = (front + theSize) % items.length;
        items[rear] = t;
        theSize++;
    }
    /**
     * 出队
     *
     * @return
     * @throws Exception
     */
    @SuppressWarnings("unchecked")
    public T dequeue() throws Exception {
        if (isEmpty()) {
            throw new Exception("循环队列为空队列，不能出队");
        }
        T ele = (T) items[front];
        items[front] = null;
        front = (front + 1) % items.length;
        theSize--;
        return ele;
    }
    public int size() {
        return theSize;
    }
    /**
     * 判断已满，与顺序队列不同
     *
     * @return
     */
    public boolean isFull() {
        return items.length == theSize;
    }
    public boolean isEmpty() {
        return theSize == 0;
    }
}

链表实现

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
/**
 * 队列：单链表实现
 */
public class SingleLinkedListQueue<T> {
    private SingleLinkedList<T> list;
    public SingleLinkedListQueue() {
        list = new SingleLinkedList<>();
    }
    /**
     * 入队，链表增加一个元素
     * @param t
     */
    public void enqueue(T t){
        list.add(t);
    }
    /**
     * 出队，链表删除索引为0的元素
     * @return
     */
    public T dequeue() throws Exception {
        if (isEmpty()){
            throw new Exception("队列是空的");
        }
        return list.remove(0);
    }
    public int size(){
        return list.size();
    }
    public boolean isEmpty(){
        return list.size() == 0;
    }
}