赞
踩
队列概念:
队列:是一种只允许在一端进行数据的插入,在另一端进行数据的删除操作的特殊线性表,在
Java
中,队列(Queue)
是个接口,继承自Collection
,底层是通过链表来实现的;
将插入数据的一端称为队尾,删除数据的一端称为对头。
如下图所示:
队列特性:
队列遵循先进先出的原则,(First In First Out) ;
大神比喻:吃进去,拉出来
常用方法:
e
入队列package day20211018; import java.util.LinkedList; import java.util.Queue; public class TestQueue { //测试队列 public static void main(String[] args) { Queue q=new LinkedList(); //入队列:1 2 3 4 q.offer(1); q.offer(2); q.offer(3); q.offer(4); System.out.println(q); //[1, 2, 3, 4] //获取队头元素 System.out.println(q.peek()); //1 //获取队列中元素的个数 System.out.println(q.size()); //4 //出队头2个元素 q.poll(); q.poll(); System.out.println(q); //[3, 4] //判断队列是否为空 if(q.isEmpty()) { System.out.println("队为空"); }else{ System.out.println("队不为空"); } } }
package day20211023; //模拟实现队列--Queue public class Queue <E>{ public static class ListNode<E>{ E value; ListNode<E> next; ListNode<E> prev; public ListNode(E val){ this.value = val; } } ListNode<E> first; //标记表示队头元素 ListNode<E> last; // 标记队尾元素 int size=0; //队列中有效元素的个数 //入队列--offer public boolean offer(E e){ ListNode<E> newNode=new ListNode<>(e); if(first==null){ //队列为空 first=newNode; //last=newNode; }else{ //队列不为空 last.next=newNode; //last=newNode; } last=newNode; size++; return true; } //出队列-poll //实质:删除队头元素 public E poll() { if(0 == size){ return null; } ListNode<E> delNode = first; first = first.next; if(null == first){ last = null; } size--; return delNode.value; } //获取队头元素 public E peek() { if (first == null) { //说明队列中没有元素 return null; } return first.value; } //获取有效元素的个数 public int size(){ return size; } // 判空 public boolean isEmpty(){ return first==null; } public static void main(String[] args) { Queue<Integer> q=new Queue<>(); //测试入队列 1 2 3 4 5 q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5); System.out.println(q.size()); //5 System.out.println(q.peek()); //1 //测试出队列 q.poll(); q.poll(); q.poll(); System.out.println(q.size()); //2 System.out.println(q.peek()); //4 //测试判空 if(q.isEmpty()){ System.out.println("队列为空"); }else{ System.out.println("队列不为空"); } } }
思考
:
在 Java
中,队列是采用链表来实现的,如果采用连续空间是否能满足队列的所有操作的时间复杂度都为O(1)?
分析如下:
假设借助数组的一段连续空间来实现入队列、出队列和获取队头元素的的操作;
如下图所示:入队列:1 2 3 4 5 6
这 6 个元素,直接插入尾部即可,时间复杂度为O(1);
出队列时:由于队列具有先进先出的特性,因此只有该元素成为队头元素才可以实现出队列;
出队列方式一:
保持
front
不动,将后面5个元素整体往前搬移一个位置;再将rear
往前移动一个位置;
注意:虽然这样可以实现出队列,但当有N
个元素时,就需要搬移N-1
次,所以时间复杂度为O(N),不满足要求;
如下图所示:
那么,要保证队列的所有操作中,时间复杂度均为O(1),要怎么实现呢?
方式二:
出队列时,让
front
往后移动一步即可实现;
原因:front
每次标记的都是队头元素,因此当front
往后移动时,就相当于将前面的元素移出队列了;
而且确保了出队列的时间复杂度为O(1),但采用该种方式时,又会导致假溢出
的现象。
假溢出:当想要再该空间进行数据插入时,由于rear
已经指向了空间的末尾,因此不能插入。但实际上前面有三个元素已经出队列了,这部分是有剩余空间的,只是不能被使用而已。把这种现象称为队列的假溢出;
针对上面使用连续空间所出现的假溢出问题,提出了循环队列
循环队列:就是将队列存储空间的最后一个位置绕回到第一个位置,形成逻辑上的环状空间,以便实现队列的循环使用,循环队列也是一种线性的数据结构,其操作表现是基于 FIFO(先进先出)的原则;如下图所示:
如上环形队列图所示:
入队列时
:
将元素放在rear队尾的位置,然后将rear往后移动一步;
出队列时
:front往后移动一步即可;
在上图中的5号位置再插入一个元素时,rear
就指向了front
的位置,那此时,如何判断队列是空还是满呢?
判断循环队列是空还是满的**三种方式
**:
count
来计数当
count
为0 时,循环队列就是空的;
当count
为arr.length时,循环队列为满;
当
front
等于rear
时,队列为空;
当rear
加1
等于rear
时,队列就为满
注意:当队列中的元素存储到最后一个位置时,再插入元素就回到了起始位置,所以队列满时判断条件为:
(rear+1)% arr.length==front
起始状态,将
flag
设为false
入队列时,rear
往下一个位置移动,同时flag=true
;
出队列时:front
往下一个位置移动,同时flag=false
;
当front
等于rear
&&flag
等于false
时,队列为空;
当front
等于rear
&&flag
等于true
时,队列为满;
如何实现一个循环队列?
class MyCircularQueue { int[] array; int front=0; //标记队头元素 int rear=0; //标记队尾元素 int count=0; //判断队列是满还是空 int N; //队列的长度 public MyCircularQueue(int k) { array=new int[k]; N=k; } //入队列 public boolean enQueue(int value) { if(isFull()){ return false; } array[rear]=value; rear++; if(rear==N){ rear=0; } count++; return true; } //出队列 public boolean deQueue() { if(isEmpty()){ return false; } front++; front %= N; count--; return true; } //获取队头元素 public int Front() { if(isEmpty()){ return -1; } return array[front]; } //获取队尾元素 public int Rear() { if(isEmpty()){ return -1; } return array[((rear-1)+N)%N]; } public boolean isEmpty() { return 0==count; } public boolean isFull() { return count==array.length; } }
双端队列(Deque)是指允许两端都可以进行入队和出队操作的队列,底层也是通过
LinkedList
实现的; 集合框架中的结构图如下图所示:
(很重要哦)
注
:下面三道题点开蓝色链接查看原题 !!!
问题描述
:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
解题思路:
使用两个队列
q1
和q2
,q1
用来存储元素,q2
用来作为入栈的辅助队列;
入栈时:先将元素入队到q2
中,然后再将q1
的全部元素出队到q2
中,再将两个队列中的元素互换,则q1
的前端元素和后端为栈顶和栈底元素;
由于每次入栈操作都确保q1
的前端元素为栈顶元素,因此,出栈操作只需要移除q1
的前端元素并返回即可。
获取栈顶元素:只需要获得q1
的前端元素并返回;
判断栈空:只需要q1
是否为空;
class MyStack { //定义两个队列q1,q2,一个用来存储元素,一个用作为辅助队列 Queue<Integer> q1=new LinkedList<>(); Queue<Integer> q2=new LinkedList<>(); public MyStack() { } //入栈 public void push(int x) { q2.offer(x); while (!q1.isEmpty()) { q2.offer(q1.poll()); } Queue<Integer> temp = q1; q1 = q2; q2 = temp; } //出栈 public int pop() { return q1.poll(); } //获取栈顶元素 public int top() { return q1.peek(); } public boolean empty() { return q1.isEmpty(); } }
问题描述
:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
解题思路:
使用两个栈
s1
和s2
,s1
用来模拟入队列,s2
用来模拟出队列;
入队列时:直接将元素放入s1
中;
出队列时:如果s2
是空的,将s1
中的所有元素导入到s2
中,将s2
栈顶元素删除;
获取队头元素:如果s2
是空的,将s1
中的所有元素导入到s2
中,将s2
栈顶元素返回;
代码实现:
class MyQueue { Stack<Integer> s1=new Stack<>(); Stack<Integer> s2=new Stack<>(); public MyQueue() { } //入队列 public void push(int x) { s1.push(x); } //出队列 public int pop() { if(s2.empty()){ //将s1中的所有元素导入到s2中 while(s1.size()>0){ s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if(s2.empty()){ while(s1.size()>0){ s2.push(s1.pop()); } } return s2.peek(); } public boolean empty() { return s1.isEmpty() && s2.isEmpty(); } }
问题描述
:设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
解题思路:
入栈时:
当
S2
不空时,将元素在S1
,S2
中各放入一份;
若S2
不空,就将 val 与S2
栈顶元素进行比较,当val小于等于S2
的栈顶元素时,将val
在S1
和S2
中个放入一份,当val
大于S2
的栈顶元素时,将val 放入S1
中;
出栈时:
当
S1
和S2
栈顶元素相等时,S2
出栈;
S1
每次都要出栈一个元素;
栈顶元素就在S1
中
最小值就在S2
中
class MinStack { Stack<Integer> s1=new Stack<>(); Stack<Integer> s2=new Stack<>(); public MinStack() { } //入栈 public void push(int val) { if(s2.empty() || val<=s2.peek()){ s2.push(val); } s1.push(val); } //出栈 public void pop() { if(s1.peek().equals(s2.peek())){ s2.pop(); } s1.pop(); } public int top() { return s1.peek(); } public int getMin() { return s2.peek(); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。