数据结构和算法4-线性-队列
1.什么是队列
队列其实也是特殊的线性表。被限制了从尾插入数据,从头取出数据
特点:
- 先进后先出 FIFO (First In First Out)
- 向队尾(rear)插入元素称为入队
- 从队首(front)中删除元素称为出队
常见操作
- size: 大小
- isEmpty: 是否为空
- enqueue: 入队
- dequeue: 出队
- peek 取队首元素
2.存储结构
- 顺序队列结构
- 链队列结构
2-1.顺序队列
缺点:
- 从队首移除数据(出队),空间浪费了。
那如何解决呢?
可以使用循环顺序方式。末尾元素的下一个指向头元素。
循环顺序队列实现
public class CircleArrayQueue<T> {
private Object[] elementData;
private int size = 0;
private int front = 0;
private int rear = 0;
private ReentrantLock lock = new ReentrantLock();
private Condition fullCondition = lock.newCondition();
private Condition emptyCondition = lock.newCondition();
public CircleArrayQueue(int size) {
this.size = size;
elementData = new Object[size];
front = 0;
rear = 0;
}
public void enqueue(T value) {
try {
lock.lock();
if (isFull()) {
System.out.println("队列满了,还往哪塞?" + value);
fullCondition.await();
}
this.elementData[rear] = value;
//rear+1,防止超过size,要跟size取模
rear = (rear + 1) % size;
emptyCondition.signal();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
public T dequeue() {
try {
lock.lock();
if (isEmpty()) {
System.out.println("队列空了,还取个啥子?");
emptyCondition.await();
}
T value = (T) this.elementData[front];
//front+1,防止超过size,要跟size取模
front = (front + 1) % size;
fullCondition.signal();
return value;
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
return null;
}
public int size() {
return Math.abs(rear - front);
}
public boolean isEmpty() {
// front和rear在一起说明是空
return this.front == this.rear;
}
public boolean isFull() {
// 下表从0开始,rear+1 取mod跟front对比
return (this.rear + 1) % this.size == front;
}
}
测试
public class CircleArrayQueueTest {
public static void main(String[] args) throws InterruptedException {
final CircleArrayQueue<String> queue = new CircleArrayQueue<String>(5);
int totalCount = 20;
ExecutorService pool = Executors.newFixedThreadPool(2);
pool.submit(() -> {
for (int i = 0; i < totalCount; i++) {
queue.enqueue("" + (Math.random() * 100));
}
});
pool.submit(() -> {
for (int i = 0; i < totalCount; i++) {
System.out.println(queue.dequeue());
}
});
TimeUnit.SECONDS.sleep(5);
pool.shutdown();
}
}
2-2.链队列
队列的链式存储可以使用单链表来实现。需要两个node,分别对应队首front和队尾rear
3.双端队列
当队列两端都可以操作,不限于一端读、一端写。两端都可以读写,那么就是双端队列了。
4.演示
我们直接使用java提供的类来演示
- Queue:队列类
Queue是接口,使用了LinkedList来实列化对象。因为LinkedList实现了Queue
Queue里有以下几个方法
操作 | 会抛异常 | 会阻塞 | 有返回值 | 超时 |
---|---|---|---|---|
添加 | add(e) | put(e) | offer(e) | offer(e,time,unit) |
移除/取出 | remove() | take() | poll() | poll(time,unit) |
检查 | element() | 无 | peek() | 无 |
public class JavaQueueTest {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
while (!queue.isEmpty()){
System.out.print(queue.poll());
}
}
}
结果:abcd
5.进入一步深造
下一步如何再深造呢?
去看java的
Queue
的实现类ListList
、ConcurrentLinkedQueue
等源码
转载请注明来源,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 157162006@qq.com
文章标题:数据结构和算法4-线性-队列
字数:714
本文作者:沐雨云楼
发布时间:2020-07-04, 14:10:22
最后更新:2020-09-12, 21:21:47
原始链接:https://iworkh.gitee.io/blog/2020/07/04/data-structures-algorithms-linear-queue/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。