【数据结构】顺序队列的原理及实现_顺序结构实现队列

1.什么是队列

• 队列是一种比较特殊的线性表，特殊就在于它只允许在表的前端来进行删除，在表的后端来进行插入，队列它是一种操作受限制的线性表。插入的一端称为队尾，删除的一端称为队头，队列里没有元素就称它为空队列。
• 队列是一个有序列表，可以用数组或者是链表来实现的。遵循的是先入先出的原则，就是先存入队列的数据要先取出，后面存的需要后面取出。

• 顺序队列

  • 顺序队列通常是采用了一维数组存储队列里的元素，另外是增加两个指针分别是指向了数组里的队首元素和队尾的元素。其中对头的指针称为front，队尾的称为rear。

• 链式队列

  • 链式队列就是采用单链表作为存储表示，因此话可以在链式队列的声明里用单链表来定义它的存储空间。

  • 链式队列的队头指针指向单链表的第一个结点，队尾指针指向单链表的最后一个结点。

  • 链式队列的队头元素存放在单链表的第一个结点内，若要从队列中退出一个元素，必须从单链表中删去第一个结点，而存放着新元素的结点应插在队列的队尾，即单链表的最后一个结点后面，这个新节点将成为新的队尾

2.顺序队列的功能实现

（1）初始化队列大小

（2）判断队列是否已满

（3）判断队列是否为空

（4）遍历队列中所有元素

（5）入队操作

（6）出队操作

3.顺序队列功能测试

（1）整体代码实现

/**
 * @description 顺序队列 底层采用数组实现的队列
 * @author lixiang
 * @version v1.0
 */
public class ListQueue<T> {

    /**
     * 定义队列的最大长度
     */
    private int maxSize;

    /**
     * 队头指针
     */
    private int front;

    /**
     * 队尾指针
     */
    private int rear;

    /**
     * 当前数组的长度
     */
    private int size;

    /**
     * 定义数组
     */
    private final T[] queue;

    /**
     * 定义默认的队列大小
     */
    private final static int DEFAULT_QUEUE_SIZE = 10;

    /**
     * 初始化队列
     * 指定队列大小
     * @param maxSize
     */
    public ListQueue(int maxSize){
        this.maxSize = maxSize;
        this.front = 0;
        this.size = 0;
        this.rear = 0;
        queue = (T[]) new Object[maxSize];
    }

    /**
     * 初始化队列
     * 不指定队列大小，默认10
     * @param maxSize
     */
    public ListQueue(){
        this.maxSize = DEFAULT_QUEUE_SIZE;
        this.front = 0;
        this.size = 0;
        this.rear = 0;
        queue = (T[]) new Object[DEFAULT_QUEUE_SIZE];
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return front == rear;
    }

    /**
     * 判断队列是否已满
     * @return
     */
    public boolean isFull(){
        return rear == maxSize;
    }

    /**
     * 获取当前有效元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 元素入队操作
     * @param data
     */
    public void add(T data){
        if (isFull()){
            throw new RuntimeException("当前队列已将满了");
        }
        //将当前的队尾指向新的数据
        queue[rear] = data;
        //队尾++
        rear++;
        //有效元素个数++
        size++;
    }

    /**
     * 元素出队操作
     * @return
     */
    public T get(){
        if (isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        //队列先进先出，弹出队列头部的数据
        T data = queue[front];
        //队头++
        front++;
        //有效元素个数--
        size--;
        return data;
    }

    /**
     * 展示所有元素
     */
    public void show(){
        if (isEmpty()){
            System.out.println("[]");
            return;
        }
        for (int i = front; i < rear; i++) {
            System.out.print(queue[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListQueue<Integer> listQueue = new ListQueue<>(5);
        System.out.println("判断当前队列是否为空："+listQueue.isEmpty());
        System.out.println("判断当前队列是否已满："+listQueue.isFull());
        System.out.println("向队列中加入元素：1 2 3");
        listQueue.add(1);
        listQueue.add(2);
        listQueue.add(3);
        System.out.println("输出队列中的元素：");
        listQueue.show();
        System.out.println("队列弹出元素："+listQueue.get());
        System.out.println("输出队列中的元素：");
        listQueue.show();
        System.out.println("当前有效元素个数："+ listQueue.getSize());
    }
}
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

（2）测试结果