队列

(1) 顺序队列!

操作规则：先进先出，后进后出。

1. 定义：int queue[N], front=0, rear=0;

front指向队列首个元素，rear指向队列尾部元素的右侧。

2. 入队：inline void push(int a) { queue[rear++]=a; }

3. 出队：inline int pop() { return queue[front++]; }

4. 队空的条件：inline bool empty() { return front==rear; }  

(2) 循环队列!

循环队列——把链状的队列变成了一个环状队列。与上面的链状队列相比，可以节省很大空间。

1. 定义：int queue[N], front=0, rear=0;

front指向队列首个元素，rear指向队列尾部元素的右侧。

2. 入队：inline void push(int a) { queue[rear]=a; rear=(rear+1)%N; }

3. 出队：inline int pop() { int t=queue[front]; front=(front+1)%N; return t; }

4. 队满或队空的条件：inline bool empty() { return front==rear; } 队满和队空都符合上述条件。怎么把它们区分开呢？第一种方法：令队列的大小是 N+1，然后只使用 N 个元素。这样队满和队空的条件就不一样了。

第二种方法：在入队和出队同时记录队列元素个数。这样，直接检查元素个数就能知道队列是空还是满。

(3) BFS和队列

BFS要借助队列来完成，并且，将队列改成堆栈，BFS就变成了DFS。BFS的具体实现见42页“3.7 代码模板”。