循环队列的实现方式详解(三种处理方式) |
您所在的位置：网站首页 › 循环队列为空的判定条件是什么 › 循环队列的实现方式详解(三种处理方式) |
循环队列的实现方式详解(三种处理方式)
|
这篇文章提供了判断循环队列是否已满，是否为空，提供了三种处理方式，在这里只是提供给大家一种解决问题的方式； 使用数组的方式实现循环队列本质是一种队列，具有FIFO的数据结构； 把数组想象成为一个一个环状的空间，就是把存储队列元素从逻辑上看作一个环，成为循环队列； 有几个比较重要的操作 初始化时：Q.front == Q.rear =0; 队头指针前进时：(Q.front + 1) % MaxSize; 队尾指针前进时：(Q.rear + 1) % MaxSize; 队列的长度：(Q.rear + MaxSize - Q.front) % MaxSize 其实这几个操作，小伙伴们可以细细品一下，以后做数组循环的相关的问题，手到擒来； 循环队列的队满和队空的判断条件是什么？显然队空的判断条件时Q.front == Q.rear 这是由初始条件决定的；如果入队的速度快于出队的速度，队尾的指针很快追上队头的指针，可以看到队列满的时候也有Q.front == Q.rear; 为了区分循环队列 队满 还是对空？有三种处理方式： 牺牲一个存储单元来区分队满还是队空，入队时少用一个队列单元，“队头指针在队尾指针的下一个位置作为队满的标志” 队满的条件：（Q.rear + 1）% MaxSize == Q.front 在循环队列中增设表示元素个数的成员变量(size), 队空的条件：Q.size == 0 队满的条件：Q.size == Q.MaxSize 在编码中，这种方式是比较推荐的，这是因为size成员变量可以使得Q.rear,Q.front成员变量解耦； 增设tag成员变量，用于区分队满还是队空。 tag等于0时，因删除导致的Q.front == Q.rear则是队空，tag等于1时，因为插入导致的Q.front== Q.rear，则为队满 定义队列接口 interface Queue { int poll(); void offer(int e); } 牺牲一个元素 static class RecycleQueueV1 implements Queue { private final int MAXSIZE; private final int[] element; private int front = 0,rear = 0; public RecycleQueueV1(int length) { this.element = new int[length]; this.MAXSIZE = length; } @Override public int poll() { if(this.rear == this.front) { throw new RuntimeException("队列为空"); } int res = this.element[this.front]; this.front = (this.front + 1) % MAXSIZE; return res; } @Override public void offer(int e) { int next = (this.rear + 1) % MAXSIZE; if(next == this.front) { throw new RuntimeException("队列已满"); } this.element[this.rear] = e; this.rear = next; } } 增设一个元素个数的成员变量 static class RecycleQueueV2 implements Queue{ private final int MAXSIZE; private final int[] element; private int front = 0,rear = 0; int size = 0; public RecycleQueueV2(int length) { this.MAXSIZE = length; this.element = new int[length]; } @Override public int poll() { if(size == 0) { throw new RuntimeException("队列为空"); } int res = this.element[this.front]; this.front = (this.front + 1) % MAXSIZE; this.size--; return res; } @Override public void offer(int e) { if(size == MAXSIZE) { throw new RuntimeException("队列已满"); } int next = (this.rear + 1) % MAXSIZE; this.element[this.rear] = e; this.rear = next; this.size++; } } 增设一个tag成员变量 static class RecycleQueueV3 implements Queue{ private final int MAXSIZE; private final int[] element; // 初始化front == rear == 0,tag = 0,表示此时队列为null private int front = 0,rear = 0; int tag = 0;// public RecycleQueueV3(int length){ this.MAXSIZE = length; this.element = new int[length]; } @Override public int poll() { if(tag == 0 && this.front == this.rear) { throw new RuntimeException("队列为空"); } int res = this.element[this.front]; this.front = (this.front + 1) % MAXSIZE; if(this.front == this.rear) tag = 0; return res; } @Override public void offer(int e) { if(tag == 1 && this.front == this.rear) { throw new RuntimeException("队列已满"); } int next = (this.rear + 1) % MAXSIZE; this.element[this.rear] = e; this.rear = next; if(this.rear == this.front) tag = 1; } } |
规定Q表示队列,成员变量front,rear分别表示队头指针和队尾指针，MaxSize表示队列数组的长度【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |