算法通关村第五关-白银挑战实现队列

队列基础

队列的基本概念和基本特征

队列的特点是节点的排队次序和出队次序按入队时间先后确定，即先入队者先出队，后入队者后出队，即我们常说的FIFO(first in first out)先进先出。队列实现方式也有两种形式，基于数组和基于链表。

更好的理解队列

我们用一个生活中的例子来说明。假如公路上有一条单行隧道，所有通过隧道的车辆只允许从隧道入口驶入，从隧道出口驶出，不允许逆行。

因此，要想让车辆驶出隧道，只能按照它们驶入隧道的顺序，先驶入的车辆先驶出，后驶入的车辆后驶出，任何车辆都无法跳过它前面的车辆提前驶出。

它的特征和行驶车辆的单行隧道很相似。
不同于栈的先入后出，队列中的元素只能先入先出（First In First Out，简称FIFO）。队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。

实现队列

队列的数组实现如下 :

队列的链表实现如下 :

队列的基本操作

数组实现 :

入队

入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，
新元素的下一个位置将会成为新的队尾

出队

出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出
队元素的后一个元素将会成为新的队头

Java中的队列

java代码以链表的形式实现队列 :

我们在自己设计的时候根据自己的需求定义 , 这里简单实现了队列

package src.sl.stack;/*** 队列*/
public class MyQueue {//虚拟节点private  Node dum = new Node(-1,null);private Node last = dum;/*** 节点*/private class Node{int val;Node next;public Node(int val,Node next) {this.val = val;this.next = next;}}/*** 入队* @param value*/public void push(int value){Node node = new Node(value, null);node.next = dum.next;dum.next = node;last = node;}/*** 出队*/public void pull(){if (dum.next == null){throw new RuntimeException("队列为空!!!");}dum.next = dum.next.next;}/*** 遍历队列*/public void forEach(){Node temp = dum.next;while (temp != null){System.out.print(temp.val + " ");temp = temp.next;}}
}

测试 :

package src.sl.stack;public class QueueTest {public static void main(String[] args) {MyQueue myQueue = new MyQueue();myQueue.push(1);myQueue.push(2);myQueue.push(3);myQueue.push(4);myQueue.push(5);myQueue.forEach();myQueue.pull();myQueue.pull();myQueue.pull();myQueue.forEach();}
}

这期就到这里 , 下期见!