在美国读计算机本科专业，编程课程中可能会涉及随机化队列和队列相关问题。下面我们给大家分享一个编程任务例题，对这方面内容掌握得不是很牢固的同学可以重点关注一下~

一、任务要求

为随机队列和队列编写一个泛型ADT。作业具体目标是使用数组和链表实现基本数据结构，并使你重新熟悉Java编程。

二、作业解析

1.Step1：安装Java

为你的操作系统安装Java。注意，泛型需要Java 1.5。[Windows·Mac OS X·Linux]

并使你重新熟悉Java编程。

2.Step2：随机队列

随机队列类似于堆栈或队列，不同之处在于，要删除的项是从数据结构中的项中均匀随机选择的。创建一个支持以下操作的通用ADT RandomizedQueue。

public class RandomizedQueue{

public RandomizedQueue() // construct an empty randomized queue

public boolean isEmpty() // return true if the queue is empty,false otherwise

public void add(Item item) // insert the item into the queue

public Item remove() // delete and return an item from the queue,uniformly at random

}

你的ADT应该在常数平摊时间内支持所有的操作。也就是说，任何N个随机队列操作序列(从空队列开始)都应该执行O(N)个步骤。

3.Step3：出列

双端队列或deque(发音为“deck”)是堆栈和队列的泛化，支持从数据结构的前端或后端插入和删除项。创建一个支持以下操作的泛型ADT Deque。

public class Deque{

public Deque() // construct an empty deque

public boolean isEmpty() // return true if the queue is empty,false otherwise

public void addFirst(Item item) // insert the item at the front of the queue

public void addLast(Item item) // insert the item at the end of the queue

public Item removeFirst() // delete and return the first item in the queue

public Item removeLast() // delete and return the last item in the queue

}你的ADT应该支持在恒定的最坏情况时间内的每个操作。也就是说，每个deque操作应该执行O(1)个步骤。

4.Step4：客户端

编写一个客户端程序来解决以下问题。你只能在客户端声明一个变量，并且它必须是Deque或RandomizedQueue类型。客户端程序应该通过使用泛型来避免强制转换。

给定一个命令行参数k，从标准输入中读取字符串序列，并均匀随机地打印出恰好k个字符串的子集。

使用StdIn.readChar从标准输入读入DNA序列。确定字符串是否表示沃森-克里克补码回文(当你用其补码替换每个碱基时，字符串等于它的反向:a - t,C-G)。DNA中的回文具有许多重要的生物学作用。例如，肿瘤细胞经常通过形成DNA回文来扩增它们的基因。

5.Step5：可交付成果

提交数据类型RandomizedQueue.java和dequeue .java。每种数据类型都应该包含自己的main函数，该函数可以彻底测试相关的操作。不能调用任何Java库函数。同时提交客户端程序子集。java和palindrome.java。最后，提交一个readme.txt文件并回答问题。

上述内容是美国本科计算机随机化队列和队列相关问题作业解析，需要的同学可以看看，希望对你们完成作业有帮助。有其他作业问题，欢迎大家随时咨询留求艺的资深教师，获取专业解答!