队列

作者: 一张橙 | 来源:发表于2018-11-05 21:43 被阅读0次

队列
队列
iOS底层-- GCD源码分析(1)-- dispatch_qu
队列，异步，同步，线程通俗理解
GCD基础总结一
OC多线程
GCD
数据结构第三篇队列
利用链表实现队列
Git 常用操作命令(持续更新)

队列是最为经典的先进先出（FIFO）形式的数据结构。

所谓的先进先出是形象地来说就好比一个取餐窗口的队伍，排队取餐的人们构成了取餐队伍的元素集合。排进队伍的动作称为“入队”，即元素添加到队伍的尾部，取到餐后离开队伍的动作称为“出队”，即元素从队的头部移除。而这一生活中的现象在数据结构中抽象来说呢就是队列了。

首先我们来说明白“单向队列”。

单向队列

这是一种最简单的队列，它的一切属性都与现实生活中的现象重合，因此一点儿也不抽象。我们来分析一下一个队列需要做哪些事情，以及完成这些事情需要哪些属性。依据文章开头的分析，我们可以得到以下初步的结论。

队列最重要的操作是“入队”、“出队”。
需要定义一个基础容器存放数据，不论此处使用数组或者链表都可，为了方便说明，下方代码中我们使用ArrayList<Integer>，泛型指定为Integer是为了更简洁地说明。
我们至少需要标记“队头”，即队伍第一个元素是哪个，我们引入一个指针永远地指向队伍的第一个元素，不论队列做了多少次入队、出队的操作。
我们在入队的时候需要判断这个队伍是否已经满了，如果满了显然不能再入队了，因此队列还需要判满方法。
同样地，我们需要在出队的时候判断是否队列空了，队列都空了再出队显然不合理。

以下是代码部分：

class MyQueue{
        
    //定义存储数据的容器
    private List<Integer> data;
    
    //队头指针，始终指向队伍自对头开始数第一个元素
    private Integer pStart;
    
    //构造器
    public MyQueue(){
        
        //初始化一个只允许存储Integer类型的ArrayList，这样此队列就是无限长的，且入队无需判断是否队伍满了
        data = new ArrayList<Integer>();
        //初始化时头指针指向队列位置0
        pStart = 0;
    }
    
    //入队
    public boolean enQueue(Integer el){
        
        //入队，在队伍尾部添加需要入队的元素
        data.add(el);
        //添加成功嚷嚷一声
        return true;
    }
    
    //出队
    public boolean deQueue(){
        
        //判空，如果队伍都空则说明没有元素可以出队了
        if(!isEmpty){
            //移除头指针指向的元素
            data.remove(pStart);
            //此时第n+1元素成了队头元素，故将指针后移一位
            pStart ++;
            //惯例嚷嚷一声
            return true;
        }
        //队伍空了，就喊一声没有元素了
        return false;
    }
    
    
    //判空
    public boolean isEmpty(){
        
        //什么时候才代表队伍空了？是List 的size为0吗这只是一种情况，假设建了一个长度为3的ArrayList，
        //但是一个元素都没有，此时我们依然说这个队伍是空的。但是如果我们假设队伍有限长，当永远指向头元素的指针指
        return pStart >= data.size();
    }
}

循环队列

单向队列有一个显而易见的缺陷，它的长度是无限增长的，且一旦队头出列了后，队头指针后移，则原先保存队头元素的位置被弃用了，这是一种很浪费空间的行为。为了提高空间的利用率，我们引入循环队列。所谓循环队列，就是将在出队操作执行后不再使用的空间作为队列的后方空间，将来在入队时，以之前执行出队操作的次序依次进行入队操作。

为了达成上述目的，需要构建以下属性：

定长数组，作为存储数据的容器。//int [] data;
头指针，指向队列的头部。 // int pStart;
尾指针，指向队列的尾部。 //int pEnd;
容器容量，存储容器（定长数组）的大小。 //int size;
以下是循环队列的代码实现：


class CricleQueue{
    
    private int[] data; //容器
        
    private int pStart; //头指针
    
    private int pEnd; //尾指针
    
    private int size; //容器容量
    
    
    //构造器
    public CricleQueue(int k){
        
        data = new int[k];  //初始化容器为k容量的int数组
        pStart = -1;    //初始化头指针
        pEnd = -1;  //初始化尾指针
        size = k;   //将容器容量给到变量size，方便后面使用
    }
    
    //入队
    public boolean enQueue(int el){
        
        //先判满
        if(isFull()){
            return false;
        }
        
        //第一次执行入队操作
        if(pStart == -1 && pEnd == -1){
            pStart = 0;
            pEnd = (pEnd + 1)%size;     //入队操作需要关注的是尾指针的移动
            data[pEnd] = el;
            return true;
        }
        
        pEnd = (pEnd + 1)%size;
        data[pEnd] = el;
        return true;
    }
    
    //出队
    public boolean deQueue(){
        
        //先判空
        if(isEmpty()){
            return false;
        }
        
        //如果是最后一个元素准备出队了
        if(pStart == pEnd){
            
            pStart = -1;    //将两个指针重置为初始化状态
            pEnd = -1;
            return true;
        }
        
        pStart = (pStart + 1)%size; //出队操作需要关注头指针的移动，空出来的位置的废弃元素等待将来元素入队覆盖而不必理会
        return true;
    }
    
    //获取队头元素
    public int getHeadEl(){
        //队中必须还有元素
        if(!isEmpty()){
            
            return data[pStart];
        }
        return -1;  //否则无元素可出
    }
    
    //获取队尾元素
    public int getTailEl(){
        if(!isEmpty()){
            
            return data[pEnd];
        }
        return -1;
    }
    
    //判空
    public boolean isEmpty(){
        
        return pStart == -1 && pEnd == -1;  //指针初始化状态
    }
    
    //判满
    public boolean isFull(){
        
        return pStart == (pEnd + 1)%size; //两个指针的位置关系通过其中一个指针位置与数组长度取余得到。
    }
    
}
```/