一、什么是队列？
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）
二、队列的使用
1.java中的基本使用
代码如下（示例）：
public static void main(String[] args) {
System.out.println("普通队列的使用:");
Queue<Integer> queue=new LinkedList<>();
//添加元素
queue.add(2);
queue.add(4);
queue.add(5);
queue.offer(4);
queue.offer(9);
queue.offer(23);
System.out.print("队列的大小:");
System.out.println(queue.size());
System.out.print("获取队头元素:");
System.out.print(queue.peek()+" ");
System.out.println(queue.element());
System.out.print("弹出队列:");
System.out.print(queue.poll()+" ");
System.out.println(queue.remove());
System.out.print("队列的大小:");
System.out.println(queue.size());
System.out.println("======================");
System.out.print("双端队列的使用:");
Deque<Integer> deque=new LinkedList<>();
//添加元素，队头入队
deque.addFirst(4);
deque.addFirst(5);
deque.addFirst(87);
deque.offerFirst(23);
//队尾入队
deque.addLast(56);
deque.add(7);//add也可以使用
deque.offerLast(12);
deque.offer(66);//也可以
System.out.print("双端队列的大小"+" ");
System.out.println(deque.size());
System.out.print("获取队头元素:");
System.out.print(deque.getFirst()+" ");
System.out.print(deque.peekFirst()+" ");
System.out.println(deque.peek());
System.out.print("获取队尾元素:");
System.out.print(deque.getLast()+" ");
System.out.println(deque.peekLast());
System.out.print("出队列(队头):");
System.out.print(deque.remove()+ " ");
System.out.println(deque.poll()+" ");
System.out.print(deque.removeFirst()+" ");
System.out.println(deque.pollFirst());
System.out.print("出队列(队尾):");
System.out.print(deque.removeLast()+" ");
System.out.println(deque.pollLast());
System.out.print("双端队列的大小"+" ");
System.out.println(deque.size());
}
2.链表实现队列
代码如下（示例）：
//用链表实现队列
class Node{
int val;
Node next;
public Node(int val,Node next){
this.val=val;
this.next=next;
}
public Node(int val){
this(val,null);
}
}
class MyQueue{
private Node head=null;
private Node tail=null;
private int size=0;
//入队：类似于尾插法。
public void offer(int v){
Node node=new Node(v);
if(tail==null){
this.head=node;
}else {
tail.next=node;
}
this.tail=node;
size++;
}
//出队：类似删除头节点
public int poll(){
if(size==0){
throw new RuntimeException("队列为空");
}
Node oldHead=head;
head=head.next;
if(head==null){
tail=null;
}
size--;
return oldHead.val;
}
//出队不删除队列元素。
public int peek(){
if (size==0){
throw new RuntimeException("队列为空");
}
return head.val;
}
//判断是否为空
public boolean isEmpty(){
//size为0，返回为true,否则falase
return size==0;
}
//队列长度
public int size(){
return size;
}
}
public class Demo2 {
public static void main(String[] args) {
MyQueue myQueue=new MyQueue();
//入队
myQueue.offer(4);
myQueue.offer(5);
myQueue.offer(23);
//长度
System.out.println(myQueue.size());
//出队不删除
System.out.println(myQueue.peek());
//出队
System.out.println(myQueue.poll());
System.out.println(myQueue.peek());
//长度
System.out.println(myQueue.size());
//是否为空
System.out.println(myQueue.isEmpty());
}
}
注：实现双端队列只需使用双向链表即可
3、用数组实现队列，循环队列。
判断队列是空是满，即rear和front的关系。
一、使用UsedSizde与数组长度比较。
- usedsize记录添加元素和删除元素是的长度，如usedsize和数组长度相同就是满的，否则为空。
二、设置标志位
三、检查下一个元素是不是front。
- 检查下一个元素是不是front，若是则满，否则未满。
class MyCircularQueue{
public int[] elem;
public int front;//头下标
public int rear;//尾下标
public MyCircularQueue(int k){
this.elem=new int[k+1];
}
//入队
public boolean enQueue(int value){
if(isFull()){
return false;
} else {
this.elem[rear] = value;
rear=(rear+1)%elem.length;
}
return true;
}
//出队
public boolean deQueue(){
if(isEmpty()){
return false;
}
front=(front+1)%elem.length;
return true;
}
//得到队头元素
public int Front(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}else {
return elem[front];
}
}
public int Rear(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
int index=-1;//初始化index
if (rear==0){
index=elem.length-1;//单独判断若rear为0时队尾下标。
}else {
index=rear-1;
}
return elem[index];
}
//使用的是第三种方法判断满没满
public boolean isFull(){
if((this.rear+1)%elem.length==front){
return true;
}
return false;
}
public boolean isEmpty(){
return front==rear;
}
}
3、两个队列实现栈
//用两个队列实现栈
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1=new LinkedList<>();
queue2=new LinkedList<>();
}
public void push(int x) {
if(!queue1.isEmpty()){
queue1.offer(x);
}else if(!queue2.isEmpty()){
queue2.offer(x);
}else{
queue1.offer(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
int size=queue1.size();
for(int i=0;i<size-1;i++){
int val=queue1.poll();
queue2.offer(val);
}
return queue1.poll();
}
if(!queue2.isEmpty()){
int size=queue2.size();
for(int i=0;i<size-1;i++){
int val=queue2.poll();
queue1.offer(val);
}
return queue2.poll();
}
return -1;
}
public int top() {
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
int val=-1;
int size=queue1.size();
for(int i=0;i<size;i++){
val=queue1.poll();
queue2.offer(val);
}
return val;
}
if(!queue2.isEmpty()){
int val=-1;
int size=queue2.size();
for(int i=0;i<size;i++){
val=queue2.poll();
queue1.offer(val);
}
return val;
}
return -1;
}
public boolean empty() {
return queue1.isEmpty()&&queue2.isEmpty();
}
}
public class Demo4 {
public static void main(String[] args) {
MyStack myStack=new MyStack();
myStack.push(5);
myStack.push(7);
System.out.println(myStack.pop());
System.out.println(myStack.top());
System.out.println(myStack.empty());
}
}
4、用栈来实现队列
class MyQueue1 {
public Stack<Integer> stack1;
public Stack<Integer> stack2;
public MyQueue1() {
stack1=new Stack<>();
stack2=new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
int size=stack1.size();
while(!stack1.isEmpty()){
for(int i=0;i<size;i++){
int val=stack1.pop();
stack2.push(val);
}
}
}
return stack2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
int size=stack1.size();
while(!stack1.isEmpty()){
for(int i=0;i<size;i++){
int val=stack1.pop();
stack2.push(val);
}
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
}
public class Demo5 {
public static void main(String[] args) {
MyQueue1 myQueue1=new MyQueue1();
myQueue1.empty();
myQueue1.push(6);
myQueue1.push(8);
myQueue1.push(3);
myQueue1.push(23);
System.out.println(myQueue1.peek());
System.out.println(myQueue1.pop());
System.out.println(myQueue1.empty());
}
}
