Collection与数据结构 Stack与Queue(二):队列与Queue
1. 队列
1.1 概念
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）.
这样的数据结构有些像我们平时在食堂排队打饭的操作.
1.2 队列的使用
在Java中,Queue是一个接口,底层是通过链表来实现的.所以在实例化的时候,必须用LinkedList来实例化.
| 方法 | 功能 |
|---|---|
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
- offer和poll操作的时间复杂度都是O(1),所以在使用单向链表实现队列的时候,必须使用头插尾插.如果说是尾删头插的话,删掉的时候不知道该结点的pre是谁(因为是单向链表),所以要重新遍历寻找最后一个结点,时间复杂度就不是O(1).
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()); } }1.3 队列的模拟实现
我们根据队列底层的逻辑:使用LinkedList来实现队列.
public class MyQueue { public static class ListNode{ ListNode next; ListNode pre; int val; public ListNode(int val) { this.val = val; } } ListNode first; ListNode last; int size = 0; /** * 入队列,在双向链表的尾部插入新结点 * @param e */ public void offer (int e){ ListNode listNode = new ListNode(e); if (first == null){ first = listNode; last = listNode; }else { listNode.pre = last; last.next = listNode; last = listNode; } size++; } /** * 出队列,在链表头部删除结点 * @return */ public int poll(){ int value = 0; if (first == null){ return -1; } else if (first == last) { value = first.val;//需要先把value记录下来,以便最后返回 first = null; last = null; //return value;//不可以直接返回first.val,否者空指针异常 }else { value = first.val; first = first.next; first.pre.next = null; first.pre = null; //return value; } size --;//在返回之前size-- return value; } /** * 返回队头元素 * @return */ public int peek(){ if (first == null){ return -1; } return first.val; } /** * 获取队列大小 * @return */ public int size(){ return this.size; } /** * 判断队列是否为空 * @return */ public boolean isEmpty(){ return size == 0; } }1.4 环形队列
在实际中,我们经常用的一种队列还有一种,叫做循环队列,环形队列通常由数组实现.
既然是环形队列,所以我们在存放元素的时候,就要按循环下标的方式来添加元素,数组下标循环公式:
(当前位置+偏移量)%数组大小.
eg:
区分空与满的问题:
在一个队列中,一定会有队头和队尾,在队列空的时候,队列头和尾指向同一位置:
在队列满的时候,头和尾也会指向同一位置:
如果按上述的方法,我们就没有办法区别队列是空还是满了,那么我们提供以下解决方案:
- 通过添加size属性
- 保留一个位置(牺牲空间法)
- 使用标记
在下面,我们只以第二种方法为例:我们令头为front,尾为rear
在满的时候,我们通过把最后一个位置空出来,以front = (rear+1)%array.length来表示队列满.
下面我们来通过上述方式设计循环队列:
OJ链接
class MyCircularQueue { public int front;//队头 public int rear;//队尾 public int[] elem; public MyCircularQueue(int k) { front = 0; rear = 0; elem = new int[k+1];//使用牺牲空间法来区分满和空,初始化空间的时候就要多一个空间 } public boolean enQueue(int value) { if(isFull()){ return false;//队列为满,返回false }else{ elem[rear] = value; rear = (rear+1)%elem.length; } return true; } public boolean deQueue() { if(front == rear){ return false;//队列为空,删除失败 }else{ elem[front] = 0; front = (front+1)%elem.length; } return true; } public int Front() { if(rear == front){ return -1; }else{ return elem[front]; } } public int Rear() { if(rear == front){ return -1; }else{ return rear == 0? elem[elem.length-1]:elem[rear-1]; }//分两种情况,一种是rear为0,一种是不为0的时候,为0返回数组的最后一个元素,否者返回rear指向的前一个元素 }//队尾放的最后一个元素总是比rear指针向前一个位置,因为在插入操作的时候,最后进行了rear = (rear+1)%elem.length操作 public boolean isEmpty() { if(rear == front){ return true;//头和尾重合的时候,就是空 }else{ return false; } } public boolean isFull() { if(front == (rear+1)%elem.length){ return true;//中间空出一个空间的时候,就是满 } return false; } } }2. 双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口,必须使用LinkedList实例化对象.
Deque stack = new ArrayDeque();//双端队列的线性实现 Deque queue = new LinkedList();//双端队列的链式实现
3. 队列与栈的综合
3.1 用栈实现队列
在用栈实现队列的时候,核心思想把握住一句话:出队列的顺序和出栈的顺序相反,对头的元素对应栈底的元素.
OJ链接
class MyQueue2 {//需要用两个栈来实现一个队列 Stack stack1; Stack stack2; public MyQueue2() { stack1 = new Stack(); stack2 = new Stack(); } public void push(int x) { stack1.push(x);//入队列的时候就入第一个栈就可以 } public int pop() { int value = 0; if (stack2.empty()){//如果stack2为空的时候,就把stack1的元素全部倒到2中 //是因为出队列的顺序和出栈的顺序相反,对头的元素对应栈底的元素 while(!stack1.empty()){ stack2.push(stack1.pop()); } value = stack2.peek(); stack2.pop();//出2的栈顶元素 }else {//如果不为空,直接出栈顶元素 value = stack2.peek(); stack2.pop(); } return value; } public int peek() { int value = 0; if (stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.pop()); } value = stack2.peek(); }else { value = stack2.peek(); } return value;//和pop原理一样,只不过没有元素出栈 } public boolean empty() {//两个栈都为空的时候,队列为空 if (stack1.empty() && stack2.empty()){ return true; }else { return false; } } }3.2 用队列实现栈
这道题的核心是:队列中最后一个元素对应栈顶的元素,所以要让队尾的元素露出来.
OJ链接
class MyStack { Queue queue1; Queue queue2;//使用两个队列来完成栈的实现 public MyStack() { queue1 = new LinkedList(); queue2 = new LinkedList(); } public void push(int x) { if (empty()){//空就往任意一个队列中添加 queue1.offer(x); return;//记得返回 } if (!queue1.isEmpty()){//谁不为空,就往谁添加 queue1.offer(x); }else { queue2.offer(x); } } public int pop() { if (empty()){ return -1; } if (queue1.isEmpty()){ while(queue2.size() != 1){//poll到队列中只有1个元素,目的是让队列中的元素与栈顶元素对应起来 queue1.offer(queue2.poll()); } return queue2.poll();//弹出只剩一个元素的队列 }else { while(queue1.size() != 1){ queue2.offer(queue1.poll()); } return queue1.poll(); } } public int top() { if (empty()){ return -1; } int value = 0;//利用vlaue保存peek的值 if (queue1.isEmpty()){ while(queue2.size() != 1){ queue1.offer(queue2.poll()); } value = queue2.peek(); queue1.offer(queue2.poll());//先peek保存,再poll到另一个队列中 return value; }else { while(queue1.size() != 1){ queue2.offer(queue1.poll()); } value = queue1.peek(); queue2.offer(queue1.poll()); return value; } } public boolean empty() { return queue1.isEmpty() && queue2.isEmpty(); } }
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
