Coursera算法Programming Assignment 2: Deques and Randomized Queues

代码实现

题目链接：http://coursera.cs.princeton.edu/algs4/assignments/queues.html

本次编程要求编写3个类，分别是Deque类、RandomizedQueue类以及Permutation类。Deque类为数据提供双向储存结构，要求在结构始末都可实现数据的增减操作。RandomizedQueue类需要实现随机取出数据，Permutation类主要对RandomizedQueue类进行测试。

Deque类

Deque类可采用双向链表实现，类似于向后增加索引last，可在前增加索引pre，便可实现双向操作。

//Deque类
import java.util.NoSuchElementException ;
import java.util.Iterator ;

public class Deque<Item> implements Iterable<Item> { 
    private Node<Item> first , last ;
    private int n ;
    private static class Node<Item> { // construct an empty deque
        private Item item ;
        private Node<Item> pre ;
        private Node<Item> next ;
	}
    public Deque(){
        n=0;first=null;last=null;
	}
    public boolean isEmpty(){return n==0;} // is the deque empty?
    public int size(){return n;} // return the number of items on the deque
    public void addFirst(Item item){ // add the item to the front
        if(item==null) throw new IllegalArgumentException();
        Node<Item> oldfirst=first;
        first=new Node<Item>();
		first.pre=null;first.item=item;
		if(isEmpty()) {
			first.next=null;last=first;
		}
		else {
			first.next=oldfirst;oldfirst.pre=first;
		}
		n++;
	}
	public void addLast(Item item){ // add the item to the end
		if(item==null) throw new IllegalArgumentException();
		Node<Item> oldlast=last;
		last=new Node<Item>();
		last.item=item;last.next=null;
		if(isEmpty()) {
			last.pre=null;first=last;
		}
		else {
			oldlast.next=last;last.pre=oldlast;
		}
		n++;
	}
	public Item removeFirst(){ // remove and return the item from the front
		if(isEmpty()) throw new NoSuchElementException();
		Item item=first.item;
		n--;
		if(isEmpty()) {
			first=null;last=null;
		}
		else {
			first=first.next;first.pre=null;
		}
		return item;
	}
	public Item removeLast(){ // remove and return the item from the end
		if(isEmpty()) throw new NoSuchElementException();
		Item item=last.item;
		n--;
		if(isEmpty()) {
			first=null;last=null;
		}
		else {
			last=last.pre;last.next=null;
		}
		return item;
	}
	public Iterator<Item> iterator(){ // return an iterator over items in order from front to end
		return new DequeIterator(first);
	}
	private class DequeIterator implements Iterator<Item> {
		Node<Item> current;
		public DequeIterator(Node<Item> first){current=first;}
		public boolean hasNext(){
			return current!=null;
		}
		public void remove(){
			throw new UnsupportedOperationException();
		}
		public Item next(){
			if(!hasNext()) throw new NoSuchElementException();
			Item item=current.item;
			current=current.next;
			return item;
		}
	}
}

RandomizedQueue类

为了方便定位每一个数据，本类采用数组的形式，其中sample()和dequeue()方法可以生成随机数实现随机输出，而迭代器中可利用StdRandom.shuffle()方法打乱数组再按顺序输出。

//RandomizedQueue类
import java.util.NoSuchElementException;
import java.util.Iterator;
import edu.princeton.cs.algs4.StdRandom;

public class RandomizedQueue<Item> implements Iterable<Item> {
	private Item[] a;private int n;
	public RandomizedQueue(){ // construct an empty randomized queue
		a=(Item[])new Object[1];
		n=0;
	}
	public boolean isEmpty(){return n==0;} // is the randomized queue empty?
	public int size(){return n;} // return the number of items on the randomized queue
	public void enqueue(Item item){  // add the item
		if(item == null) throw new IllegalArgumentException();
		if(n == a.length) resize(2*a.length);
		a[n++]=item;
	}
	public Item sample(){ // return a random item (but do not remove it)
		if(isEmpty()) throw new NoSuchElementException();
		return a[StdRandom.uniform(0, n)];
	}
	public Item dequeue(){ // remove and return a random item
		if(isEmpty()) throw new NoSuchElementException();
		int i=StdRandom.uniform(0, n);
		Item item=a[i];
		a[i]=a[--n];
		a[n]=null;
		if(0<n&&n==a.length/4) resize(a.length/2);
		return item;
	}
	private void resize(int max){
		Item[] re=(Item[])new Object[max];
		for(int i=0;i<n;i++) re[i]=a[i];
		a=re;
	}
	public Iterator<Item> iterator(){ // return an independent iterator over items in random order
		return new RandomizedQueueIterator();
	}
	private class RandomizedQueueIterator implements Iterator<Item>{
		private Item[] aarray;
		private int N;
		private int i=0;
		public RandomizedQueueIterator() {
			N=a.length;
			aarray=(Item[])new Object[N];
			for(int i=0;i<a.length;i++) aarray[i]=a[i]; 
			StdRandom.shuffle(aarray);
		}
		public boolean hasNext(){return i<N;}
		public void remove(){throw new UnsupportedOperationException();}
		public Item next(){
			if(!hasNext()) throw new NoSuchElementException();
            Item item=aarray[i++];
            return item;
		}
	}
}

Permutation类

本类主要是测试RandomizedQueue类，输出时注意要跟示例一样一行一个数据，不然代码检测中会扣分。

//Permutation类
package com.construction;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Permutation {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int k=Integer.parseInt(args[0]);
		RandomizedQueue<String> rq=new RandomizedQueue<String>();
		while(!StdIn.isEmpty()){
			rq.enqueue(StdIn.readString());
		}
		while(rq.size()-k>0) rq.dequeue();
		for(int i=0;i<k;i++){
			StdOut.println(rq.dequeue());
		}
	}
}

小结

数组和链表是最基本的数据结构，本次编程加深了对链表的理解，但自己编程时对内存使用和运行时间的优化意识还需加强。