一、队列概述
队列也是常见的数据结构，是一种线性数据结构，队列的主要特点：“先进先出”。
队列有队头和队尾，一般在队尾进行插入操作，队头进行删除操作。
二、队列的模拟实现
在实现队列时可以使用链表也可以使用数组，但是链表的长度不受限制，不需要一段连续的空间，所以此处采用链表进行模拟实现。
在单链表进行模拟实现队列时，除了定义头结点外，还需要定义尾结点以确保在插入元素时时间复杂度为O(1),还定义一个usedSize来表示队列的长度。
1、入队
在入队时首先应该判断队列是否为空，如果队列为空，就将head和last都指向新插入的结点；如果队列不为空，就将新插入的结点插入到last指向结点的后面。这两种情况都需要将队列的有效长度加1。
//入队 public void offer(int val){ QNode qNode=new QNode(val); if(head==null){ head=qNode; last=head; }else{ last.next=qNode; last=qNode; } usedSize++; }
2、出队
在出队列时，首先需要判断队列是否为空，若不为空，就取出head结点的值，将head后移，在此处也需要判断此时的head是否为null，若为null则也需要将last置为null，然后将队列的有效长度减一。
//出队 public int poll(){ if(isEmpty()){ System.out.println("队列为空"); return -1; }else{ int val=head.val; head=head.next; if(head==null){ last=head; } usedSize--; return val; } } //判断队列是否为空 public boolean isEmpty(){ if(usedSize==0){ return true; }else{ return false; } }
3、取队头元素
若队列为空则无法获取，否则直接获取head的val值。
//取队头元素 public int peek(){ if(head==null){ return -1; }else{ return head.val; } }
4、获取队列长度
直接返回链表的有效长度即可。
//获取队列的长度 public int getSize(){ return usedSize; }
三、循环队列
为什么引入循环队列？
当队列用数组存储时，会造成极大的空间浪费。例如如下情况，rear队尾已达到数组的最大值，此时已无法存储元素，但是front队头之前还有空间却无法利用就会造成空间浪费。
循环队列：可以充分地利用空间，下面利用数组存储模拟实现循环队列。
1、入队
在入队之前需要判断队列是否已满，可以定义一个usedSize来表示队列长度，还可以浪费一个空间，也就是rear指向队尾元素的下一个空间，用(rear+1)%数组长度==front来判断队列是否已满，前者比较简单就采用后者所示的方法进行实现，如下就表示队列已满。接着就在rear所指的位置插入元素，由于是循环队列，就让rear=(rear+1)%数组长度来进行后移。
public boolean isFull() { if((rear+1)%data.length==front){ return true; } return false; } public boolean enQueue(int value) { if(isFull()){ return false; }else{ data[rear]=value; rear=(rear+1)%data.length; return true; } }
2、出队
首先判断队列是否为空，若不为空则弹出front所指的元素，同样front=(front+1)%数组长度来实现后移。
public boolean isEmpty() { return rear==front; } public boolean deQueue() { if(isEmpty()){ return false; }else{ front=(front+1)%data.length; return true; } }
3、取队头元素
若队列不为空则直接取对头元素。
public int Front() { if(isEmpty()){ return -1; }else{ return data[front]; } }
4、取队尾元素
也需要先判断队列是否为空，还有由于rear指的是队尾元素的下一个空间，所以要对rear指向0进行特殊处理：返回数组长度-1位置的元素，其余情况返回rear-1位置的元素即可。
public int Rear() { if(isEmpty()){ return -1; }else{ if(rear==0){ return data[data.length-1]; }else{ return data[rear-1]; } } }
四、面试题
1、用队列实现栈
如果用一个队列来直接实现，栈是先进后出，队列是先进先出，在出栈时就无法只依靠一个队列来实现，所以就需要定义两个队列。
入栈：哪个队列不为空，就入哪个队列，如果都为空，就入第一个队列，因为要留一个队列用于出队列。
出栈：首先判断两个队列是否都为空，若都不为空则将不为空的队列出size-1个元素到为空的队列中，以确保不为空的队列中最后出队列的是最后进入的。
取栈顶元素：与出栈类似，但是取栈顶元素需要将不为空的队列全部入到为空的队列，同时需要拿到最后一个出队的元素值。
public class MyStack2 { Queue<Integer> qu1; Queue<Integer> qu2; public MyStack2() { 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()-1; for(int i=0;i<size;i++){ qu2.offer(qu1.poll()); } return qu1.poll(); } else { int size = qu2.size() - 1; for (int i = 0; i < size; i++) { qu1.offer(qu2.poll()); } return qu2.poll(); } } public int top() { if(empty()){ return -1; } if(!qu1.isEmpty()){ int size=qu1.size(); int val=-1; for(int i=0;i<size;i++){ val=qu1.poll(); qu2.offer(val); } return val; } else { int size = qu2.size(); int val=-1; for (int i = 0; i < size; i++) { val=qu2.poll(); qu1.offer(val); } return val; } } public boolean empty() { return qu1.isEmpty()&&qu2.isEmpty(); } }
2、用栈实现队列
与上题类似，同样也需要两个栈来实现，但是一个栈主要进行去队列，另一个栈进行出队列，假设s1为入队栈，s2为出队栈。
入队：直接在s1进行入栈操作。
出队：如果s2不为空，就直接进行出栈，否则就将s1中的元素全部转移到s2中再进行出栈。
取队头元素：与出队操作类似，只不过将出栈换成取栈顶元素即可。
public class MyQueue2 { Stack<Integer> s1; Stack<Integer> s2; public MyQueue2() { s1=new Stack<>(); s2=new Stack<>(); } public void push(int x) { s1.push(x); } public int pop() { if(!s2.isEmpty()){ return s2.pop(); }else if(!s1.isEmpty()){ int size=s1.size(); for(int i=0;i<size;i++) { s2.push(s1.pop()); } return s2.pop(); }else{ return -1; } } public int peek() { if(!s2.isEmpty()){ return s2.peek(); }else if(!s1.isEmpty()){ int size=s1.size(); for(int i=0;i<size;i++) { s2.push(s1.pop()); } return s2.peek(); }else{ return -1; } } public boolean empty() { return s1.isEmpty()&&s2.isEmpty(); } }
