队列的概念:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
package 队栈;
public class seqQueue<T> {
private T data[];// 数组容器
private int front;// 头
private int rear;// 尾
private int maxsize;// 最大长度
public seqQueue(int i)// 设置长为i的int 型队列
{
data = (T[]) new Object[i+1];
front = 0;
rear = 0;
maxsize = i+1;
}
public int lenth() {
return (rear+maxsize-front)%maxsize;
}
public boolean isempty() {
return rear == front;
}
public boolean isfull() {
return (rear + 1) % maxsize == front;
}
public void enQueue(T i) throws Exception// 入队
{
if (isfull())
throw new Exception("已满");
else {
data[rear] = i;
rear=(rear + 1) % maxsize;
}
}
public T deQueue() throws Exception// 出队
{
if (isempty())
throw new Exception("已空");
else {
T va=data[front];
front=(front+1)%maxsize;
return va;
}
}
public String toString()// 输出队
{
String va="队头: ";
int lenth=lenth();
for(int i=0;i<lenth;i++)
{
va+=data[(front+i)%maxsize]+" ";
}
return va;
}
}
对于链表实现的队列,要根据先进先出的规则考虑头和尾的位置
我们知道队列是先进先出的,对于链表,我们能采用单链表尽量采用单链表,能方便尽量方便,同时还要兼顾效率。
方案一 如果队头设在链表尾,队尾设在链表头。那么队尾进队插入在链表头部插入没问题。容易实现,但是如果队头删除在尾部进行,如果不设置尾指针要遍历到队尾,但是设置尾指针删除需要将它指向前驱节点那么就需要双向链表。都挺麻烦的。
方案二但是如果队头设在链表头,队尾设在链表尾部,那么队尾进队插入在链表尾部插入没问题(用尾指针可以直接指向next)。容易实现,如果队头删除在头部进行也很容易,就是我们前面常说的头节点删除节点。
所以我们最终采取的是方案2的带头节点,带尾指针的单链表!
主要操作为:
package 队栈;
public class listQueue<T> {
static class node<T> {
T data;// 节点的结果
node next;// 下一个连接的节点
public node() {}
public node(T data) {
this.data = data;
}
}
node front;//相当于head 带头节点的
node rear;//相当于tail/end
public listQueue() {
front=new node<T>();
rear=front;
}
public int lenth() {
int len=0;
node team=front;
while(team!=rear)
{
len++;team=team.next;
}
return len;
}
public boolean isempty() {
return rear == front;
}
public void enQueue(T value) // 入队.尾部插入
{
node va=new node<T>(value);
rear.next=va;
rear=va;
}
public T deQueue() throws Exception// 出队
{
if (isempty())
throw new Exception("已空");
else {
T va=(T) front.next.data;
front.next=front.next.next;
return va;
}
}
public String toString()
{
node team=front.next;
String va="队头: ";
while(team!=null)
{
va+=team.data+" ";
team=team.next;
}
return va;
}
}
我一般采用java中的封装好的函数来进行:
import java.util.LinkedList;
import java.util.Queue;
public class Queue_test {
public static void main(String[] args) {
//创建一个队列
Queue<Integer> queue = new LinkedList<>();
//在队列中添加元素
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
queue.add(6);
System.out.println(queue);
//获取即将出队的元素
int temp1 = queue.peek();
System.out.println(temp1); //这里的结果是1 因为1是最先进入队列的,所以,先进先出
//删除即将出队的元素
int temp2 = queue.poll();
System.out.println(temp2); //这里的结果是1 因为1是最先进入队列的,所以,先进先出,删除了1
System.out.println(queue); //队列为 6 5 4 3 2
//判断队列是否为空
System.out.println(queue.isEmpty()); // false
//输出队列的长度
System.out.println(queue.size()); // 5
//遍历输出队列
/*
我们在遍历的过程中,最好是使用边删除,边遍历的方法啊,因为删除之后,下一个元素是即将出队的元素,就好遍历出来了
* */
while(!queue.isEmpty()){//当队列不为空,就遍历,为空就终止
int temp = queue.poll();
System.out.println(temp);
} //出来的顺序为 2 3 4 5 6
}
}