(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 代码模板”。
|