在美國(guó)讀計(jì)算機(jī)本科專(zhuān)業(yè)，編程課程中可能會(huì)涉及隨機(jī)化隊(duì)列和隊(duì)列相關(guān)問(wèn)題。下面我們給大家分享一個(gè)編程任務(wù)例題，對(duì)這方面內(nèi)容掌握得不是很牢固的同學(xué)可以重點(diǎn)關(guān)注一下~

一、任務(wù)要求

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

二、作業(yè)解析

1.Step1：安裝Java

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

并使你重新熟悉Java編程。

2.Step2：隨機(jī)隊(duì)列

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

3.Step3：出列

雙端隊(duì)列或deque(發(fā)音為“deck”)是堆棧和隊(duì)列的泛化，支持從數(shù)據(jù)結(jié)構(gòu)的前端或后端插入和刪除項(xiàng)。創(chuàng)建一個(gè)支持以下操作的泛型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應(yīng)該支持在恒定的最壞情況時(shí)間內(nèi)的每個(gè)操作。也就是說(shuō)，每個(gè)deque操作應(yīng)該執(zhí)行O(1)個(gè)步驟。

4.Step4：客戶端

編寫(xiě)一個(gè)客戶端程序來(lái)解決以下問(wèn)題。你只能在客戶端聲明一個(gè)變量，并且它必須是Deque或RandomizedQueue類(lèi)型。客戶端程序應(yīng)該通過(guò)使用泛型來(lái)避免強(qiáng)制轉(zhuǎn)換。

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

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

5.Step5：可交付成果

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

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