队列结构
-
今天要学习的队列,也是一种线性结构,他包括两类
- 顺序队列:即使用一组地址连续的内存单元依次保存队列中的数据
- 链式队列:即使用链表形式保存队列中各元素的值
- 队列用图来表示就是这样的
- 从图中可以看出,队列允许在两端进行操作,一段进行添加操作,称为队尾,以便进行删除操作称为队头,他遵循了先进先出FIFO(first in first out)的规则,那这是什么意思呢?拿生活中的例子就是排队,先来的拍前面,前面的先接受服务
-
从上面也可以看出来,队列的基本操作只有两种
- 入队:就是将元素添加到队尾
- 出队:就是将队头的元素移出
- 那么我们来看的一下队列的入队出队流程
- 注意:上图的添加顺序是按照数字的大小顺序添加的,而非从右到左添加的:即添加顺序为0>1>2>3>4>5>6,而不是类似压入栈的顺序:6>5>4>3>2>1>0
-
如上就反映出来一个问题:随着出队和入队的操作,tail指针一直在往后移,也就导致了整个队列在"假变小",因为入队只能在一端进行,所以tail就一直往后移,导致了前面的出队后的位置不能再次利用,那么我们应该怎么去解决这个问题
- 我的想法是:head从0开始计算,数组的Max_Size是最大下标加一的值,所以当head==Max_Size的时候,就代表了head指针已经到数组外了,那么就代表数组内元素全部取完了,是一个空队列,在这个时候,将head和tail都恢复到空队列状态
![markdown_img_paste_20181205103824970]( "markdown_img_paste_20181205103824970")
- 如上图,当tail到达末尾,而head之前有一个空位置,这个现象造成的原因就是先将队列插满,然后取出一个,当遇到这种情况下,在执行插入元素的时候,是插入不进去的,因为tail到达末尾了,所以我们将head到tail之间的元素移动到最前方位置,然后更改head和tail的指针即可,这时候后面就会空出一个位置让新元素插入进来,如下图
- 知道了基本的入队出队规律,下面就是代码实现
顺序队列
import java.util.Arrays;
public class MyQueue<T> {
//头指针
private int head;
//尾指针
private int tail;
//默认大小
private final int MAX_SIZE ;
//存放数据的数组
private Object[] elementData;
public MyQueue() {
this.MAX_SIZE = 5;
elementData = new Object[MAX_SIZE];
}
public MyQueue(int init_size) {
this.MAX_SIZE = init_size;
elementData = new Object[MAX_SIZE];
}
//添加tail
public void put(T element){
//代表空队列
if (head == MAX_SIZE){
//将头指针和尾指针都恢复到空队列状态
tail = 0;
head = 0;
}
//代表tail已经添加到队列末尾了
if (tail == MAX_SIZE){
//不等于0就说明head前面已经有取出的元素了,代表有可用位置
if (head != 0){
//临时数组
Object[] temp = new Object[MAX_SIZE];
//将元素拷贝到临时数组的开始位置,排除原来数组之前的可以空位置
System.arraycopy(elementData,head,temp,0,tail - head);
//拷贝完成赋值
elementData = temp;
//tail就是指向数组有效元素的最后一个下标
tail = MAX_SIZE - head;
//既然已经将数组元素移动到最开始了,那么head肯定是指向最开始的位置了
head = 0;
//然后将本次数据存放在数组最后一个元素中
elementData[tail] = element;
//tail后移
tail ++;
return;
}
//代表head=0并且tail等于最大值,那么就说明存满了
throw new RuntimeException("队列已满");
}
//正常存放
elementData[tail] = element;
tail ++;
}
//拿出head
public T get(){
//空的
if (head >= tail){
return null;
}
//取出头元素
T element = (T) elementData[head];
//释放头元素位置空间
elementData[head] = null;
//head后移
head ++;
//返回数据
return element;
}
@Override
public String toString() {
return Arrays.toString(elementData) + head + " : " + tail;
}
}-
测试
public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<>(); queue.put(1); System.out.println(queue); queue.put(2); System.out.println(queue); queue.put(3); System.out.println(queue); queue.put(4); System.out.println(queue); queue.put(5); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.put(6); System.out.println(queue); queue.put(7); System.out.println(queue); queue.put(8); System.out.println(queue); queue.put(9); System.out.println(queue); queue.put(10); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); System.out.println("-----------------------"); queue.put(11); System.out.println(queue); queue.put(12); System.out.println(queue); queue.put(13); System.out.println(queue); } -
结果
[1, null, null, null, null]0 : 1 [1, 2, null, null, null]0 : 2 [1, 2, 3, null, null]0 : 3 [1, 2, 3, 4, null]0 : 4 [1, 2, 3, 4, 5]0 : 5 [null, 2, 3, 4, 5]1 : 5 [null, null, 3, 4, 5]2 : 5 [null, null, null, 4, 5]3 : 5 [null, null, null, null, 5]4 : 5 [null, null, null, null, null]5 : 5 [6, null, null, null, null]0 : 1 恢复操作 [6, 7, null, null, null]0 : 2 [6, 7, 8, null, null]0 : 3 [6, 7, 8, 9, null]0 : 4 [6, 7, 8, 9, 10]0 : 5 [null, 7, 8, 9, 10]1 : 5 [null, null, 8, 9, 10]2 : 5 [null, null, null, 9, 10]3 : 5 ----------------------- [9, 10, 11, null, null]0 : 3 迁移操作 [9, 10, 11, 12, null]0 : 4 [9, 10, 11, 12, 13]0 : 5
链式队列
-
链式结构就不存在可用空位置了,只要取出直接改变引用即可,同样需要头指针和尾指针,下面是代码实现
public class MyLinkedQueue<T> { private int size; private Node<T> head; private Node<T> tail; private class Node<T>{ private T element ; private Node<T> next; public Node(T element, Node<T> next) { this.element = element; this.next = next; } @Override public String toString() { return String.valueOf(element); } } public MyLinkedQueue() { head = new Node<>(null,null); tail = new Node<>(null,null); } //入队 public void put(T element){ //代表空链表 if (head.next == null){ head.next = new Node<>(element,null); tail = head.next; return; } Node<T> node = new Node<>(element,null); tail.next = node; tail = tail.next; size ++; } //出队 public T get(){ if (head.next == null) { return null; } Node<T> next = head.next; head = head.next; size --; return (T) next; } public int getSize() { return size; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("["); for (Node<T> node = head.next ; node != null ; node = node.next){ builder.append(node.toString()+" "); } return builder.toString(); } } -
测试
public static void main(String[] args) { MyLinkedQueue<Integer> queue = new MyLinkedQueue<>(); queue.put(1); queue.put(2); queue.put(3); queue.put(4); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.put(5); System.out.println(queue); queue.put(6); System.out.println(queue); System.out.println(queue.get()); } -
结果
[1 2 3 4 [2 3 4 [3 4 [4 [ [ [5 [5 6 5
