队列的实现

数组

数组实现需要用到循环队列操作，同时还需要考虑数组的扩容
循环队列操作详见 https://dingzh.cc/posts/b66774c1.html

public class Main{
	int[] array;	//储存元素的数组
	int Rear;	// 队尾索引,初始为0
	int Front;	// 队头索引,初始为0
	int maxSize;	// 数组大小
	
	//方法。实例化数组队列
	public void createQueue(int maxSize){
		this.maxSize = maxSize;
		array = new int[maxSize];
	}
	
	// 拓展方法。数组扩容（一般用不到）
	public void reSize(){
		int[] arrayBig = new int[maxSize*2];
		System.arraycopy(array,0,arrayBig,array.length);
		array = arrayBig;
	}
	
	/**
		这样写太麻烦，要实例化后再调用。一般直接设为全局变量就行。
	class Queen{
		int[] array;	
		int Rear;	
		int Front;
		int maxSize;	

		public Queen(){
			array = new int[maxSize];
		}
	}
	**/
}

链表

public class Main{
	Node front = null;	//队首，对应头结点
	Node rear = null;	//队尾，对应尾结点
	int size = 0;	  //队内元素

	// 链表结点类
	class Node{
		Node next;
		int val;
		public Node(int val){
			this.val = val;
		}
	}
}

正常情况
- 出队：front = front.next
- 入队：rear.next = node; rear = rear.next
特殊情况
- 队列为空时，front = rear = null。此时入队操作是让 front = rear = node
- 队列只有一个元素时，front = rear。此时出队操作是让 front = rear = null

API实现队列

队列类

1	Queue<Integer> q = new LinkedList<>();

入队

1	q.offer(3);

出队

q.poll();

得到队内第一个元素

1	Integer front = q.peek(); // 如果队内无元素，则返回null

得到队的大小

1	int size = q.size();

队是否为空

1	if(queue.isEmpty())

双端队列

顾名思义，既可以在头进出，也可以在尾进出的队列称为双端队列。

注意：ArrayDeque的效率是高于stack和LinkedList的，但ArrayDeque中不能放null，否则会报空指针异常，这种情况只能用LinkedList

双端队列Deque既有先入先出的特性又有先入后出的特性，既可以实现队列又可以实现栈
Deque接口继承于Queue
Deque实现了ArrayDeque和LinkedList
- ArrayDeque：数组实现的双端队列，作为队列时效率高
- LinkedList：链表实现的双端队列，作为栈时效率高

实现类

1 2	Deque<Integer> stack = new LinkedList<>(); Deque<Integer> queue = new ArrayDeque<>();

栈API

pop(): 弹出栈中元素，也就是返回并移除队头元素，等价于removeFirst()，如果队列无元素，则发生NoSuchElementException异常
push(): 向栈中压入元素，也就是向队头增加元素，等价于addFirst()，如果元素为null，则发生NPE，如果栈空间受到限制，则发生IllegalStateException异常