循环队列的Java实现

  与栈一样，队列也是最基本的数据结构之一。队列也是对象的一种容器，其中对象的插入和删除遵循“先进先出”（First-In-First-Out, FIFO）的原则⎯⎯也就是说，每次删除的只能是最先插入的对象。因此，我们可以想象成将对象追加在队列的后端，而从其前端摘除对象。为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。下面将用两种方式实现循环队列。

Queue接口

package com.queue;

public interface Queue {

    public int getSize();//获得队列中元素的数目
    
    public boolean isEmpty();//判断队列是否为空
    
    public Object front();//取出队列的头元素
    
    public void enqueue(Object elem);//入队
    
    public Object dequeue();//出队
    
    public void Traversal();//遍历
}

基于数组的实现

package com.queue;

public class MyQueue implements Queue{
    public static final int CAPACITY = 1000;//数组的默认长度
    public int capacity;//数组的实际长度
    public Object[] q;//对象数组
    public int front = 0;//队首元素的位置
    public int rear = 0;//队尾元素的位置
    
    public MyQueue()
    {
        this(CAPACITY);
    }
    
    public MyQueue(int cap)
    {
        capacity = cap;
        q = new Object[capacity];
    }
    
    @Override
    public int getSize() {
        
        return (capacity-front+rear) % capacity;
    }

    @Override
    public boolean isEmpty() {
        
        return (front == rear);
    }

    @Override
    public Object front() {
        if(isEmpty())
        {
            System.out.println("队为空");
            return null;
        }
        return q[front];
    }

    @Override
    public void enqueue(Object elem) {
        if(getSize() == capacity-1)
        {
            System.out.println("队满");
            return;
        }
        q[rear] = elem;
        rear = (rear +1)%capacity;
        
    }

    @Override
    public Object dequeue() {
        if(isEmpty())
        {
            System.out.println("队为空");
            return null;
        }
        
        Object elem = q[front];
        q[front]=null;
        front = (front + 1)%capacity;
        return elem;
    }

    @Override
    public void Traversal() {
        if(isEmpty())
        {
            System.out.println("队为空");
            return;
        }
        int f = front;
        int r = rear;
        while(rear != (front+1)%capacity)
        {
            System.out.print(q[front++] + " ");
        }
        System.out.println();
    }

}

基于链表的实现

  单链表的节点

package com.node;

public class Node {

    private Object elem;
    private Node next;
    
    public Node()
    {
        this(null,null);
    }
    
    public Node(Object e,Node n)
    {
        elem = e;
        next = n;
    }
    
    public Object getElem() {       
        return elem;
    }

    public void setElem(Object elem) {
        this.elem = elem;
    }
    
    public Node getNext()
    {
        return this.next;
    }
    
    public void setNext(Node next)
    {
        this.next = next;
    }

}

  循环队列的实现

package com.queue;

import com.node.Node;

public class Queue_list implements Queue{

    protected Node head;
    protected Node tail;
    protected int size;
    
    public Queue_list()
    {
        head = tail = null;
        size=0;
    }
    
    
    @Override
    public int getSize() {
        
        return size;
    }

    @Override
    public boolean isEmpty() {
        
        return (size == 0)? true:false;
    }

    @Override
    public Object front() {
        if(isEmpty())
        {
            System.out.println("栈为空");
            return null;
        }
    
        return head.getElem();
    }

    @Override
    public void enqueue(Object elem) {
        Node newNode = new Node(elem,null);
        if(isEmpty())
        {
            head = newNode;
        }
        else
        {
            tail.setNext(newNode);
        }
        tail = newNode;
        size++;
    }

    @Override
    public Object dequeue() {
        if(isEmpty())
        {
            System.out.println("栈为空");
            return null;
        }
        
        Object elem = head.getElem();
        head = head.getNext();
        size--;
        //如果队列已空，将队尾指针置空
        if(0 == size)
        {
            tail = null;
        }
        return elem;
    }

    @Override
    public void Traversal() {
        Node p = head;
        while (null != p) {
        System.out.print(p.getElem()+" ");
        p = p.getNext();
        }
        System.out.println();
    }

}