南昌做网站建设哪家好,欧美风格网站模版,亚i洲人页码24林妹妹,北京网站建设套餐环形队列
1. 定义
环形队列就是将队列在逻辑上看作环形结构、物理上仍是数组形式存储的一种数据结构。
其实现主要分为两种情况#xff1a;
浪费空间法记录空间法
2. 实现 实现要考虑的是成员变量 2.1 记录空间法
使用used标识当前存储了多少元素#xff0c;如果为空
浪费空间法记录空间法
2. 实现 实现要考虑的是成员变量 2.1 记录空间法
使用used标识当前存储了多少元素如果为空那么就将head移到0位置处如果满了那么就将tail移到0位置处
1. 入队 队列是从队尾入队头出所以就是在tail的位置入队每入一个元素就将tail当满的时候就将tail恢复到队头。 普通情况 队列满了
这时就需要tail0等待某个时候有元素出队这个时候新插入的元素就又能在tail的位置进行插入。 出队操作与入队操作对称同理。 2. 代码实现
package MyCircleQueue;public class CircleQueue {int size 5;// 队列最大容量int used 0;// 队列已使用元素int[] data new int[size];// 存储队列数据int tail 0, head 0;// 队列头尾指针public void offer(int val) {// 满了if (used size) {tail 0;System.out.println(满了);return;}// 没满data[tail] val;used;System.out.println(存入val);}public int poll() {if (used 0) {head 0;System.out.println(空了);return -1;}int ret data[head];used--;System.out.println(取出ret);return ret;}
}
2.2 浪费空间法
在这种方式中我们只使用头尾两个指针进行计算并将 head tail 的情况记作空将 (tail1)%size head 的情况记作满。
2.2.1实现代码
package MyCircleQueue;public class CircleQueue2 {int size 5;int[] data new int[size];int head 0, tail 0;public void offer(int val) {if ((tail1) % size head) {System.out.println(满了);return;}data[tail] val;System.out.println(入队:val);}public int poll() {if (head tail) {System.out.println(空了);return -1;}int ret data[head];System.out.println(出队:ret);return ret;}
}
3. 测试代码
package MyCircleQueue;public class Test {public static void main(String[] args) {CircleQueue queue new CircleQueue();for (int i 0; i 10; i) {queue.offer(i);}for (int i 0; i 10; i) {int ret queue.poll();}}
}
4. 结论
环形队列分为两种实现方式
方法满的标记空的标记浪费空间法(tail1)%size headhead tail标记长度法used sizeused 0
其中推荐使用标记长度法。
