前言
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。先进先出,简单暴力的理解就是吃进去拉出来
优点:
- 提供了先进先出的存取方式
缺点:
- 存取其他项很慢
队列有两个最基本的操作,入队enqueue(),放一个数据到队列的尾部;出队dequeue(),从队列头部取出一个元素。
队列可以使用数组来实现也可以使用链表来实现,用数组实队列的栈叫做顺序队列,用链表实现的队列叫做链式队列。
使用数组来实现一个队列:public class ArrayQueue {
private String[] items;
private int n = 0;//总大小
private int head = 0;
private int tail = 0;
//申请一个大小为n的数组
public ArrayQueue(int n) {
this.items = new String[n];
this.n = n;
}
//入队
public boolean enqueue(String item){
//如果队列满了返回false
if(tail == n) return false;
items[tail] = item;
++tail;
return true;
}
//出队
public String dequeue(){
//head == tail 表示队列为空
if(head == tail) return null;
String res = items[head];
++head;
return res;
}
}
队列需要两个指针,一个指向队头,一个指向队尾。
当a、b、c、d一次进入队列之后,队列中的head指针指向下标为0的位置,tail下标为4的位置 当我们调用两次出队操作的之后,队列中的head指针指向下标为2的位置,tail指针位置不变。
随着不停的入队和出队操作,head和tail指针会不断的往后移动移动到最右边,即使数组中还有空闲的空间也不能往队列中添加数据了,那怎么办呢?
我们可以使用数据搬移,当然出队的时候不会出现空间不够的情况也就不用搬移,我们只需要在入队的时候集中触发一次数据搬移即可。根据这个思想,上面的出队操作不用变,入队操作可以改成下面的:
public boolean enqueue(String item){
//tail==n 说明队列满了
if(tail == n){
//tail==n&&head==0说明整个队列都是满的
if(head == 0) return false;
//搬移数据
for (int i = head; i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?