【数据结构五】队列和Queue详解

目录

队列

 1.模拟实现一个队列

2.Queue的基本使用

3.循环队列详解

4.双端队列详解

5.分别用栈实现队列，队列实现栈

---

队列

队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾（ Tail/Rear ） 出队列：进行删除操作的一端称为队头（ Head/Front ）

 1.模拟实现一个队列

   队列中存储结构需要用到空间类型的数据结构，这里我们回顾一下什么是数据结构，数据结构研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，其中物理结构即顺序结构和链式结构，因为队列的使用情况多为增加和删除，很少查询，所以我们使用链表来实现一个自己的队列。

public class MyQueue {
    class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    private int usedsize;
    ListNode head;
    ListNode last;
    public MyQueue() {
        usedsize = 0;
        head = last = null;
    }
    public boolean offer(int val) {
        ListNode cur = new ListNode(val);
        if (usedsize == 0) {
            head = last = cur;
            usedsize++;
            return true;
        } else {
            last.next = cur;
            last = cur;
            usedsize++;
            return true;
        }
    }
    public int poll(){
        ListNode cur=head;
        head=head.next;
        usedsize--;
        return cur.val;
    }
    public int peek(){
        return head.val;
    }
    public int size(){
        return usedsize;
    }
    public boolean isEmpty(){
        return usedsize==0;
    }
}

2.Queue的基本使用

在java中，Queue是个接口，底层是通过链表实现的，下面是Queue提供的方法

因为Queue是接口，不能直接实例对象，所以创建对象时需要借助LinkedList，如下：

Queue q = new LinkedList();

 

3.循环队列详解

循环队列，即首尾相连的队列，如下所示：

 在基于顺序结构实现的队列中，数组头部排出数据后，空间便不能在被使用，循环队列的一个好处是我们可以利用这个队列之前用过的空间。

循环队列的设计需要注意几点：

1.如何实现循环：

通过设置front，rear两个前后，指针，每次增加或删除数据通过(front/rear+1)%arr.length即可。

2.需要注意当front==rear时，该队列为空

3.如何辨别队列是否满：

• 可以通过设置size，size等于数组长度则满
• 保留一个空位置，rear+1=front时，队列满

  下面是一道设计循环队列的oj题，大家可以趁热打铁：

  设计循环队列

  4.双端队列详解

  双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

  与Queue一样，Deque在Java中是一个接口。在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

  Deque stack = new ArrayDeque();//双端队列的线性实现
  Deque queue = new LinkedList();//双端队列的链式实现

  5.分别用栈实现队列，队列实现栈

  来自力扣的两道算法题

  1.用队列实现栈

  2.用栈实现队列