java算法:FIFO队列
FIFO队列是一个ADT,由两个基本操作构成:插入(放入)一个新项,删除(得到)最早插入的项。
例1:FIFO队列ADT接口
- interfaceintQueue{
-
intQueue(intq);
-
intempty();
-
voidput(intq);
-
intget();
- }
interface intQueue{
intQueue(int q);
int empty();
void put(int q);
int get();
}
使用数组或链表,在常数时间内实现FIFO队列ADT的get和put操作。
例2:FIFO队列的链表实现
- publicclassintQueue{
-
privateclassNode{
-
intitem;
- Nodenext;
-
Node(intitem){
-
this.item=item;
-
next=null;
- }
- }
-
privateNodehead,tail;
-
intQueue(intmax){
-
head=null;
-
tail=null;
- }
-
booleanempty(){
-
return(head==null);
- }
-
voidput(intitem){
- Nodet=tail;
-
tail=newNode(item);
-
if(empty()){
- head=tail;
-
}else{
- t.next=tail;
- }
- }
-
intget(){
-
intv=head.item;
- Nodet=head.next;
- head=t;
-
returnv;
- }
- }
public class intQueue{
private class Node{
int item;
Node next;
Node(int item){
this.item = item;
next = null;
}
}
private Node head, tail;
intQueue(int max){
head = null;
tail = null;
}
boolean empty(){
return (head == null);
}
void put(int item){
Node t = tail;
tail = new Node(item);
if(empty()){
head = tail;
}else{
t.next = tail;
}
}
int get(){
int v = head.item;
Node t = head.next;
head = t;
return v;
}
}
数组要求自始自终都要为预计的最大的项数保留足够的空间,而链表表示使用的空间与数据结构中的元素个数成比例,但要为指针分配额外的空间,并且每个操作都要花分配和释放内存的额外时间。
例3:FIFO队列的数组实现
- publicclassintQueue{
-
privateint[]q;
-
privateintN,head,tail;
-
intQueue(intmax){
-
q=newint[maxN+1];
- head=N;
-
tail=0;
- }
-
booleanempty(){
-
return(head%N==tail);
- }
-
voidput(intitem){
- q[tail++]=item;
- tail=tail%N;
- }
-
intget(){
- head=head%N;
-
returnq[head++];
- }
- }
public class intQueue{
private int[] q;
private int N, head, tail;
intQueue(int max){
q = new int[maxN + 1];
head = N;
tail = 0;
}
boolean empty(){
return (head%N == tail);
}
void put(int item){
q[tail++] = item;
tail = tail%N;
}
int get(){
head = head%N;
return q[head++];
}
}
拓展:双端队列,删除随机项队列(如果第一项则是FIFO队列,如果最后一项则是栈),或者删除关键字项,自定义项等。
分享到:
相关推荐
并发编程中,FIFO队列通常用作线程间的通信工具,例如Java的`java.util.concurrent.BlockingQueue`接口,它提供了线程安全的入队和出队操作,能够有效地协调生产者和消费者的执行顺序。 总的来说,FIFO队列设计的...
在java实现中,使用了FIFO队列来存储可能的解决方案,并使用剪枝函数来减少搜索空间。Java实现的主要步骤包括: 1. 初始化FIFO队列和剪枝函数。 2. 生成可能的解决方案,并将其存储在FIFO队列中。 3. 使用剪枝函数...
Java中的队列是一种数据结构,它遵循先进先出(FIFO)原则,即最先插入的元素将是最先被删除的。在Java中,队列的实现主要有三种:顺序队列、链式队列和循环队列。下面我们将详细探讨这三种队列的实现方式。 1. **...
在java中,我们可以使用一个队列来实现FIFO算法。队列的每个元素是一个页面,队列的头部是最早进入内存的页面。每当系统需要置换一页时,我们从队列的头部取出一页,并将其置换出去。 java实现代码 在给定的java...
在实际编程中,Java中的`java.util.LinkedList`可以用来实现FIFO队列,因为它的插入(add)和移除(removeFirst)操作都遵循FIFO原则。而为了模拟操作系统的进程调度,开发者可能需要设计一个类来表示进程,包含进程...
Java算法大全源码包是一个集合,包含了众多使用Java语言实现的算法示例代码。这个压缩包为学习和理解计算机科学中的各种算法提供了宝贵的资源。在Java编程中,掌握算法是提升编程技能和解决复杂问题的关键。下面将...
- 队列:先进先出(FIFO)的数据结构,适用于处理等待执行的任务。 - 树:非线性数据结构,包括二叉树、平衡树(如AVL树和红黑树)、B树等,用于搜索、排序等操作。 - 图:由节点和边构成,用于表示复杂的关系,...
队列是一种遵循“先进先出”(FIFO,First In First Out)原则的数据结构,类似于现实生活中的排队等待。在链队列中,元素按照加入的顺序排列,第一个加入的元素被称为队首(front),最后一个加入的元素称为队尾...
- 队列:队列是一种先进先出(FIFO)的数据结构,常见应用包括任务调度、缓冲区等。 - 树:树结构包括二叉树、平衡树(如AVL树、红黑树)等,广泛应用于搜索、排序等领域。 - 图:图数据结构表示对象之间的关系,...
这里我们将深入探讨三种常见的页面替换算法:FIFO(先进先出)、LRU(最近最少使用)以及OPT(最佳页面替换)算法,并以Java实现为切入点。 1. FIFO(先进先出)算法: FIFO是最简单的页面替换策略,它基于队列数据...
4. 队列:先进先出(FIFO)的数据结构,适用于任务调度和消息传递。 5. 树:非线性的数据结构,如二叉树、平衡树(AVL、红黑树)等,常用于搜索和排序。 6. 图:表示对象之间的关系,如邻接矩阵和邻接表,用于网络...
Java实现FIFO和LRU页面置换算法,可以创建模拟内存的数组,用于存储页面,并维护一个队列(对于FIFO)或时间戳(对于LRU)来追踪页面的使用情况。在处理页面请求时,Java程序会根据所选算法更新这些数据结构并决定...
- 队列:先进先出(FIFO)的数据结构,如循环队列、链式队列等。 - 栈:后进先出(LIFO)的数据结构,如递归的底层实现。 - 树结构:包括二叉树、平衡树(AVL、红黑树)、B树、B+树等。 - 图:邻接矩阵和邻接表...
- 栈和队列:后进先出(LIFO)的栈用于函数调用、表达式求值;先进先出(FIFO)的队列在任务调度、打印队列中有应用。 - 树:包括二叉树、平衡树(AVL、红黑树)、堆(最大堆、最小堆)等,广泛应用于搜索、排序等...
同时,创建一个FIFO队列来存储页面的访问历史。 2. **页表**: 为了跟踪每个页面在内存中的状态(是否在内存中、最近的访问时间等),可以使用一个布尔数组或自定义类表示页表。 3. **页面替换**: 当新的数据请求...
1. 并发队列:Java 的并发库提供了一组线程安全的队列实现,如 ConcurrentLinkedQueue 和 LinkedBlockingQueue,它们在多线程环境中高效且安全。 2. 队列优先级排序:PriorityQueue 是一个可以按照特定顺序排序的...
- 栈和队列:LIFO(后进先出)和FIFO(先进先出)的数据结构。 - 树:包括二叉树、平衡树(AVL、红黑树等)、堆等。 - 图:表示对象之间的关系,如邻接矩阵和邻接表。 7. **递归与回溯**: - 递归:函数调用...
- 栈和队列:LIFO(后进先出)和FIFO(先进先出)的数据结构,常用于处理操作序列。 - 树和二叉树:如二叉搜索树、平衡二叉树(AVL树、红黑树)等。 - 哈希表:提供快速查找和插入功能,通过哈希函数实现。 9. ...
本项目通过Java语言实现了几种经典的磁盘调度算法,包括FIFO(先进先出)、SSTF(最短寻道时间优先)、SCAN(扫描)以及C-SCAN(循环扫描),并提供了用户界面和结果记录功能,有助于理解这些算法的工作原理。...