队列的基本操作

r囧r小猫 2023-09-23 16:15 100阅读 0赞

**目录**

一、什么是队列？

二、用数组实现队列

代码实现：

数组实现的缺点：

三、用链表实现队列

代码实现：

--------------------

## 一、什么是队列？ ##

**·**队列（Queue）是一个先进先出（FIFO-First In First Out）的有序列表。

**·**主要方法：入队（enqueue / offer）和 出队（的dequeue / poll）

![aaddc9a4c53b421bb1539b5526e3758a.png][]

**·**队列的应用场景：（1）线程池 （2）消息队列 （3）广度优先搜索（BFS）图遍历

## 二、用数组实现队列 ##

>     思路：定义一个指向队首指针head、一个指向队尾指针tail，
>     //     入队：元素按添加顺序依次添加，每添加一个元素tail指针往后移动一位，
>     //     出队：出队元素从数组前面依次出去，每出去一个元素head指针后移一位。
> 
> ![286594300ce44e52bfe16bd355ee92a2.png][]

### 代码实现： ###

package Queue;
    
    //用数组实现队列
    //思路：定义一个指向队首指针head、一个指向队尾指针tail，
    //     入队：元素按添加顺序依次添加，每添加一个元素tail指针往后移动一位，
    //     出队：出队元素从数组前面依次出去，每出去一个元素head指针后移一位。
    public class MyArrayQueue<T> {
        //定义一个Object类型数组
        Object[] items;
        //定义一个指向队首指针
        int head;
        //定义一个指向队尾指针
        int tail;
        //定义栈的长度
        int size;
        //定义数组的容量
        int capacity;
    
        //初始化成员变量
        public MyArrayQueue(int capacity) {
            //给数组赋值内存空间
            this.items = new Object[capacity];
            //一开始head、tail都指向数组第一个位置
            this.head = 0;
            this.tail = 0;
            //一开始栈中没有元素
            this.size = 0;
            this.capacity = capacity;
        }
    
        //入队列的方法
        public boolean offer(T item){
            if(tail == capacity){//如果tail等于capacity数组的容量，说明数组满了
                return false;
            }
            //向数组尾部中添加元素
            this.items[this.tail] = item;
            //tail指针向后移动一位
            this.tail++;
            this.size++;
            return true;//添加成功返回true，否则返回false
        }
    
        //出队列的方法
        public T poll(){
            //获取队首的元素
            T item =(T) this.items[this.head];
            //head向数组后面移动一位
            this.head++;
            this.size--;
            return item;
        }
    
    }

> ### 数组实现的缺点： ###
> 
> 1.在整个队列元素都放满之后，面临着扩容的问题。
> 
> 2.元素出队列之后，head会向后面移动，但是head前面的数组空间就浪费了，如果把元素往前移动，同样会有效率低下的问题。

## 三、用链表实现队列 ##

> 思路：用链表实现队列，定义head指针和tail指针，head指针指向链表第一个结点，tail指针指向链表最后一个节点。入队时在链表尾部插入，出队时在链表头部获取。

### 代码实现： ###

package Queue;
    
    //链表实现队列
    //思路：用链表实现队列，定义head指针和tail指针，head指针指向链表第一个结点，
    //     tail指针指向链表最后一个节点。入队时在链表尾部插入，出队时在链表头部获取。
    public class MyLinkedQueue<T> {
        //节点类设计，设计结点内部类
        private class Node{
            T item;//结点存储的数据
            Node next;//下一个结点的地址
            //节点类设计
            public Node(T item, Node next) {
                this.item = item;
                this.next = next;
            }
        }
    
        //定义链表第一个结点位置（队首）
        Node head;
        //定义链表最后一个结点位置（队尾）
        Node tail;
        //定义链表长度
        int size;
    
        public MyLinkedQueue() {
            this.size = 0;
        }
    
        //入队列方法
        public boolean offer(T item){
            //创建插入的结点
            Node node = new Node(item,null);
            if (this.tail == null){//判断链表是否为null，如果为null直接添加,相当于两个指针指向第一个节点
                this.tail = node;
                this.head = node;
            }else {
                //添加到链表的尾部
                this.tail.next = node;
                tail = node;
            }
            this.size++;
            return true;
        }
    
        //出队列方法
        public T poll(){
            if(this.head == null){//如果head==null说明链表没有节点
                throw new RuntimeException("队列中没有元素");
            }
            //出栈直接返回第一个结点即可
            Node node = this.head;
            //移动head到下一个结点
            this.head = this.head.next;
            this.size--;
    
            return node.item;
        }
    
    }

[aaddc9a4c53b421bb1539b5526e3758a.png]: https://img-blog.csdnimg.cn/aaddc9a4c53b421bb1539b5526e3758a.png
[286594300ce44e52bfe16bd355ee92a2.png]: https://img-blog.csdnimg.cn/286594300ce44e52bfe16bd355ee92a2.png