一 队列
队列是一种先进先出的数据结构，队列中的元素按照进入的顺序排列，第一个插入的元素最先被移除。
1.队列的使用 ：
Queue是一个接口，底层是通过链表实现的。
我们可以通过双链表模拟实现一个Queue
1.入队列（向双向链表位置插入新的节点）
public class MyQueue {static class ListNode{public ListNode prev;public ListNode next;public int val;public ListNode(int val){this.val=val;}}public ListNode head=null;public ListNode last=null;public int usedSize=0;//public void offer(int val){ListNode node=new ListNode(val);if(isEmpty()){head=last=node;}else {last.next=node;node.prev=last;last=last.next;}usedSize++;}2.出队列（将队列中的第一个节点移除）
public class MyQueue {static class ListNode{public ListNode prev;public ListNode next;public int val;public ListNode(int val){this.val=val;}}public ListNode head=null;public ListNode last=null;public int usedSize=0;public boolean isEmpty(){return usedSize==0;}public int pop() {if (isEmpty()) {}head = head.next;int val1 = head.val;if(head!=null){head.prev = null;}usedSize--;return val1;}
}3.查询队列的节点
由于队列的规则为先进先出，所以查询的队列为首节点。
public class MyQueue {static class ListNode{public ListNode prev;public ListNode next;public int val;public ListNode(int val){this.val=val;}}public ListNode head=null;public ListNode last=null;public int usedSize=0;public int peek(){if(isEmpty()){return -1;}return head.val;}
}2.循环队列
模拟实现的方法：
1. 通过添加 size 属性记录
2. 保留一个位置
3. 使用标记
循环队列是一个环形队列，我们可以使用舍弃一个位置的方法来实现一个循环队列（保留一个位置）
. - 力扣（LeetCode）
public class MyCircleQueue {public int front;public int last;public int[] elem;public MyCircleQueue(int k){elem=new int[k+1];}public boolean enQueue(int value){if (isFull()){return false;}elem[last]=value;last=(last+1)%elem.length;return true;}public boolean deQueue(){if(isEmpty()){return false;}front=(front+1)%elem.length;return true;}public int Last(){if (isEmpty()){return -1;}int index=(last==0)?elem.length-1:last-1;return elem[index];}public int Front(){if (isEmpty()){return -1;}return front;}public boolean isEmpty(){return last==front;}public boolean isFull(){return (last+1)%elem.length==front;}
}二 双端队列 (Deque)
两端都可以进，可以出。
三 栈和队列的互相实现
1.用队列实现栈
. - 力扣（LeetCode）
class MyQueue {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyQueue() {qu1=new LinkedList<>();qu2=new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}public int pop() {if(empty()){return -1;}if(!qu1.isEmpty()){int size=qu1.size();for(int i=0;i<size-1;i++){qu2.offer(qu1.poll());}return qu1.poll();}else{int size=qu2.size();for(int i=0;i<size-1;i++){qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {if(empty()){return -1;}if(!qu1.isEmpty()){int size=qu1.size();int val=0;for(int i=0;i<size;i++){val=qu1.poll();qu2.offer(val);}return val;}else{int size=qu2.size();int val=0;for(int i=0;i<size;i++){val=qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}
2.用栈实现队列
. - 力扣（LeetCode）
class MyQueue {public ArrayDeque<Integer> s1;public ArrayDeque<Integer> s2;public MyQueue() {s1=new ArrayDeque<>();s2=new ArrayDeque<>();}public void push(int x) {s1.push(x);}public int pop() {if(empty()){return -1;}if(s2.isEmpty()){while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.pop();}public int peek() {if(empty()){return -1;}if(s2.isEmpty()){while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}希望能对大家有所帮助！！！！
)