来源：来源works-application
1、要求实现一个FIFO队列；能够查看最大值、最小值、中位数；队列中的每个对象能够比较大小。
接口1：
package jp.co.worksap.recruiting;
public interface ExamPeekableQueue<E extends Comparable<E>> {
public void enqueue(E e);
public E dequeue();
public E peekMedian();
public E peekMaximum();
public E peekMinimum();
public int size();
}
代码：
package jp.co.worksap.recruiting;
import java.util.*;
public class ExamPeekableQueueImpl<E extends Comparable<E>> implements ExamPeekableQueue<E> {
private LinkedList<E> q = null;
public ExamPeekableQueueImpl(){
q = new LinkedList<E>();
}
@Override
public E dequeue() {
if(q.isEmpty())
{
throw new NoSuchElementException();
}
return q.remove();
}
@Override
public void enqueue(E e) {
if(e==null)
{
throw new IllegalArgumentException();
}
q.offer(e);
}
@Override
public E peekMaximum() {
E e = q.peek();
for(Iterator it = q.iterator();it.hasNext();)
{
E tmp = (E)it.next();
if(e.compareTo(tmp)<=0)
e = tmp;
}
return e;
}
@Override
public E peekMedian() {
Collections.sort(q);
E e = null;
int i = 0;
for(Iterator it = q.iterator();it.hasNext();)
{
if(i<q.size()/2+1)
{
e = (E) it.next();
i++;
}
else
{
break;
}
}
return e;
}
@Override
public E peekMinimum() {
E e = q.peek();
for(Iterator it = q.iterator();it.hasNext();)
{
E tmp = (E)it.next();
if(e.compareTo(tmp)>=0)
e = tmp;
}
return e;
}
@Override
public int size() {
// TODO Auto-generated method stub
return q.size();
}
@SuppressWarnings("unchecked")
public static void main(String[] args){
ExamPeekableQueueImpl eq = new ExamPeekableQueueImpl();
eq.enqueue(new Integer(7));
eq.enqueue(new Integer(1));
eq.enqueue(new Integer(3));
eq.enqueue(new Integer(3));
eq.enqueue(new Integer(5));
eq.enqueue(new Integer(1));
eq.enqueue(new Integer(2));
eq.enqueue(new Integer(4));
eq.enqueue(new Integer(3));
System.out.println(eq.peekMinimum());
System.out.println(eq.peekMedian());
System.out.println(eq.peekMaximum());
System.out.println(eq.size());
}
}
2、 要求实现一个immutable的队列
接口2：
package jp.co.worksap.recruiting;
public interface ExamImmutableQueue<E> {
public ExamImmutableQueue<E> enqueue(E e);
public ExamImmutableQueue<E> dequeue();
public E peek();
public int size();
}
代码实现：
package jp.co.worksap.recruiting;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class ExamImmutableQueueImpl<E> implements ExamImmutableQueue<E> {
private List<E> q;
public ExamImmutableQueueImpl(){
q = new ArrayList<E>();
}
public ExamImmutableQueueImpl(List<E> q){
this.q = q;
}
@Override
public ExamImmutableQueue<E> dequeue() {
if(q.isEmpty()){
throw new NoSuchElementException();
}
List<E> clone = new ArrayList<E>(q);
clone.remove(0);
return new ExamImmutableQueueImpl<E>(clone) ;
}
@Override
public ExamImmutableQueue<E> enqueue(E e) {
if(e==null){
throw new IllegalArgumentException();
}
List<E> clone = new ArrayList<E>(q);
clone.add(e);
return new ExamImmutableQueueImpl<E>(clone) ;
}
@Override
public E peek() {
if(q.isEmpty()){
throw new NoSuchElementException();
}
return q.get(0);
}
@Override
public int size() {
return q.size();
}
@SuppressWarnings("unchecked")
public static void main(String[] args){
ExamImmutableQueueImpl eiq = new ExamImmutableQueueImpl();
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(7));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(1));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(3));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(3));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(5));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(1));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(2));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(4));
eiq = (ExamImmutableQueueImpl) eiq.enqueue(new Integer(3));
System.out.println(eiq.peek());
}
}
PS：这是work-application的试题，要求分别实现接口1、接口2构造两个队列，要求队列的操作效率尽可能高，但是很显然上文给出的效率肯定不高，但是一不知道怎么改进？如果不使用集合类效率会不会更高点呢？？