队列实现
程序员文章站
2022-03-08 08:05:25
...
一、数组实现
public class ArrayQueue {
//存储数据的数组
private String[] items;
//记录数组容量
private int n;
private int size;
//head记录队头索引,tail记录队尾索引
private int head = 0;
private int tail = 0;
//申请一个指定容量的队列
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
/*
* 入队:
* 1.堆满的时,入队失败
* 1.1频繁出入队,造成数组使用不连续
* 1.2在入队的时候,集中触发进行数据搬移
* 2.在末尾插入数据,注意tail指向队尾元素的索引+1
*/
public boolean enqueue(String item) {
//表示队满
if (head == 0 && tail == n)
return false;
//表示需要数据搬移
else if (head != 0 && tail == n) {
for (int i = head; i < tail; i++) {
items[i - head] = items[i];
}
head = 0;
tail = tail - head;
}
//将数据加入队列
items[tail++] = item;
size++;
return true;
}
//出队:1.队空时,出队失败;2.出队,head索引+1
public String dequeue() {
String res = null;
if (head == tail) return res;
res = items[head++];
size--;
return res;
}
}
二、循环队列
public class LoopArrayQueue {
//存储数据的数组
private String[] items;
//记录数组容量
private int n;
private int size = 0;
//head记录队头索引,tail记录队尾索引
private int head = 0;
private int tail = 0;
//申请一个指定容量的队列
public LoopArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
//入队:关键在于队满的条件
public boolean enqueue(String item) {
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
size++;
return true;
}
//出队:关键在于队空的条件
public String dequeue() {
String res = null;
if (head == tail) return res;
res = items[head];
head = (head + 1) % n;
size--;
return res;
}
}
三、链表实现
public class LinkedQueue {
//定义一个节点类
private class Node {
String value;
Node next;
}
//记录队列元素个数
private int size = 0;
//head指向队头结点,tail指向队尾节点
private Node head;
private Node tail;
//申请一个队列
public LinkedQueue() {
}
//入队
public boolean enqueue(String item) {
Node newNode = new Node();
newNode.value = item;
if (size == 0) head = newNode;
else tail.next = newNode;
tail = newNode;
size++;
return true;
}
//出队
public String dequeue() {
String res = null;
if (size == 0) return res;
if (size == 1) tail = null;
res = head.value;
head = head.next;
size--;
return res;
}
}
推荐阅读
-
php利用正则表达式实现手机号码格式验证代码
-
如何利用html和css来实现注册表单的简单实例
-
常见JS效果之图片减速度滚动实现代码_图象特效
-
javascript实现的动态添加表单元素input,button等(appendChild)_javascript技巧
-
挖掘PHP上传文件类型原理实现_PHP教程
-
php结合md5实现的加密解密方法,php结合md5加密解密_PHP教程
-
PHP实现自动识别Restful API的返回内容类型
-
php日期格式 php实现常见图片格式的水印和缩略图制作面向对象
-
通过Jquery遍历Json的两种数据结构的实现代码_jquery
-
分享用Node.js实现注册邮箱的步骤实例