1. 队列的逻辑结构
a) 定义：只允许在表的一端进行插入，另一端进行删除的线性表，进行插入的一端叫队尾，进行删除的一端叫队头，没有数据元素时称为空队列。
b) 特征：先进先出
c) 抽象数据类型
i. 数据元素：同属一类的任意类型对象
ii. 数据结构：线性结构，队头无前驱，队尾无后继
iii. 数据操作：定义在IQueue中
publicinterface IQueue<E> {
boolean enqueue(E e); //入栈
E dequeue(); //出栈
E peek(); //去对头元素
int size(); //返回队长
boolean isEmpty(); //判断是否空队
boolean ifFull(); //判断是否满队
}
2. 队列实现之顺序队列
a) 存储结构：顺序队列采用一个连续的一维数组来保存数据，队头设置在最近一个元素离开的位置front，队尾设置在最近一个元素插入的位置rear，但是如果队列设置成一个直线型的由于队尾入队和队头出对会造成“假溢出”，因此将队列设置成一个环状的。当队空时，front=rear，当队满时(rear+1)%maxsize=front，入队时，rear=(rear+1)%maxsize，出队时，front=(front+1)%maxsize，队中元素个数为(rear-front+maxsize)，且数组中的下标为front的元素不存储数据
b) 基本操作
i. 初始化顺序队列：给定顺序队列最大存储空间大小，front和rear都设为0，size设为0；
ii. 入队：将下标为rear设为(rear+1)%maxsize且对应的位置值设为指定入队元素
iii. 出队：将front设为(front+1)%maxsize
iv. 求队长：返回(rear-front+maxsize)%maxsize
v. 判断是否满队：判断(rear+1)%maxsize==front
vi. 判断是否空队：判断rear==front
c) 代码实现
publicclass MySequenceQueue<E> implements IQueue<E> {
privateintsize; //队列长度
privateintmaxsize; //队列最大长度
privateintfront; //队头,指向的是将要离开的元素的前一个位置
privateintrear; //队尾
private E[] data;
//初始化顺序队列
public MySequenceQueue(intmaxsize) {
super();
this.size = 0;
this.maxsize = maxsize;
data=(E[])new Object[this.maxsize];
this.front = 0;
this.rear = 0;
}
//入队
@Override
publicboolean enqueue(E e) {
if(!this.isFull()) {
this.rear=(this.rear+1)%this.maxsize;
this.data[this.rear]=e;
returntrue;
}
returnfalse;
}
//出队
@Override
public E dequeue() {
if(!this.isEmpty()) {
this.front=(this.front+1)%this.maxsize;
returnthis.data[this.front];
}
returnnull;
}
//取队头元素
@Override
public E peek() {
if(!this.isEmpty())
returnthis.data[(this.front+1)%maxsize];
returnnull;
}
//求队长
@Override
publicint size() {
this.size=(this.rear-this.front+maxsize)%maxsize;
returnthis.size;
}
@Override
publicboolean isEmpty() {
if(this.front==this.rear)
returntrue;
returnfalse;
}
@Override
publicboolean isFull() {
if((this.rear+1+this.maxsize)%maxsize==this.front)
returntrue;
returnfalse;
}
}
3. 队列实现之链队列
a) 存储结构：队头节点用front，队尾节点用rear，每个节点包含数据域和指向下一个节点的next，队尾节点的next为null，队头队尾节点不用来存储数据
b) 基本操作
i. 初始化链队列：设置队列长度size为0，队头节点和队尾节点都为null，然后将队头节点的next设置为rear
ii. 入队：首先找到队列的除队尾的最后一个节点（队尾的上一个节点），然后新建节点，将新建节点的next设为rear，将入队前的最后一个节点的next设为新建节点，并使size自增
iii. 出队：找到队头节点的下一个节点，将其数据区域的值取出并保存在临时变量中，将队头节点的next设为出队前的第一个节点的下一个节点，使size自减，并返回临时变量
iv. 判断是否空队：如果front的next指向rear返回true，否则返回false
c) 代码实现
//建立队列节点，包括数据和指向下一个节点的next
class QueueNode<E>{
private E e;
private QueueNode<E> next;
public QueueNode(E e, QueueNode<E> next) {
super();
this.e = e;
this.next = next;
}
public E getE() {
returne;
}
publicvoid setE(E e) {
this.e = e;
}
public QueueNode<E> getNext() {
returnnext;
}
publicvoid setNext(QueueNode<E> next) {
this.next = next;
}
}
publicclass MylinkQueue<E> implements IQueue<E> {
privateintsize;
private QueueNode<E> front;
private QueueNode<E> rear;
//初始化链队列，将size设为0，front和rear都设为null
public MylinkQueue() {
super();
this.size = 0;
this.front = new QueueNode(null,null); //初始化队列，让队头的next指向队尾
this.rear = new QueueNode(null,null);
this.front.setNext(this.rear);
}
//入队
@Override
publicboolean enqueue(E e) {
QueueNode temp=this.front;
if(!this.isFull()) {
while(temp.getNext()!=this.rear)
temp=temp.getNext(); //找到队尾的上一个元素
QueueNode<E> node=new QueueNode(e,this.rear); //新建立一个节点，并将该节点的next指向队尾
temp.setNext(node); //将入队前队列的最后一个元素的next指向新节点
this.size++;
returntrue;
}
returnfalse;
}
//出队
@Override
public E dequeue() {
QueueNode<E> temp=this.front.getNext();
this.front.setNext(temp.getNext());
this.size--;
returntemp.getE();
}
//返回队列的第一个元素
@Override
public E peek() {
returnthis.front.getNext().getE();
}
@Override
publicint size() {
returnthis.size;
}
@Override
publicboolean isEmpty() {
if(this.front.getNext()==this.rear)
returntrue;
returnfalse;
}
@Override
publicboolean isFull() {
returnfalse;
}
}
1. 队列的逻辑结构
a) 定义：只允许在表的一端进行插入，另一端进行删除的线性表，进行插入的一端叫队尾，进行删除的一端叫队头，没有数据元素时称为空队列。
b) 特征：先进先出
c) 抽象数据类型
i. 数据元素：同属一类的任意类型对象
ii. 数据结构：线性结构，队头无前驱，队尾无后继
iii. 数据操作：定义在IQueue中
publicinterface IQueue<E> {
boolean enqueue(E e);//入栈
E dequeue(); //出栈
E peek(); //去对头元素
int size(); //返回队长
boolean isEmpty();//判断是否空队
boolean ifFull();//判断是否满队
}
2. 队列实现之顺序队列
a) 存储结构：顺序队列采用一个连续的一维数组来保存数据，队头设置在最近一个元素离开的位置front，队尾设置在最近一个元素插入的位置rear，但是如果队列设置成一个直线型的由于队尾入队和队头出对会造成“假溢出”，因此将队列设置成一个环状的。当队空时，front=rear，当队满时(rear+1)%maxsize=front，入队时，rear=(rear+1)%maxsize，出队时，front=(front+1)%maxsize，队中元素个数为(rear-front+maxsize)，且数组中的下标为front的元素不存储数据
b) 基本操作
i. 初始化顺序队列：给定顺序队列最大存储空间大小，front和rear都设为0，size设为0；
ii. 入队：将下标为rear设为(rear+1)%maxsize且对应的位置值设为指定入队元素
iii. 出队：将front设为(front+1)%maxsize
iv. 求队长：返回(rear-front+maxsize)%maxsize
v. 判断是否满队：判断(rear+1)%maxsize==front
vi. 判断是否空队：判断rear==front
c) 代码实现
publicclass MySequenceQueue<E> implements IQueue<E> {
privateintsize;//队列长度
privateintmaxsize; //队列最大长度
privateintfront;//队头,指向的是将要离开的元素的前一个位置
privateintrear;//队尾
private E[] data;
//初始化顺序队列
public MySequenceQueue(intmaxsize) {
super();
this.size = 0;
this.maxsize = maxsize;
data=(E[])new Object[this.maxsize];
this.front = 0;
this.rear = 0;
}
//入队
@Override
publicboolean enqueue(E e) {
if(!this.isFull()) {
this.rear=(this.rear+1)%this.maxsize;
this.data[this.rear]=e;
returntrue;
}
returnfalse;
}
//出队
@Override
public E dequeue() {
if(!this.isEmpty()) {
this.front=(this.front+1)%this.maxsize;
returnthis.data[this.front];
}
returnnull;
}
//取队头元素
@Override
public E peek() {
if(!this.isEmpty())
returnthis.data[(this.front+1)%maxsize];
returnnull;
}
//求队长
@Override
publicint size() {
this.size=(this.rear-this.front+maxsize)%maxsize;
returnthis.size;
}
@Override
publicboolean isEmpty() {
if(this.front==this.rear)
returntrue;
returnfalse;
}
@Override
publicboolean isFull() {
if((this.rear+1+this.maxsize)%maxsize==this.front)
returntrue;
returnfalse;
}
}
3. 队列实现之链队列
a) 存储结构：队头节点用front，队尾节点用rear，每个节点包含数据域和指向下一个节点的next，队尾节点的next为null，队头队尾节点不用来存储数据
b) 基本操作
i. 初始化链队列：设置队列长度size为0，队头节点和队尾节点都为null，然后将队头节点的next设置为rear
ii. 入队：首先找到队列的除队尾的最后一个节点（队尾的上一个节点），然后新建节点，将新建节点的next设为rear，将入队前的最后一个节点的next设为新建节点，并使size自增
iii. 出队：找到队头节点的下一个节点，将其数据区域的值取出并保存在临时变量中，将队头节点的next设为出队前的第一个节点的下一个节点，使size自减，并返回临时变量
iv. 判断是否空队：如果front的next指向rear返回true，否则返回false
c) 代码实现
//建立队列节点，包括数据和指向下一个节点的next
class QueueNode<E>{
private E e;
private QueueNode<E> next;
public QueueNode(E e, QueueNode<E> next) {
super();
this.e = e;
this.next = next;
}
public E getE() {
returne;
}
publicvoid setE(E e) {
this.e = e;
}
public QueueNode<E> getNext() {
returnnext;
}
publicvoid setNext(QueueNode<E> next) {
this.next = next;
}
}
publicclass MylinkQueue<E> implements IQueue<E> {
privateintsize;
private QueueNode<E> front;
private QueueNode<E> rear;
//初始化链队列，将size设为0，front和rear都设为null
public MylinkQueue() {
super();
this.size = 0;
this.front = new QueueNode(null,null); //初始化队列，让队头的next指向队尾
this.rear = new QueueNode(null,null);
this.front.setNext(this.rear);
}
//入队
@Override
publicboolean enqueue(E e) {
QueueNode temp=this.front;
if(!this.isFull()) {
while(temp.getNext()!=this.rear)
temp=temp.getNext(); //找到队尾的上一个元素
QueueNode<E> node=new QueueNode(e,this.rear); //新建立一个节点，并将该节点的next指向队尾
temp.setNext(node); //将入队前队列的最后一个元素的next指向新节点
this.size++;
returntrue;
}
returnfalse;
}
//出队
@Override
public E dequeue() {
QueueNode<E> temp=this.front.getNext();
this.front.setNext(temp.getNext());
this.size--;
returntemp.getE();
}
//返回队列的第一个元素
@Override
public E peek() {
returnthis.front.getNext().getE();
}
@Override
publicint size() {
returnthis.size;
}
@Override
publicboolean isEmpty() {
if(this.front.getNext()==this.rear)
returntrue;
returnfalse;
}
@Override
publicboolean isFull() {
returnfalse;
}
}