Java实现顺序队列
什么是队列
我们之前说的栈是一种先进后出的数据结构,而队列呢是先进先出数据结构。
也就是说,先放进去的元素,先拿出来。而放进去元素的操作叫做入队,拿出的元素操作我们称之为出队。
日常生活中最简单的栗子就是–排队做核酸。做核酸应该是先来排队的先做对不对,不可能你后来的先做吧。
PS:排队有风险,插队需谨慎。
具体实现
核心代码
IQueue.class
队列接口
/**
* title
* description 队列的接口
*
* @author 三文鱼
* @date2022/3/17
**/
public interface IQueue {
//置空
public void clear();
//判空
public boolean isEmpty();
//队列长度
public int length();
//取队首元素
public Object peek() throws Exception;
//入队
public void offer(Object o) throws Exception;
//出队
public Object poll();
}
SqQueue.class
具体实现
/**
* title
* description
*
* @author 三文鱼
* @date2022/3/20
**/
public class SqQueue implements IQueue {
private Object[] queueElem;
private int front;//指向队首 有元素
private int rear; //指向队尾 没有元素
//初始化
public SqQueue(int maxSize) {
queueElem = new Object[maxSize];
front = rear =0;
}
@Override
public void clear() {
front = rear = 0;
}
@Override
public boolean isEmpty() {
return front == rear;
}
@Override
public int length() {
//要考虑rear < front 这种情况
return (rear - front + queueElem.length)%queueElem.length;
}
//取出元素前需要判空
@Override
public Object peek() throws Exception {
if(rear == front)
return null;
else
return queueElem[front];
}
//入队
@Override
public void offer(Object o) throws Exception {
if((rear + 1) % queueElem.length == front)
System.out.println("队列已满。");
else {
//存入元素
queueElem[rear] = o;
//rear指向下一个存储位置
rear = (rear + 1) % queueElem.length;
}
}
//出队
@Override
public Object poll() {
if(rear == front)
return null;
else {
//取出元素
Object o = queueElem[front];
//front前移
front = (front + 1) % queueElem.length;
return o;
}
}
//遍历输出所有元素
public void display() {
if(!isEmpty()) {
//取余到队尾
for(int i = front; i != rear; i = (i + 1) % queueElem.length) {
System.out.print(queueElem[i].toString() + " ");
}
}else {
System.out.println("队列为空。");
}
}
}
测试
测试代码
/**
* title
* description
*
* @author 三文鱼
* @date2022/3/27
**/
public class QueueTest {
public static void main(String[] args) throws Exception {
SqQueue sqQueue = new SqQueue(5);
sqQueue.offer("零");
sqQueue.offer("一");
sqQueue.offer("二");
sqQueue.offer("三");
sqQueue.offer("四");//rear为保留位置 不能存放元素
sqQueue.display();
System.out.println();
System.out.println("队首元素为:" + sqQueue.peek());
System.out.println("出队元素为:" + sqQueue.poll());
System.out.println("出队操作后的队列元素为:");
sqQueue.display();
System.out.println();
System.out.println("队列长度为:" + sqQueue.length());
sqQueue.offer("四");//由于出队了一个元素 此时front = 1 rear 可以指向0 故而可以存入元素
sqQueue.display();
System.out.println();
System.out.println("队列长度为:" + sqQueue.length());
}
}
测试结果
队列已满。
零 一 二 三
队首元素为:零
出队元素为:零
出队操作后的队列元素为:
一 二 三
队列长度为:3
一 二 三 四
队列长度为:4