Coursera普林斯顿大学算法Week2: Deques and Randomized Queues 队列

任务链接：http://coursera.cs.princeton.edu/algs4/assignments/queues.html

本周任务主要以下难点：

1、根据各自特点选取实现Deques和Randomized Queues的物理存储方式。在本文中，选取双链表形式实现双端队列（Deques），选取数组形式实现随机化队列（Randomized Queues）

2、在实现Deques的过程中，在插入元素时要注意插入第一个元素的情况；在删除元素时，要主要删除最后一个元素的情况。

3、在实现Randomized Queues时，要注意next()函数，当随机选中a[i]元素时，应将a[i]元素与a[n-i]元素对换，并接着在前n-i个元素中随机选择。另外还要注意中数的处理方法。

import java.util.Iterator;
import edu.princeton.cs.algs4.StdOut;

public class Deque<Item> implements Iterable<Item> {
	private int count;  // 队列元素个数
	private Node first;
	private Node last;
	private class Node // 元素节点
	{
		Item item;  // 数据
		Node leftNext; // 左链 
		Node rightNext; // 右链
	}
	
	public Deque()                           // 创建一个空的双端队列
	{
	   count = 0;
	   first = null;
	   last = null;
	}
	public boolean isEmpty()                 // 判断队列是否为空？ 
	{
	   return count == 0;
	}
	public int size()                        // 计算队列中元素的个数
	{
	   return count;
	}
	public void addFirst(Item item)          // 在头部加入新元素
	{
		if (item == null) 
		{
			throw new java.lang.IllegalArgumentException("item is null");
		}
		else 
		{
			Node oldfirst = first;
		
			first = new Node();   // 新加入节点元素
			first.item = item;
			first.leftNext = null;
			first.rightNext = null;
		
			if (!isEmpty())// 原队列中有元素
			{ 
				first.rightNext = oldfirst;
				oldfirst.leftNext = first;
			}
			else //原队列中无元素
			{
				last = first;
			}
			count++;
		}
		
	   
	}
	public void addLast(Item item)           // 在尾部加入新元素
	{
		if (item == null) 
		{
			throw new java.lang.IllegalArgumentException("item is null");
		}
		else 
		{
			Node oldLast = last;
		
			last = new Node(); // 新加入节点元素
			last.item = item;
			last.leftNext = null;
			last.rightNext = null;
		
			if (!isEmpty()) // 原队列中有元素
			{
				last.leftNext = oldLast;
				oldLast.rightNext = last;
			}
			else // 原队列中无元素
			{
				first = last;
			}
			count++;
		}
		
	}
	public Item removeFirst()                // 从头部删除并返回该元素
	{
		if (isEmpty()) 
		{
			throw new java.util.NoSuchElementException("the Deque is empty");
		}
		else 
		{
			Node oldfirst = first;
			count--;
			if (count == 0) 
			{
				first = null;
				last = null;
			}
			else
			{
				first = first.rightNext;
				oldfirst.rightNext = null;
				first.leftNext = null;
			}
			return oldfirst.item;
		}
	   
	   
	}
	public Item removeLast()                 // 从尾部删除并返回该元素
	{
		if (isEmpty()) 
		{
			throw new java.util.NoSuchElementException("the Deque is empty");
		}
		else  
		{
			Node oldLast = last;
			count--;
			if (count == 0) 
			{
				first = null;
				last = null;
			}
			else 
			{
				last = last.leftNext;
				oldLast.leftNext = null;
				last.rightNext = null;
			}
			return oldLast.item;
		}
		
	}
	private class MyDequeIteror implements Iterator<Item> //实现迭代器的内部类
	{
		private Node current = first;  //当前节点元素
		public boolean hasNext() 
		{
			return current != null;
		}
		public Item next() 
		{
			if (!hasNext()) 
			{
				throw new java.util.NoSuchElementException("the naxt() is overflow");
			}
			else
			{
				Item item = current.item;
				current = current.rightNext;
				return item;
			}
			
		}
		public void remove() 
		{
			throw new java.lang.UnsupportedOperationException("remove method is unsupported");
		}
	}
	
	public Iterator<Item> iterator()         // 从头到尾依次返回数据
	{
		return new MyDequeIteror();
	}
	
	public static void main(String[] args)   // unit testing (optional)
	{
	   Deque<String> deque = new Deque<String>();
	   deque.addFirst("addfirst1");
	   deque.addFirst("addfirst2");
	   deque.addLast("addlast1");
	   deque.addLast("addlast2");
	   deque.addFirst("addfirst3");
	   for (String s:deque)
		   StdOut.println(s);
	   System.out.println(deque.size());
	   deque.removeFirst();
	   deque.removeLast();
	   deque.addFirst("addfirst4");
	   deque.addFirst("addfirst5");
	   deque.addLast("addlast3");
	   for (String s:deque)
		   StdOut.println(s);
	   System.out.println(deque.size());
	}
}

import java.util.Iterator;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public class RandomizedQueue<Item> implements Iterable<Item> 
{
	private Item[] itemArray;
	private int count;
	
	
	public RandomizedQueue()                 // 创建一个空的RandomizedQueue
	{
		itemArray = (Item[]) new Object[2];
		
		count = 0;
	}
	
	public boolean isEmpty()                 // 判断是否为空?
	{
		return count == 0;
	}
	public int size()                        // 返回队列中元素个数
	{
		return count;
	}
	

	private void resize(int capacity)  // 数组长度加倍
	{
		Item[] copy = (Item[]) new Object[capacity];  // 新的数组 
		for (int i = 0; i < count; i++)
			copy[i] = itemArray[i];
		itemArray = copy;
	}
	
	public void enqueue(Item item)           // 增加元素
	{
	   if (item == null) 
	   {
		   throw new java.lang.IllegalArgumentException("item is null");
	   }
	   else
	   {
		   if (count == itemArray.length) // 数组空间满
		   {
			   resize(2*itemArray.length);
		   }
		   itemArray[count++] = item;
	   }
	}
	
	public Item dequeue()                    // 随机删除并返回一个元素
	{
		if (count == 0) 
		{
			throw new java.util.NoSuchElementException("the queue is empty");
		}
		else 
		{
			int deletei = StdRandom.uniform(0, count); // 随机选取返回节点
			Item itemi = itemArray[deletei];   // itemi 为随机选取元素值
			if (deletei != --count) {
				itemArray[deletei] = itemArray[count]; // 用最后一个元素覆盖掉删除元素位置
				itemArray[count] = null;
			}
			
			if (count > 0 && count == itemArray.length/4)  // 数组有效长度为四分之一，调整数组空间大小
				resize(itemArray.length/2);
			
			return itemi;
		}
		
	}
	public Item sample()                     // 随机返回一个元素（不删除）
	{
		if (count == 0) 
		{
			throw new java.util.NoSuchElementException("the queue is empty");
		}
		else 
		{
			int deletei = StdRandom.uniform(0, count); // 随机选取返回节点
			Item itemi = itemArray[deletei];   // itemi 为随机选取元素值
			return itemi;
		}
	}
	
	private class MyRandomQueueIterator implements Iterator<Item>
	{
		private int current = count; // current表示数组中有效数据个数
		private Item[] iterItemArray;
		public MyRandomQueueIterator() {
			iterItemArray = (Item[])new Object[current]; 
			for (int i = 0; i < current; i++)
				iterItemArray[i] = itemArray[i];
			// StdRandom.shuffle(iterItemArray);
		} 

		public boolean hasNext() 
		{
		
			return current != 0;
		}
		
		public Item next()  // 随机选ai，将ai与a(n-i)位置互换
		{
			if (!hasNext()) 
			{
				throw new java.util.NoSuchElementException("the naxt() is overflow");
			}
			else 
			{
				int findi = StdRandom.uniform(0, current); // 随机选取本次访问位置
				Item itemi = iterItemArray[findi];
				--current;
				iterItemArray[findi] = iterItemArray[current];
				iterItemArray[current] = itemi;
		
				return itemi; // 返回本次选取数据
			}	
		}
		
		
		public void remove() 
		{
			throw new java.lang.UnsupportedOperationException("remove method is unsupported");
		}
	}
	public Iterator<Item> iterator()         // 以随机形式返回数据
	{
	   return new MyRandomQueueIterator();
	}
	public static void main(String[] args)   // unit testing (optional)
	{
	   RandomizedQueue<String> myRandomizedQueue = new RandomizedQueue<String>();
	   myRandomizedQueue.enqueue("add1");
	   myRandomizedQueue.enqueue("add2");
	   myRandomizedQueue.enqueue("add3");
	   myRandomizedQueue.enqueue("add4");
	   myRandomizedQueue.enqueue("add5");
	   myRandomizedQueue.enqueue("add6");
	   myRandomizedQueue.enqueue("add7");
	   myRandomizedQueue.enqueue("add8");
	   myRandomizedQueue.enqueue("add9");
	   myRandomizedQueue.enqueue("add10");
	   myRandomizedQueue.enqueue("add11");
	   System.out.println(myRandomizedQueue.size());
	   System.out.println(myRandomizedQueue.dequeue());
	   System.out.println(myRandomizedQueue.sample());
	   System.out.println(myRandomizedQueue.size());
	   for (int i = 0; i < 10; i++) {
		  // System.out.println(myRandomizedQueue.sample());
	   }
	   
	   for (String s:myRandomizedQueue)
		   StdOut.println(s);
	   

	}
}

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Permutation {
	public static void main(String[] args) {
		int k = Integer.parseInt(args[0]);
		
		RandomizedQueue<String> myRandomizedQueue = new RandomizedQueue<String>();
		while (!StdIn.isEmpty()) 
			myRandomizedQueue.enqueue(StdIn.readString());
		 for (int i = 0; i < k; ++i)
	            StdOut.println(myRandomizedQueue.dequeue());
	}
}