数据结构与算法（5）队列
不知道你有没有过在餐厅打饭的经历，我们排的队其实就是我们今天所讲的主题，我们在排队的时候，在队列头部的人打好饭离开，新来的人排在队尾。这就是入队和出队的操作。所以，队列的特性就是先进先出。有了这个概念，就可以开始今天的主题。先给出这篇文章的大致脉络：
首先，使用java语言描述了队列的基本操作，有链式存储和顺序
然后，介绍循环队列和一系列需要注意的知识点
最后，对队列进行一个总结。
OK，开始今天的文章。
一、队列基本操作
1、队列的基本认识
队列的基本特性就是先进先出（FIFO）。也就是第一个进去的元素，第一个出来。现在给出一个标准的定义：
队列就是一个只允许在一端进行插入，在另一端进行删除操作的线性表。
既然是线性表，按照存储方式那就有两种存储方式，基于数组的顺序存储方式和基于链表的链式存储方式。
队列按照实现方式也分为两种：
①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。
②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。
有了对概念分类有了了解，下面我们就是用java代码来实现这些队列
2、顺序队列的实现
顺序队列是基于数组实现的，针对于队列的操作主要有以下几个
（1）插入（2）删除（3）查找元素（4）队列长度（5）是否为空、
我们先给出最基本的操作图解
下面就根据这几个常用的操作使用java代码来实现队列
首先，我们定义一个操作队列的接口
public interface Queue<T> {
//增加元素
void add(T t);
//删除元素
T remove();
//队列长度
int size();
//返回对头元素，并未删掉
T front();
//是否为空
boolean isEmpty();
//是否已满
boolean isFull()
}
然后我们就开始去实现。
插入操作，我们首先要先判断当前队列是否已满，如果满了直接返回。接下来得到当前元素的位置。最后插入元素，再移动位置。
删除操作与插入操作类似，首先要先判断当前队列是否为空，如不为空再移动指针（这里不是指针，指的是指向当前元素位置的标志），删除元素。
判断当前元素是否为空和是否已满类似，只需要判断当前队列的元素数量。
下面给出代码实现。
public class ArrayQueue<T> implements Queue<T>{
private T[] data;
private int size;//元素个数
private int front;//队列中第一个对象的位置
private int rear;//队列中当前对象的位置
//初始化方法
public ArrayQueue() {
data = (T[]) new Object[10];
size = 0;
front =0;
rear = 0;
}
//增加元素
@Override
public void add(T t) {
if(isFull()){
resize();
front = 0;
}
rear = (front+size)%data.length;
System.out.println(rear);
data[rear] = t;
size++;
}
//删除元素
@Override
public T remove() {
if (isEmpty()) {
throw new RuntimeException("队列为空!");
}
T tempData = data[front];
data[front] = null;
front = (front + 1) % (data.length);
size--;
return tempData;
}
//取得队列大小
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
//判断当前队列是否已满
@Override
public boolean isFull(){
return size == data.length;
}
//取得当前队头元素
@Override
public T front() {
if (isEmpty()) {
throw new RuntimeException("队列为空!");
}
return data[front];
}
//扩容
public void resize(){
/*注意重新扩容的时候并不需要去设置size
* 队列的大小并不能通过数组的大小直观的显示出来。
* 但是栈就可以直观的通过数组的大小显示出来*/
T[] tmp = (T[]) new Object[data.length*2];
System.arraycopy(data, 0, tmp, 0, data.length);
data = tmp;
tmp = null;//引用置为空，便于gc处理
}
}
3、链式队列的实现
链式队列与顺序队列不同，每个节点不仅保存当前元素的值，还有指向下一个元素的指针。所以我们先看一下每个节点的图解形式
使用代码来表示就是
public class QueueNode<Item>{
Item item;
QueueNode next;
}
然后我们看链式队列入队和出队的操作
（a）空队列 （b）X入队 （c）y入队 （d）x出队
从上面的操作我们可以看到，实现上面的操作我们需要实现下面的代码
（1）一个指向FIFO头节点的指针
（2）一个指向FIFO尾节点的指针
（3）一个记录节点数的Int变量
private QueueNode first;//指向FIFO头节点的指针
private QueueNode last; //指向FIFO尾节点的指针
private int nodeNum; //记录节点数的Int变量
（4）判断当前队列是否为空
public boolean isEmpty(){
return first == null;
}
（5）队列的大小
public int size(){
return nodeNum;
}
（6）入队和出队操作
//入队
public void enqueue(Item item) {
QueueNode oldLast = last;
last = new QueueNode();
last.item = item;
last.next = null;
if (isEmpty()){
first = last;
} else{
oldLast.next = last;
}
nodeNum++;
}
//出队
public Item dequeue(){
Item item = (Item) first.item;
first = first.next;
if (isEmpty()){
last = null;
}
nodeNum--;
return item;
}
（7）遍历
private class LinkListIterator implements Iterator<Item>{
QueueNode node = first;
@Override
public boolean hasNext(){
return node.next != null;
}
@Override
public Item next() {
Item item = (Item) node.item;
node = node.next;
return item;
}
}
OK。有了上面的这些操作之后，下面给出一个完整的代码
public class Queue<Item> implements Iterable<Item>{
private QueueNode first;
private QueueNode last;
private int nodeNum;
public boolean isEmpty(){
return first == null;
}
public int size(){
return nodeNum;
}
public void enqueue(Item item){
QueueNode oldLast = last;
last = new QueueNode();
last.item = item;
last.next = null;
if (isEmpty()){
first = last;
} else{
oldLast.next = last;
}
nodeNum++;
}
public Item dequeue(){
Item item = (Item) first.item;
first = first.next;
if (isEmpty()){
last = null;
}
nodeNum--;
return item;
}
@Override
public Iterator<Item> iterator(){
return new LinkListIterator();
}
private class LinkListIterator implements Iterator<Item>{
QueueNode node = first;
@Override
public boolean hasNext(){
return node.next != null;
}
@Override
public Item next(){
Item item = (Item) node.item;
node = node.next;
return item;
}
}
}
OK，上面就是顺序队列和链式队列的基本实现。下面我们将介绍一种新的队列循环队列，为什么要有这个队列，我们先要考虑一个问题，也就是我们的队列弹出一个元素，那么这个空间将不能使用。这就是假溢出问题：
为了解决这个问题所以才出现了一个新的队列-循环队列
二、循环队列
我们先给出队列的图解形式
有了循环队列的基本实现，我们思考一个问题，在之前我们可以根据rear直接得到当前队列是否为空和是否已满。那么在循环队列里面还可以这样嘛？当然不可以，我们需要考虑font和rear的位置关系来判断。我们看下面两种情况：
一种是队列为空的时候，front和rear都指向同一个位置。一种是队列已满的时候，front和rear指向的元素紧邻。
我们可以使用下面的公式来判断
我们代码实现一下循环队列
public interface IQueue {
public void clear();
public boolean isEmpty();
public int length();
public Object peek();// 取队首元素
public void offer(Object x) throws Exception;// 入队
public Object poll();// 出队
public void display();
}
然后是接口的实现
public class CircleSqQueue implements IQueue {
private Object[] queueElem;//队列存储空间
private int front;//队首引用，若队列不为空，指向队首元素
private int rear;//队尾引用，若队列不为空，指向队尾的下一个元素
public CircleSqQueue(int maxsize) {
front=rear=0;
queueElem=new Object[maxsize];//分配maxsize个单元
}
@Override
public void clear() {
front=rear=0;
}
@Override
public boolean isEmpty() {
return rear==front;
}
@Override
public int length() {
return (rear-front+queueElem.length)%queueElem.length;
}
@Override
public Object peek() {
if(front==rear){
return null;
}
else{
return queueElem[front];
}
}
@Override
public void offer(Object x) throws Exception {
if((rear+1)%queueElem.length==front){//队满
throw new Exception("队列已满");
}
else{
queueElem[rear]=x;
rear=(rear+1)%queueElem.length;//修改队尾指针
}
}
@Override
public Object poll() {
if(front==rear){
return null;//队列为空
}
else{
Object t=queueElem[front];
front=(front+1)%queueElem.length;
return t;
}
}
@Override
public void display() {
if(!isEmpty()){
for(int i=front;i!=rear;i=(i+1)%queueElem.length){
System.out.println(queueElem[i].toString()+" ");
}
}
else{
System.out.println("此队列为空");
}
}
}
三、总结
对于队列主要在于面试中常见的算法题，因为概念非常容易理解，我们只要根据当前实现的代码进行一些变化就好。谢谢大家的关注。
更多相关文章
- Selenium3自动化测试【12】元素定位认知
- Jquery对选取到的元素显示指定的长度，对于的字符串用“...”显示
- jQuery编程基础精华02（属性、表单过滤器，元素的each，表单选择器，子元
- scrollTop到溢出滚动div中的活动元素
- jQuery使用之（四）处理页面的表单元素
- jQuery遍历祖先元素：parentsUntil
- jQuery入门(2) 获取元素和DOM转换
- 用Jquery控制元素的上下移动 实现排序功能
- jQuery -添加活动类并在单击时从其他元素中删除活动类