本帖最后由 Jacky_Chen1990 于 2013-5-1 02:59 编辑
以下是我以前的学习笔记,代码应该是以前从网上找的,我看过没有问题,希望可以帮助到你。
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作。
1.队列的顺序存储结构及实现
public class SequenceQueue<T>
{
private int DEFAULT_SIZE = 10;
//保存数组的长度。
private int capacity;
//定义一个数组用于保存顺序队列的元素
private Object[] elementData;
//保存顺序队列中元素的当前个数
private int front = 0;
private int rear = 0;
//以默认数组长度创建空顺序队列
public SequenceQueue()
{
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以一个初始化元素来创建顺序队列
public SequenceQueue(T element)
{
this();
elementData[0] = element;
rear++;
}
/**
* 以指定长度的数组来创建顺序队列
* @param element 指定顺序队列中第一个元素
* @param initSize 指定顺序队列底层数组的长度
*/
public SequenceQueue(T element , int initSize)
{
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
//获取顺序队列的大小
public int length()
{
return rear - front;
}
//插入队列
public void add(T element)
{
if (rear > capacity - 1)
{
throw new IndexOutOfBoundsException("队列已满的异常");
}
elementData[rear++] = element;
}
//移除队列
public T remove()
{
if (empty())
{
throw new IndexOutOfBoundsException("空队列异常");
}
//保留队列的rear端的元素的值
T oldValue = (T)elementData[front];
//释放队列的rear端的元素
elementData[front++] = null;
return oldValue;
}
//返回队列顶元素,但不删除队列顶元素
public T element()
{
if (empty())
{
throw new IndexOutOfBoundsException("空队列异常");
}
return (T)elementData[front];
}
//判断顺序队列是否为空队列
public boolean empty()
{
return rear == front;
}
//清空顺序队列
public void clear()
{
//将底层数组所有元素赋为null
Arrays.fill(elementData , null);
front = 0;
rear = 0;
}
public String toString()
{
if (empty())
{
return "[]";
}
else
{
StringBuilder sb = new StringBuilder("[");
for (int i = front ; i < rear ; i++ )
{
sb.append(elementData.toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2 , len).append("]").toString();
}
}
}
2.循环队列(顺序结构存储实现)
import java.util.Arrays;
public class LoopQueue<T>
{
private int DEFAULT_SIZE = 10;
//保存数组的长度。
private int capacity;
//定义一个数组用于保存循环队列的元素
private Object[] elementData;
//保存循环队列中元素的当前个数
private int front = 0;
private int rear = 0;
//以默认数组长度创建空循环队列
public LoopQueue()
{
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以一个初始化元素来创建循环队列
public LoopQueue(T element)
{
this();
elementData[0] = element;
rear++;
}
/**
* 以指定长度的数组来创建循环队列
* @param element 指定循环队列中第一个元素
* @param initSize 指定循环队列底层数组的长度
*/
public LoopQueue(T element , int initSize)
{
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
//获取循环队列的大小
public int length()
{
if (empty())
{
return 0;
}
return rear > front ? rear - front
: capacity - (front - rear);
}
//插入队列
public void add(T element)
{
if (rear == front
&& elementData[front] != null)
{
throw new IndexOutOfBoundsException("队列已满的异常");
}
elementData[rear++] = element;
//如果rear已经到头,那就转头
rear = rear == capacity ? 0 : rear;
}
//移除队列
public T remove()
{
if (empty())
{
throw new IndexOutOfBoundsException("空队列异常");
}
//保留队列的rear端的元素的值
T oldValue = (T)elementData[front];
//释放队列的rear端的元素
elementData[front++] = null;
//如果front已经到头,那就转头
front = front == capacity ? 0 : front;
return oldValue;
}
//返回队列顶元素,但不删除队列顶元素
public T element()
{
if (empty())
{
throw new IndexOutOfBoundsException("空队列异常");
}
return (T)elementData[front];
}
//判断循环队列是否为空队列
public boolean empty()
{
//rear==front且rear处的元素为null
return rear == front
&& elementData[rear] == null;
}
//清空循环队列
public void clear()
{
//将底层数组所有元素赋为null
Arrays.fill(elementData , null);
front = 0;
rear = 0;
}
public String toString()
{
if (empty())
{
return "[]";
}
else
{
//如果front < rear,有效元素就是front到rear之间的元素
if (front < rear)
{
StringBuilder sb = new StringBuilder("[");
for (int i = front ; i < rear ; i++ )
{
sb.append(elementData.toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2 , len).append("]").toString();
}
//如果front >= rear,有效元素为front->capacity之间、0->front之间的
else
{
StringBuilder sb = new StringBuilder("[");
for (int i = front ; i < capacity ; i++ )
{
sb.append(elementData.toString() + ", ");
}
for (int i = 0 ; i < rear ; i++)
{
sb.append(elementData.toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2 , len).append("]").toString();
}
}
}
}
|