队列是一种特殊的线性表,其特殊性体现在只允许在表尾插入元素,表头删除元素。它具有先进先进的特性。插入操作称为入队,删除操作称为出队。进行插入操作的端称为队尾rear,进行删除操作的端称为队头front。
在实际使用中,由于顺序队列经常会因数组下标越界出现”假溢出“问题,所以除了一些简单应用之外,真正实用的队列是循环队列。
队空状态: front=rear=0
队满状态: front=(rear+1)%maxSize
代码如下:
public class CircleSqQueue {
private Object[] queueElement;
private int front;
private int rear;
public CircleSqQueue(int maxSize)
{
queueElement=new Object[maxSize];
front=rear=0;
}
//清空
public void clear()
{
front=rear=0;
}
//判断是否为空
public boolean isEmpty()
{
return front==rear;
}
//长度
public int length()
{
return (rear-front+queueElement.length)%queueElement.length;
}
//队首
public Object peek()
{
if(front==rear)
return null;
else
return queueElement[front];
}
//入队
public void offer (Object x) throws Exception
{
if((rear+1)%queueElement.length==front)
{
throw new Exception("队列已满!");
}
else
{
queueElement[rear]=x;
}
rear=(rear+1)%queueElement.length;
}
//出队
public Object poll ()
{
if(front==rear)
return null;
else
{
Object obj=queueElement[front];
front=(front+1)%queueElement.length;
return obj;
}
}
//打印
public void display()
{
if(front!=rear)
{
for(int i=front; i!=rear; i=(i+1)%queueElement.length)
{
System.out.print(queueElement[i].toString()+" ");
}
System.out.println();
}
}
public static void main(String[] args) throws Exception
{
CircleSqQueue queue=new CircleSqQueue(30);
queue.offer(3);
queue.offer(4);
queue.offer(5);
System.out.print("栈中元素: ");
queue.display();
System.out.println("栈中元素个数: "+queue.length());
int top =(int)queue.peek();
System.out.println("栈顶: "+top);
System.out.print("出队后: ");
queue.poll();
queue.display();
}
}
运行结果:
可以看到,当空间容量为maxSize时,最多只允许存放maxSize-1个数据元素。这样可以解决循环队列的堆空、堆满的判断问题。(判空为front=rear,判满为front=(rear+1)%maxSize)