美国本科计算机作业讲解：编程任务

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

　　一、任务要求

　　为随机队列和队列编写一个泛型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文件并回答问题。

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