数据结构青铜到王者第八话---队列(Queue)

目录

一、队列(Queue)

1、概念

2、队列的使用

 3、队列模拟实现

 4、循环队列

4.1数组下标循环的小技巧（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

4.2如何区分空与满

4.3设计循环队列

二、双端队列 (Deque)

三、用队列实现栈。

四、用栈实现队列。

一、队列(Queue)

1、概念

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

2、队列的使用

        在Java中，Queue是个接口，底层是通过链表实现的。

        #注：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) { Queue q = new LinkedList(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5);  // 从队尾入队列 System.out.println(q.size()); System.out.println(q.peek()); // 获取队头元素 q.poll(); System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 if(q.isEmpty()){ System.out.println(\"队列空\"); }else{ System.out.println(q.size()); } }

 3、队列模拟实现

        队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。

public class Queue { // 双向链表节点 public static class ListNode{ ListNode next; ListNode prev; int value; ListNode(int value){ this.value = value; } } ListNode first; // 队头 ListNode last; // 队尾 int size = 0; // 入队列---向双向链表位置插入新节点 public void offer(int e){ ListNode newNode = new ListNode(e); if(first == null){ first = newNode; // last = newNode; }else{ last.next = newNode; newNode.prev = last; // last = newNode; } last = newNode; size++; } // 出队列---将双向链表第一个节点删除掉 public int poll(){ // 1. 队列为空 // 2. 队列中只有一个元素----链表中只有一个节点---直接删除 // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除 int value = 0; if(first == null){ return null; }else if(first == last){ last = null; first = null; }else{ value = first.value; first = first.next; first.prev.next = null; first.prev = null; } --size; return value; } // 获取队头元素---获取链表中第一个节点的值域 public int peek(){ if(first == null){ return null; } return first.value; } public int size() { return size; } public boolean isEmpty(){ return first == null; } }

 4、循环队列

        实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。

4.1数组下标循环的小技巧
（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

（2）下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

4.2如何区分空与满

（1）通过添加 size 属性记录

（2）保留一个位置

（3）使用标记

4.3设计循环队列

class MyCircularQueue { public int front; // 队头指针，指向队列的第一个元素 public int rear; // 队尾指针，指向队列最后一个元素的下一个位置 public int[] elem; // 用于存储队列元素的数组 // 构造函数，初始化循环队列，容量为k public MyCircularQueue(int k) { elem = new int[k+1]; // 因为循环队列会浪费一个空间来判断满队列，所以数组大小为k+1 } // 入队操作：向队列尾部插入一个元素value public boolean enQueue(int value) { if(isFull()){ // 如果队列已满，插入失败 return false; } elem[rear] = value; // 将value放入队尾 rear = (rear+1)%elem.length; // 队尾指针后移，取模实现循环 return true; // 插入成功 } // 出队操作：删除队列头部的元素 public boolean deQueue() { if(isEmpty()){ // 如果队列为空，删除失败 return false; } front = (front+1)%elem.length; // 队头指针后移，取模实现循环 return true; // 删除成功 } // 获取队头元素 public int Front() { if(isEmpty()) { // 队列为空时返回-1 return -1; } return elem[front]; // 返回队头元素 } // 获取队尾元素 public int Rear() { if(isEmpty()) { // 队列为空时返回-1 return -1; } // 计算队尾元素的位置：如果rear为0，则队尾在数组末尾；否则为rear-1 int index = (rear == 0) ? elem.length-1 : rear-1; return elem[index]; // 返回队尾元素 } // 判断队列是否为空 public boolean isEmpty() { return rear == front; // 队头和队尾指针相等时队列为空 } // 判断队列是否已满 public boolean isFull() { return (rear+1)%elem.length == front; // 队尾指针的下一个位置是队头时队列已满 }}

二、双端队列 (Deque)

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

        Deque是一个接口，使用时必须创建LinkedList的对象。

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

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

三、用队列实现栈。

（225. 用队列实现栈 - 力扣（LeetCode））

        我们首先思考一下，队列和栈有什么区别。队列是先进先出的，而栈是先进后出的。我们可以发现，一个队列是无法实现一个栈的。因此我们定义两个队列qu1，qu2。

        模拟出栈，先判断哪个队列为空，另一个队列中前n-1个进入的元素进入到空队列中，最后一个元素再出队列。

        模拟入栈，每次入到不为空的队列当中；如果开始两个队列都为空，则默认放到qu1中。

import java.util.LinkedList;import java.util.Queue; public class MyStack { private Queue qu1; private Queue qu2; public MyStack() { qu1 = new LinkedList(); qu2 = new LinkedList(); } //模拟入栈 public void push(int x) { if(empty()){ qu1.offer(x); return; } if(!qu1.isEmpty()){//qu1不为空，qu2为空 qu1.offer(x); }else{//qu2不为空，qu1为空 qu2.offer(x); } } //栈顶元素出栈 public int pop() { if(empty()) { return -1; } if(!qu1.isEmpty()) { int size = qu1.size(); while(size-1 != 0) { qu2.offer(qu1.poll()); size--; } return qu1.poll(); }else { int size = qu2.size(); while(size-1 != 0) { qu1.offer(qu2.poll()); size--; } return qu2.poll(); } } //返回栈顶元素 public int top() { if(empty()){ return -1; } if(! qu1.isEmpty()){ int size = qu1.size(); int tmp = -1; while(size != 0){ tmp = qu1.poll(); qu2.offer(tmp);//size前面的元素出队列，并进入另一个队列 size--; } return tmp; }else{ int size = qu2.size(); int tmp = -1; while(size-1 != 0){ tmp = qu2.poll(); qu1.offer(tmp); size--; } return tmp; } } //两个队列都是空，说明模拟栈是空的 public boolean empty() { return qu1.isEmpty() && qu2.isEmpty(); }}

四、用栈实现队列。

（232. 用栈实现队列 - 力扣（LeetCode））

        同上，用栈实现队列，也得同时使用两个栈，并且只能使用标准栈操作。

        模拟出队列，我们先让元素进入s1中，然后全部进入s2中，再从s2中弹出元素。这样做的好处是可以只使用s2中的元素。如果s2是空的，那么看s1是不是空？s1不是空，s1中的元素全部倒出来。

        模拟入队列，全部默认放入第一个栈中。

import java.util.Stack; public class MyQueue { private Stack s1; private Stack s2; public MyQueue() { s1 = new Stack(); s2 = new Stack(); } //模拟入队列 public void push(int x) { s1.push(x); } //出队列 public int pop() { if(empty()){ return -1; } if(s2.isEmpty()){ //把s1中的数据全部倒出 while(! s1.isEmpty()){ s2.push(s1.pop()); } } return s2.peek(); } //获取队头元素 public int peek() { if(empty()){ return -1; } if(s2.isEmpty()){ //把s1中的数据全部倒出 while(! s1.isEmpty()){ s2.push(s1.pop()); } } return s2.peek(); } //两个栈都为空，则队列为空 public boolean empty() { return s1.isEmpty() && s2.isEmpty(); }}