如何使用数组和链表来实现“队列”
与栈一样,队列(Queue)也是一种数据结构,它包含一系列元素。但是,队列访问元素的顺序不是后进先出(LIFO),而是先进先出(FIFO)。
实现一个队列的数据结构,使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。与实现栈的方法类似,队列的实现也有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
下图给出了一种最简单的实现方式,用front来记录队列首元素的位置,用rear来记录队列尾元素往后一个位置。
入队列的时候只需要将待入队列的元素放到数组下标为rear的位置,同时执行rear++,出队列的时候只需要执行front++即可。
/**
* 数组实现队列
*
* @author tian
* @date 2020/4/26
*/
public class MyArrayQueueDemo {
public static void main(String[] args) {
MyQueueDemo<Integer> myQueueDemo = new MyQueueDemo<>();
myQueueDemo.enQueue(1);
System.out.println("-----向队列中添加元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
myQueueDemo.enQueue(2);
System.out.println("-----向队列中添加元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
myQueueDemo.enQueue(3);
System.out.println("-----向队列中添加元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
myQueueDemo.enQueue(4);
System.out.println("-----向队列中添加元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
System.out.println("---------------------------");
myQueueDemo.deQueue();
System.out.println("-----从队列中取出元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
myQueueDemo.deQueue();
System.out.println("-----从队列中取出元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
myQueueDemo.deQueue();
System.out.println("-----从队列中取出元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
myQueueDemo.deQueue();
System.out.println("-----从队列中取出元素-----");
System.out.println("队列头元素 = " + myQueueDemo.getFront());
System.out.println("队列尾元素 = " + myQueueDemo.getBack());
System.out.println("队列大小 = " + myQueueDemo.size());
}
}
class MyQueueDemo<T> {
private List<T> arrayList = new ArrayList<>();
private int front;
private int rear;
public MyQueueDemo() {
this.front = 0;
this.rear = 0;
}
public boolean isEmpty() {
return front == rear;
}
public int size() {
return rear - front;
}
//获取对手元素
public T getFront() {
if (isEmpty()) {
return null;
}
return arrayList.get(front);
}
//获取队列尾部元素
public T getBack() {
if (isEmpty()) {
return null;
}
return arrayList.get(rear - 1);
}
//删除队列中头部元素
public void deQueue() {
if (rear > front) {
front++;
} else {
System.out.println("队列已经不存在元素了");
}
}
//把新元素添加到队列中(队列尾部)
public void enQueue(T item) {
arrayList.add(item);
rear++;
}
}
运行结果
OK,自此,使用数组实现队列已经搞定。
出队列后数组前半部分的空间不能够充分地利用,解决这个问题的方法为把数组看成一个环状的空间(循环队列)。当数组最后一个位置被占用后,可以从数组首位置开始循环利用。
采用链表实现队列的方法与实现栈的方法类似,分别用两个指针指向队列的首元素与尾元素,如下图所示。用pHead来指向队列的首元素,用pEnd来指向队列的尾元素。
在上图中,刚开始队列中只有元素1、2和3,当新元素4要进队列的时候,只需要上图中(1)和(2)两步,就可以把新结点连接到链表的尾部,同时修改pEnd指针指向新增加的结点。出队列的时候只需要(3)这一步,改变pHead指针使其指向pHead→next,此外也需要考虑结点所占空间释放的问题。
/**
* @author tian
* @date 2020/4/26
*/
class QueueNode<T> {
T data;
QueueNode<T> next;
}
class MyNodeQueue<T> {
private QueueNode<T> head;
private QueueNode<T> end;
//初始化队列
public MyNodeQueue() {
end = head = null;
}
boolean isEmpty() {
return head == null;
}
int size() {
int size = 0;
QueueNode<T> temp = head;
while (temp != null) {
temp = temp.next;
size++;
}
return size;
}
//入队
void enQueue(T t) {
QueueNode<T> temp = new QueueNode<>();
temp.data = t;
temp.next = null;
if (head == null) {
head = end = temp;
} else {
end.next = temp;
end = temp;
}
}
//出队
void deQueue() {
if (head == null) {
System.out.println("不存在元素,出队失败");
return;
}
head = head.next;
if (head == null) {
end = null;
}
}
//获取队首元素
T getFront() {
if (head == null) {
System.out.println("队列中不存在元素,获取为空");
return null;
}
return head.data;
}
//获取队尾元素 T getBack() { if (end == null) {
System.out.println("队列中不存在元素,获取失败");
return null;
}
return end.data;
}
}
public class MyNodeQueueDemo {
public static void main(String[] args) {
MyNodeQueue<Integer> queue = new MyNodeQueue<>();
queue.enQueue(1);
System.out.println("向队列中添加元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
queue.enQueue(2);
System.out.println("向队列中添加元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
queue.enQueue(3);
System.out.println("向队列中添加元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
queue.enQueue(4);
System.out.println("向队列中添加元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
System.out.println("------------------");
queue.deQueue();
System.out.println("从队列中取出元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
queue.deQueue();
System.out.println("从队列中取出元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
queue.deQueue();
System.out.println("从队列中取出元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
queue.deQueue();
System.out.println("从队列中取出元素");
System.out.println("头 元素=" + queue.getFront());
System.out.println("尾 元素=" + queue.getBack());
System.out.println("大小=" + queue.size());
}
}
运行结果
OK,使用链表实现队列到此就搞定。
显然用链表来实现队列有更好的灵活性,与数组的实现方法相比,它多了用来存储结点关系的指针空间。此外,也可以用循环链表来实现队列,这样只需要一个指向链表最后一个元素的指针即可,因为通过指向链表尾元素可以非常容易地找到链表的首结点。