在美國讀計算機本科專業(yè)，編程課程中可能會涉及隨機化隊列和隊列相關問題。下面我們給大家分享一個編程任務例題，對這方面內容掌握得不是很牢固的同學可以重點關注一下~

一、任務要求

為隨機隊列和隊列編寫一個泛型ADT。作業(yè)具體目標是使用數(shù)組和鏈表實現(xiàn)基本數(shù)據(jù)結構，并使你重新熟悉Java編程。

二、作業(yè)解析

1.Step1：安裝Java

為你的操作系統(tǒng)安裝Java。注意，泛型需要Java 1.5。[Windows·Mac OS X·Linux]

并使你重新熟悉Java編程。

2.Step2：隨機隊列

隨機隊列類似于堆?；蜿犃?，不同之處在于，要刪除的項是從數(shù)據(jù)結構中的項中均勻隨機選擇的。創(chuàng)建一個支持以下操作的通用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應該在常數(shù)平攤時間內支持所有的操作。也就是說，任何N個隨機隊列操作序列(從空隊列開始)都應該執(zhí)行O(N)個步驟。

3.Step3：出列

雙端隊列或deque(發(fā)音為“deck”)是堆棧和隊列的泛化，支持從數(shù)據(jù)結構的前端或后端插入和刪除項。創(chuàng)建一個支持以下操作的泛型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操作應該執(zhí)行O(1)個步驟。

4.Step4：客戶端

編寫一個客戶端程序來解決以下問題。你只能在客戶端聲明一個變量，并且它必須是Deque或RandomizedQueue類型?？蛻舳顺绦驊撏ㄟ^使用泛型來避免強制轉換。

給定一個命令行參數(shù)k，從標準輸入中讀取字符串序列，并均勻隨機地打印出恰好k個字符串的子集。

使用StdIn.readChar從標準輸入讀入DNA序列。確定字符串是否表示沃森-克里克補碼回文(當你用其補碼替換每個堿基時，字符串等于它的反向:a - t,C-G)。DNA中的回文具有許多重要的生物學作用。例如，腫瘤細胞經(jīng)常通過形成DNA回文來擴增它們的基因。

5.Step5：可交付成果

提交數(shù)據(jù)類型RandomizedQueue.java和dequeue .java。每種數(shù)據(jù)類型都應該包含自己的main函數(shù)，該函數(shù)可以徹底測試相關的操作。不能調用任何Java庫函數(shù)。同時提交客戶端程序子集。java和palindrome.java。最后，提交一個readme.txt文件并回答問題。

上述內容是美國本科計算機隨機化隊列和隊列相關問題作業(yè)解析，需要的同學可以看看，希望對你們完成作業(yè)有幫助。有其他作業(yè)問題，歡迎大家隨時咨詢留求藝的資深教師，獲取專業(yè)解答!