数据结构之队列及Java实现

朴灿烈づ我的快乐病毒、 2022-05-27 11:23 195阅读 0赞

## 一、队列的基本介绍 ##

队列也是一种特殊的线性表，特点是先进先出，只能在表的一端进行插入，在另一端进行删除。向队列中插入元素的过程称为入队(Enqueue)，删除元素的过程称为出队(Dequeue)，并把允许入队的一端称为队尾，允许出的的一端称为队头，没有任何元素的队列则称为空队。其一般结构如下所示：  
![70][]

## 二、队列的Java实现 ##

与栈的实现相似，队列也有两种实现方式，分别基于数组和基于链表。由于队列是被限制的线性表，所以不能提供线性表中的方法如：获取指定索引处的元素、查找元素的位置、向指定索引处插入元素、删除索引处的元素等。  
队列的常用操作如下所示：

*  初始化：创建空队列
 *  获取队列的长度：返回队列元素的个数
 *  加入元素：向队列的rear端插入元素
 *  删除元素：在队列的front端删除元素
 *  判断队列是否为空：已空返回true，否则返回false

下面分别介绍两种方式的实现：  
1.基于数组的队列

public class ArrayQueue<T> {
        private int MaxSize;
        private T data[];
        private int front;
        private int rear;
        //构造函数初始化
        public ArrayQueue(int size){
            MaxSize = size;
            data = (T[]) new Object[MaxSize];
            front = 0;
            rear = 0;
        }
        //添加元素，加到队尾
        public boolean add(T value){
            if(value == null){
                return false;
            }
            if(rear > MaxSize -1){
                return false;
            }
            data[rear] = value;
            rear++;
            return true;
        }
        //队列长度
        public int length(){
            return rear-front;
        }
        //判断是否为空
        public boolean isEmpty(){
            if(length() == 0){
                return true;
            }
            return false;
        }
        //删除元素，删除队头节点
        public T del(){
            T tmp = null;
            if(isEmpty()){
                return tmp;
            }
            tmp = data[front];
            data[front] = null;
            front++;
            return tmp;
        }
        //队列元素遍历
        public String toString(){
            String str = "";
            for(int i=front;i<rear;i++){
                str = str + data[i] + " ";
            }
            return str;
        }
        public static void main(String args[]){
            ArrayQueue<String> aq = new ArrayQueue<String>(3);
            //添加元素测试
            aq.add("qwer");
            aq.add("asdf");
            aq.add("zxcv");
            //队列已满测试
            System.out.println(aq.add("uiop"));
            System.out.println(aq.toString());
            //队列删除测试
            aq.del();
            System.out.println(aq.toString());
            aq.del();
            System.out.println(aq.toString());
        }
    
    
    }

测试结果：

false
    qwer asdf zxcv 
    asdf zxcv 
    zxcv

2.基于链表的队列

public class NodeQueue<T> {
        class Node<T>{
            Node<T> next = null;
            T data = null;
            public Node(T value){
                this.data = value;
            }
        }
        Node<T> front = null;
        Node<T> rear = null;
        public NodeQueue(){
            front = null;
            rear = null;
        }
        //添加节点到队尾，如果队列为空头结点和尾节点都只向新节点
        public void add(T value){
            if(value == null){
                return;
            }
            if(front == null){
                front = new Node<T>(value);
                rear = front;
            }
            else{
                Node<T> n = new Node<T>(value);
                rear.next = n;
                rear = n;
            }
        }
        //返回队列的长度
        public int length(){
            if(front == null){
                return 0;
            }
            int num = 1;
            Node<T> cur = front;
            while(cur.next!=null){
                num++;
                cur = cur.next;
            }
            return num;
        }
        //删除节点，将队头的节点删除
        public boolean del(){
            if(length()==0){
                return false;
            }
            Node n = front.next;
            front = n;
            return true;
        }
        //打印队列内容
        public String toString(){
            String str = "";
            Node<T> cur; 
            for(cur = front;cur!=null;cur=cur.next){
                str = str + cur.data + " ";
            }
            return str;
        }
        public static void main(String args[]){
            NodeQueue<String> nq = new NodeQueue<String>();
            //添加节点测试
            System.out.println(nq.length());
            nq.add("qwer");
            nq.add("asdf");
            nq.add("zxcv");
            System.out.println(nq.toString());
            System.out.println(nq.length());
            //删除节点测试
            nq.del();
            System.out.println(nq.toString());
            System.out.println(nq.length());
        }
    
    
    }

测试结果：

0
    qwer asdf zxcv 
    3
    asdf zxcv 
    2

[70]: /images/20220527/d5b6492dec294a2e83162b831f3ec2f8.png