【一起学数据结构与算法】深度学习队列

一、什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 – 来源百度
在这里插入图片描述
**队头(front)**：允许删除的一端，称为队首
**队尾(rear)**：允许插入的一端
空队列：不包含任何元素的空表

二、队列的基本操作

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

offer：入队若队列未满，将x加入，使之称为新的队尾。
poll：出队，若队列未空，删除队头元素，并用x返回。
peek：获取队头元素，若队列未空，则将队头元素赋值给x。
isEmpty：判断队列是否为空，若队列为空返回true，否则返回false。
size：获取队列中有效元素个数
2.1 offer - 入队publicclassTest{publicstaticvoidmain(String[] args){Queue<Integer> queue =newLinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3);System.out.println(queue);}}## 2.2 poll - 出队publicclassTest{publicstaticvoidmain(String[] args){Queue<Integer> queue =newLinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3);System.out.println(queue); queue.poll(); queue.poll();System.out.println(queue);}}## 2.3 peek - 获取队头元素publicstaticvoidmain(String[] args){Queue<Integer> queue =newLinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3);System.out.println(queue.peek());}## 2.4 isEmpty - 判断队列是否为空publicstaticvoidmain(String[] args){Queue<Integer> queue =newLinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3);System.out.println(queue.peek());System.out.println(queue.isEmpty());}## 2.5 size - 获取队列长度publicstaticvoidmain(String[] args){Queue<Integer> queue =newLinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3);System.out.println(queue.peek());System.out.println(queue.isEmpty());System.out.println(queue.size());}## 三、队列的模拟实现## 3.1 isEmptypublicbooleanisEmpty(){returnthis.head ==null;}## 3.2 offer/** * 尾插法 * @param val */publicvoidoffer(int val){Node node =newNode(val);if(head ==null){ head = node; last = node;}else{ last.next = node; last = last.next;}}## 3.3 poll/** * 出队 * @return */publicintpoll(){if(isEmpty()){thrownewRuntimeException("队列为空");}int oldVal = head.val;this.head = head.next;return oldVal;}## 3.4 peekpublicintpeek(){if(isEmpty()){thrownewRuntimeException("队列为空");}return head.val;}## 3.5 MyQueue.java@SuppressWarnings({"all"})classNode{publicint val;publicNode next;publicNode(int val){this.val = val;}}publicclassMyQueue{publicNode head;publicNode last;/** * 尾插法 * @param val */publicvoidoffer(int val){Node node =newNode(val);if(head ==null){ head = node; last = node;}else{ last.next = node; last = last.next;}}/** * 出队 * @return */publicintpoll(){if(isEmpty()){thrownewRuntimeException("队列为空");}int oldVal = head.val;this.head = head.next;return oldVal;}publicbooleanisEmpty(){returnthis.head ==null;}publicintpeek(){if(isEmpty()){thrownewRuntimeException("队列为空");}return head.val;}}## 四、循环队列为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。 - 来源百度队列头尾相连的顺序存储结构称为循环队列。使用循环队列的时候，我们会发现一个问题，如何去区分空与满？其实是有三种解决方法的1. 通过添加size属性记录2. 保留一个位置3. 使用flag标记我们使用第二种方法来实现## 4.1 isEmpty - 判空publicbooleanisEmpty(){return front == rear;}## 4.2 isFull - 判满publicbooleanisFull(){if((this.rear+1)% elem.length == front){returntrue;}returnfalse;}## 4.3 front - 队头publicintfront(){if(isEmpty())return-1;return elem[front];}## 4.4 rear - 队尾publicintrear(){if(isEmpty())return-1;int index =-1;if(rear ==0){ index = elem.length-1;}else{ index = rear-1;}return elem[index];}## 4.5 enQueue - 入队publicbooleanenQueue(int value){if(isFull())returnfalse;this.elem[rear]= value; rear =(rear +1)% elem.length;returntrue;}## 4.6 deQueue - 出队publicbooleandeQueue(){if(isEmpty())returnfalse; front =(front+1)% elem.length;returntrue;}## 4.7 MyCircularQueue.javapublicclassMyCircularQueue{publicint[] elem;publicint front;//队头下标publicint rear;//队尾下标publicMyCircularQueue(int k){this.elem =newint[k+1];}/** * 入队 * * @param value * @return */publicbooleanenQueue(int value){if(isFull())returnfalse;this.elem[rear]= value; rear =(rear +1)% elem.length;returntrue;}publicbooleandeQueue(){if(isEmpty())returnfalse; front =(front+1)% elem.length;returntrue;}/** * 得到队头元素 * @return */publicintfront(){if(isEmpty())return-1;return elem[front];}publicintrear(){if(isEmpty())return-1;int index =-1;if(rear ==0){ index = elem.length-1;}else{ index = rear-1;}return elem[index];}publicbooleanisEmpty(){return front == rear;}publicbooleanisFull(){if((this.rear+1)% elem.length == front){returntrue;}returnfalse;}}## 五、双端队列deque（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，相比list增加[]运算符重载。在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。Deque是一个接口，使用时必须创建LinkedList的对象。由于在实际开发中Deque使用的并不是非常多，所以大家只需了解一下即可！## 六、面试题## 6.1 用队列实现栈### 6.1.1 解题思路因为栈是后进先出结构，而我们的队列是先进先出结构，我们可以用两个队列来模拟实现栈的结构，qu1用来进栈，当我们需要出栈时，将qu1里面的元素出栈size-1个元素，就能得到我们的栈顶元素，注意，进栈的时候先判断两个队列谁不为空往哪个队列进，只有两个队列都为空的时候我们的栈也为空。### 6.1.2 代码classMyStack{privateQueue<Integer> qu1;privateQueue<Integer> qu2;publicMyStack(){ qu1 =newLinkedList<>(); qu2 =newLinkedList<>();}publicvoidpush(int x){if(!qu1.isEmpty()){ qu1.offer(x);}elseif(!qu2.isEmpty()){ qu2.offer(x);}else{ qu1.offer(x);}}publicintpop(){if(empty())return-1;if(!qu1.isEmpty()){int size = qu1.size();for(int i =0; i < size-1; i++){int val = qu1.poll(); qu2.offer(val);}return qu1.poll();}if(!qu2.isEmpty()){int size = qu2.size();for(int i =0; i < size-1; i++){int val = qu2.poll(); qu1.offer(val);}return qu2.poll();}return-1;}publicinttop(){if(empty())return-1;if(!qu1.isEmpty()){int val =-1;int size = qu1.size();for(int i =0; i < size; i++){ val = qu1.poll(); qu2.offer(val);}return val;}if(!qu2.isEmpty()){int val =-1;int size = qu2.size();for(int i =0; i < size; i++){ val = qu2.poll(); qu1.offer(val);}return val;}return-1;}publicbooleanempty(){return qu2.isEmpty()&& qu1.isEmpty();}}## 6.2 用栈实现队列### 6.2.1 解题思路1. 用两个栈实现队列，先将元素全部入栈到第一个栈s1当中。2. pop()操作，先判断s1是否为空，如果为空则返回-1，接着判断条件为s2为空,s1不为空，将s1中的元素全部进栈到s2当中，然后return s2.pop()便是出队操作。3. 跟操作2类似，最后返回s2.peek()便可！### 6.2.2 代码classMyQueue{publicStack<Integer> stack1;publicStack<Integer> stack2;publicMyQueue(){ stack1 =newStack<>(); stack2 =newStack<>();}publicvoidpush(int x){ stack1.push(x);}publicintpop(){if(empty())return-1;if(stack2.isEmpty()){while(!stack1.isEmpty()){ stack2.push(stack1.pop());}}return stack2.pop();}publicintpeek(){if(empty())return-1;if(stack2.isEmpty()){while(!stack1.isEmpty()){ stack2.push(stack1.pop());}}return stack2.peek();}publicbooleanempty(){return stack1.isEmpty()&& stack2.isEmpty();}}/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */