Java实现循环队列和链式队列
队列的定义:
队列是一种只允许一端进行插入操作,在另一端进行删除操作的线性表。允许插入的一端称为称为队尾,删除的一段是队头。想象你去排队购买车票时,排着一个很长的队,排在最前面的人买完票走了,这个操作就称为出队操作,而在队列的后面又来一个人排在后面,这个操作就称为入队操作。
一个普通的队列:
对于一个普通的队列来说, 如果进行入队的话,仅在队列后面追加一个元素就可以了,然后将队尾指针后移一个位置就可以了,但是如果要删除一个元素,那就很麻烦了,在队头删除了一个元素,那么后面的每一个元素都要向前移动一个·位置,是不是很麻烦?即使我们不让后面的元素往前移,我们把头指针向后移,那么想想,前面空闲的空间是不是很浪费?所以我们就需要使用循环队列。
循环队列的定义:
其实循环队列只是在普通队列的基础上,做了一点小小的改动,如果队尾指针到达最后的时候,如果再往里面增加元素,我们使队尾指针指向队列的头部(前面有空闲空间的情况下)。
其实这里需要注意两个问题了,那就是如何判断队列是满的还是空的,判断队列空还好说,那就是如果队头指针和队尾指针相等,那么这就是一个空队列。因为这是一个循环队列,判断满的时候应该需要这样判断:(队尾 + 1)%queueSize == 队头
队列的基本操作:
public MyQueue(int size) //利用构造器创建一个空队列
public boolean EnQueue(int i) //入队操作
public boolean DeQueue() //出队操作
public void printQueue() //遍历整个队列
创建一个空队列:
public MyQueue(int size){
dataB = new int[size];
this.size = size;
rear = 0;
front = 0;
}
这里利用构造器,当调用者调用的时候就创建出来,大小由调用者决定。
入队操作:
首先需要判断队列是否为满,如果队列满了,那还怎么入队?这里思想很简单,把元素放入队尾,然后把队尾指针向后移动一个位置,,注意这里的rear = (rear+1)%size;为什么要模以size呢,因为当队尾指针在最后一个位置的时候,就使它移向队列前面,这也是循环队列最重要的思想。
public boolean EnQueue(int i){
if((rear+1)%size == front){
return false;
}
dataB[rear] = i;
rear = (rear+1)%size;
count++;
return true;
}
出队操作:
很简单,删除队头元素,队头指针向后移动。
//出队
public boolean DeQueue(){
if(rear == front){
return false;
}
front = (front+1)%size;
count--;
return true;
}
遍历整个队列:
队列有效元素的个数我们已经用一个常量记录下来,那么知道队列有效元素的个数,那么遍历整个队列不是很简单吗,从头开始遍历,遍历个数的次数不久可以了嘛。
public void printQueue(){
int i = 0;
int j = front;
while(i < count){
System.out.print(dataB[j]+"...");
j = (j+1)%size;
i++;
}
System.out.println();
}
链式队列的定义:
它的存在其实还是解决了普通队列的一些不足,那就是在空间上,链式队列更加灵活
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已。
链式队列的基本操作:
public MyLQueue() //创建一个头节点
public boolean addEle(int a) //在队尾插入元素
public int delEle() //在头部删除元素
public void printQueue() //遍历队列
创建一个队列:
建立一个头节点,数据域是不存储元素的。空队列头指针和尾指针都指向头节点。
public MyLQueue(){
ListQueue n = new ListQueue();
n.next = null;
front = rear = n;
}
在队尾插入元素:
和链表的操作差不多,把新加的节点的指针域清空,然后使尾节点的指针域保存新节点的地址,然后把尾指针指向这个新的节点。
代码:
//在尾部插入元素
public boolean addEle(int a){
ListQueue n = new ListQueue(a);
n.next = null;
rear.next = n;
rear = n;
count++;
return true;
}
在头部插入元素:
有了头节点的存在,操作起来方便了很多,首先需要判断队列是否为空,然后还需要判断队列是不是只有一个节点,那么在删除这个节点之后还需要执行一个操作,那就是把尾节点也指向头节点。在执行出队操作的时候需要一个辅助指针,辅助我们完成这个操作。
代码:
public int delEle() throws Exception{
if(front == rear)
throw new Exception("空队列");
ListQueue tmp = front.next;
front.next = tmp.next;
if(rear == tmp){ //队列只有一个节点
rear = front;
}
int i = tmp.dataB;
tmp.next = null;
count--;
return i;
}
遍历整个队列:
跟普通的链表差不多,从头节点开始,依次往后遍历。
public void printQueue(){
ListQueue tmp = front.next;
while( tmp != null){
System.out.print(tmp.dataB+"...");
tmp = tmp.next;
}
System.out.println();
}