队列以及Java实现

布满荆棘的人生 2023-07-24 02:48 13阅读 0赞

# 了解队列 #

在我们的现实生活中会经常看见队列的出现，如：排队买奶茶、叫号服务和餐厅的排号。我们去餐厅准备吃饭时，由于人多只能排队等待就餐或换一家人少的餐厅，餐厅为了让服务更加的好，就会使用排队系统，排队系统完全模拟了人群排队全过程，通过取票进队、排队等待、叫号服务(出队)等功能，代替了人们站队的辛苦。

## 队列的定义 ##

队列(queue)是一种特殊的线性表，是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。进行插入操作的端称为队尾(rear)，进行删除操作的端称为队头(front)。队列中没有数据元素时称为空队列(empty queue)。  
![队列的定义][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70]  
取票时就会入队、排队等待就在队列中、叫号了就出队

## 队列的特点 ##

队列的特点是先进先出。很好理解，早来排队的人肯定早服务。  
有元素出队，如下图所示：  
![第一次出队][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 1]  
![第二次出队][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 2]  
![第三次出队][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 3]

## 队列的基本操作 ##

*  初始队列：创建一个空队列
 *  入队：在队尾添加一个新的数据元素
 *  出队：返回并删除对头的数据元素
 *  取队头元素：获取队头的数据元素
 *  求队列长度：获取队列中数据元素的个数
 *  判断队列是否为空：判断队列中是否有数据元素
 *  判断队列是否为满：判断队列中数据元素是否超过了队列可容纳的最大的数据元素个数

接口定义：

public interface IQueue<E> {
        
        boolean enqueue(E item);    //入队
        E dequeue();                //出队
        E peek();                   //取队头元素
        int size();                 //求队列的长度
        boolean isEmpty();          //判断队列是否为空
        boolean isFull();           //判断队列是否为满
        void clear();               //清空队列
    }

# 队列的实现 #

队列可以用数组或者链表来实现。

## 顺序队列实现队列 ##

*  用一片连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列。Java的数组就是一片连续的存储空间，所以顺序队列的实现会使用数组。
 *  队头设置在最近一个已经离开队列的元素所占的位置，用front表示；
 *  队尾设置在最近一个进入队列的元素位置，用rear表示。
 *  front和rear随着插入和删除而变化。当队列为空时，front=rear=-1。  
    ![顺序队列][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 4]

### 顺序队列溢出问题 ###

*  上溢出：当队满时若进行入队操作，就会产生空间的溢出；
 *  下溢出：当队空时若进行出队操作，也会产生空间的溢出。
 *  假溢出：当移动到数组中下标最大的位置后，队列的空间就用尽了。此时，即使数组下标较小的位置处还有空闲空间，也不能进行入队操作。如上图所示的(d)假溢出。  
    我们怎么解决假溢出呢？我们可以将顺序队列看成是首尾相接的循环结构(一个圆形)。  
    ![循环顺序队列][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 5]
 *  将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列。
 *  当队尾指示器rear到达数组的上限时，如果还有数据入队并且数组的索引号为0的空间空闲时，队尾指示器rear指向数组的0端。所以，队尾指示器的加1操作修改为：  
    rear = (rear+1)%maxsize
 *  当队头指示器front到达数组的上限时，如果还有数据元素出队，队头指示器front指向数组的0端。所以，队头指示器的加1操作修改为：  
    front = (front+1)%maxsize
 *  想象一下，当入队时，rear向前追赶front。出队时，front向前追赶rear。故存在队空和队满时都有rear==front的情况，因此无法通过rear==front来判断是队空还是队满(如下图(e)所示)。  
    解决方法：  
    牺牲存储空间中的一个存储单元，使队空和队满的判断条件不同即可，具体：  
    1）出队时，rear==front时，表示队空，此时不能出队(如下图(b)所示)  
    2）入队时，当(rear+1)%maxsize==front时，表示队满，此时不能入队(如下图(d)所示)  
    ![循环队列][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 6]

### 顺序代码实现 ###

import java.lang.reflect.Array;
    
    public class SeqQueue<E> implements IQueue<E> {
        
        private int maxsize;    //队列的容量
        private E[] data;   //存储循环顺序队列中的数据元素
        private int front;  //指示最近一个已经离开队列的元素所占的位置
        private int rear;   //指示最近一个进入队列的元素的位置
        //初始化队列
        public SeqQueue(Class<E> type,int maxsize){
        
            data = (E[]) Array.newInstance(type,maxsize);
            this.maxsize = maxsize;
            front = rear = -1;
        }
    
        /**
         * 判断队列是否为满
         * @return 如果队列满了返回true，否则返回false
         */
        @Override
        public boolean isFull(){
        
            if ((front == -1 && rear == maxsize - 1)
                    || (rear + 1) % maxsize == front){
        
                return true;
            }else {
        
                return false;
            }
        }
    
        /**
         * 入队
         * @param item 要入队的元素
         * @return 入队成功返回true，失败返回false
         */
        @Override
        public boolean enqueue(E item){
        
            if (!isFull()){
        
                rear = (rear + 1) % maxsize;
                data[rear] = item;
                return true;
            }else{
        
                return false;
            }
        }
    
        /**
         * 判断队列是否为空
         * @return 队列为空返回true，不为空返回false
         */
        @Override
        public boolean isEmpty() {
        
            if (front == rear){
        
                return true;
            }else {
        
                return false;
            }
        }
    
        /**
         * 出队
         * @return 返回出队的元素
         */
        @Override
        public E dequeue(){
        
            if (!isEmpty()){
        
                front = (front + 1) % maxsize;
                return data[front];
            }else{
        
                return null;
            }
        }
    
        /**
         * 取对头元素
         * @return 返回对头元素
         */
        @Override
        public E peek(){
        
            if (!isEmpty()){
        
                return data[(front + 1) % maxsize];
            }else {
        
                return null;
            }
        }
    
        /**
         * 返回队列元素数量
         * @return
         */
        @Override
        public int size() {
        
            return (rear-front+maxsize)%maxsize;
        }
    }

## 链队列实现队列 ##

*  用链式存储结构的队列称为链队列。链队列通常用单链表来表示。
 *  链队列结点的结构与单链表结点的结构一样，由数据域data和引用域next两部分组成。  
    ![链队列][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 7]

### 链表代码 ###

public class QueueNode<E> {
        
        private E data;
        private QueueNode<E> next;
    
        QueueNode(){
        }
    
        public QueueNode(E item) {
        
            data = item;
        }
    
        public E getData() {
        
            return data;
        }
    
        public void setData(E data) {
        
            this.data = data;
        }
    
        public QueueNode<E> getNext() {
        
            return next;
        }
    
        public void setNext(QueueNode<E> next) {
        
            this.next = next;
        }
    }

### 链队列代码实现 ###

public class LinkQueue<E> implements IQueue<E> {
        
        private QueueNode<E> front; //队列头指示器
        private QueueNode<E> rear;  //队列尾指示器
        private int maxsize;        //队列的容量，假如为0，不限容量
        private int size;           //队列数据元素个数
    
        //初始化链队列
        public LinkQueue(){
        
            front = rear = null;
            size = 0;
            maxsize = 0;
        }
    
        public LinkQueue(int maxsize){
        
            super();
            this.maxsize = maxsize;
        }
    
        /**
         * 判断队列是否为空
         * @return 队列为空返回true，不为空返回false
         */
        @Override
        public boolean isEmpty(){
        
            if ((front == rear) && (size == 0)){
        
                return true;
            }else{
        
                return false;
            }
        }
    
        /**
         * 判断队列是否为满
         * @return 如果队列满了返回true，否则返回false
         */
        @Override
        public boolean isFull(){
        
            if (maxsize != 0 && size == maxsize){
        
                return true;
            }else{
        
                return false;
            }
        }
    
        /**
         * 入队
         * @param item 要入队的元素
         * @return 入队成功返回true，失败返回false
         */
        @Override
        public boolean enqueue(E item){
        
            QueueNode<E> newnode = new QueueNode<E>(item);
            if (!isFull()){
        
                if (isEmpty()){
        
                    front = newnode;
                    rear = newnode;
                }else{
        
                    rear.setNext(newnode);
                    rear = newnode;
                }
                ++size;
                return true;
            }else
            {
        
                return false;
            }
        }
    
        /**
         * 出队
         * @return 返回出队的元素
         */
        @Override
        public E dequeue(){
        
            if (isEmpty()) return null;
            QueueNode<E> node = front;
            front = front.getNext();
            if (front == null){
        
                rear = null;
            }
            --size;
            return node.getData();
        }
    
        /**
         * 取对头元素
         * @return 返回对头元素
         */
        @Override
        public E peek(){
        
            if (!isEmpty()){
        
                return front.getData();
            }else
                return null;
        }
    
        /**
         * 返回队列元素数量
         * @return
         */
        @Override
        public int size() {
        
            return size;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70]: /images/20230528/70b8162aaf0d44efb8ba039f119f93ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 1]: /images/20230528/6516b000732348c187b9e28df37394a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 2]: /images/20230528/3489e2b5928e41b4ab35b968347adeca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 3]: /images/20230528/2e0d5279c7da44da8724d73be38b2566.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 4]: /images/20230528/b03b86a5d8084a379fdc4224979e5001.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 5]: /images/20230528/3915eaa191f24dc0a02485bda0e7a06a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 6]: /images/20230528/7d5cf5b7dc6947e2b95441702a71f965.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM2MjY1MA_size_16_color_FFFFFF_t_70 7]: /images/20230528/40e0dd51e95a41b5818cb392eb0b830d.png