网站怎样做链接,上海美容论坛网站建设,做网站常用的套件,深鑫辉网站建设1. 队列
1.1 概念
只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出FIFO(First In First Out) 入队列#xff1a;进行插入操作的一端称为队尾#xff08;Tail/Rear#xff09; 出队列#xff1a;进行删除操作…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) {QueueInteger 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 (rear1)%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[k1];//使用牺牲空间法来区分满和空,初始化空间的时候就要多一个空间}public boolean enQueue(int value) {if(isFull()){return false;//队列为满,返回false}else{elem[rear] value;rear (rear1)%elem.length;}return true;}public boolean deQueue() {if(front rear){return false;//队列为空,删除失败}else{elem[front] 0;front (front1)%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 (rear1)%elem.length操作public boolean isEmpty() {if(rear front){return true;//头和尾重合的时候,就是空}else{return false;}}public boolean isFull() {if(front (rear1)%elem.length){return true;//中间空出一个空间的时候,就是满}return false;}}
}
2. 双端队列
双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口,必须使用LinkedList实例化对象.
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现3. 队列与栈的综合
3.1 用栈实现队列
在用栈实现队列的时候,核心思想把握住一句话:出队列的顺序和出栈的顺序相反,对头的元素对应栈底的元素.
OJ链接
class MyQueue2 {//需要用两个栈来实现一个队列StackInteger stack1;StackInteger 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 {QueueInteger queue1;QueueInteger 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();}}
