数据结构-线性结构之队列

什么是队列？

队列是一种具有一定约束条件的线性表。是一种常用的数据结构。基本思想是：先进先出即最先被接收的对象，最先被处理。所以又叫先进先出表（FIFO）。

例子： 队列的例子生活中有很多，比如：买火车票排队,排头最先买到车票,新来的排在队尾；进车站时安检先进去的最先出来，后进去的后出来。

---

队列的抽象数据类型描述：

类型名称： 队列（Queue）
数据对象集： 一个有0个或多个元素的有穷线性表。
操作集： 长度为MaxSize的队列Q∈Queue, 队列元素item∈ElementType;

• Queue CreatQueue(int MaxSize); 生成长度为MaxSize的空队列;
• int FullQ(Queuq Q,int MaxSize); 生成的队列Q是否为满。
• void AddQ(Queue Q,ElementType item); 将数据元素插入队列Q中
• int isEmptyQ(Queue q)； 判断队列是否为空。
• ElementType DeleteQ(Queue Q); 将队头数据元素从队列中删除并返回。

---

队列的顺序表实现（循环数组实现）：

package com.simon.datastructure.javadatastructure;

/**
 * auther: Simon zhang
 * Emaill:[email protected]
 *  队列 - 顺序表的实现
 */
public class ArrayQueue<E>{
    /**
     * 用于存储队列元素的数组
     */
    Object[] elements;
    /**
     * 用于表示队列头部元素的下表
     */
    int first;
    /**
     * 用于表示队列尾部元素的下表
     */
    int last;
    /**
     * 用于表示队列的容量
     */
    int maxSize;
    /**
     * 用于表示队列中元素的数量
     */
    int size;
    /**
     * 生成长度为MaxSize的空队列;
     * @param maxSize
     */
    public ArrayQueue(int maxSize) {
        if(maxSize<0){
            throw  new IllegalArgumentException("stack size must more than zero..");
        }
        this.last=first=0;
        this.maxSize=maxSize;
        this.elements=new Object[maxSize];
    }

    /**
     *  生成的队列Q是否为满。
     */
    public boolean isFull() {
        return size==maxSize;
    }

    /**
     * 将数据元素插入队列Q中。
     * @param e
     */
    public void push(E e){
        if(isFull()){
            System.out.println("Queue is full now..");
        }else{
            elements[last]=e;
            last=(last+1)%maxSize;
            size++;
        }
    }

    /**
     * 将队头数据元素从队列中删除并返回。
     */
    public E pop(){
        //优化，循环数组实现
        if(isEmpty()){
            System.out.println("Queue is empty now..");
            return null;
        }else{
            E popE=(E)elements[first];
            elements[first]=null;
            first=(first+1)%maxSize;
            size--;
            return popE;
        }
    }

    /**
     * 判断队列是否为空。
     */
    public boolean isEmpty(){
         return size==0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if(first<last){
            for (int i = first; i <last; i++) {
                sb.append(elements[i].toString());
                if(i!=last-1){
                    sb.append(',');
                }
            }
        }else if(last<first){
            for (int i = first; i <maxSize; i++) {
                 sb.append(elements[i].toString());
                 if(i!=maxSize-1){
                     sb.append(',');
                 }
            }
            for (int i = 0; i <last; i++) {
                sb.append(',');
                sb.append(elements[i].toString());
            }
        }
        sb.append(']').toString();
        return  sb.toString();
    }
}

队列的链表实现：

package com.simon.datastructure.javadatastructure;

/**
 * auther: Simon zhang
 * Emaill:[email protected]
 * 链表实现 队列
 */
public class LinkedQueue<E> {
    /**
     * 用于表示队列头部的元素
     */
    Node header;
    /**
     * 用于表示队列尾部的元素
     */
    Node last;
    /**
     * 用于表示队列的容量
     */
    int maxSize;
    /**
     * 当前队列数量
     */
    int size;

    /**
     * 生成长度为MaxSize的空队列;
     * @param maxSize
     */
    public LinkedQueue(int maxSize) {
        if(maxSize<0){
            throw  new IllegalArgumentException("stack size must more than zero..");
        }
        this.maxSize=maxSize;
    }

    /**
     *  生成的队列Q是否为满。
     */
    public boolean isFull() {
        return size==maxSize;
    }

    /**
     * 将数据元素插入队列Q中。
     * @param e
     */
    public void push(E e){
        if(isFull()){
            System.out.println("Queue is full now..");
        }else{
            Node insertNode=new Node(e);
            if(header==null){
                header=insertNode;
                last=insertNode;
            }else{
                last.addNext(insertNode);
                last=insertNode;
            }
            size++;
        }
    }

    /**
     * 将队头数据元素从队列中删除并返回。
     */
    public E pop(){
        if(isEmpty()){
            System.out.println("Queue is empty now..");
            return null;
        }else{
            E popE=(E)header.item;
            header=header.next;
            size--;
            return popE;
        }
    }

    /**
     * 判断队列是否为空。
     */
    public boolean isEmpty(){
        return size==0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        Node temp=header;
        while (temp.next!=null){
            sb.append(temp.item.toString());
            sb.append(',');
            temp=temp.next;
        }
        sb.append(temp.item.toString());
        sb.append(']').toString();
        return  sb.toString();
    }


    class Node<E>{
        E item;
        Node next;
        public Node(E item) {
            this.item = item;
        }

        public void addNext(Node next) {
            this.next = next;
        }
    }
}

---

队列总结：
1. 队列实现起来还是挺简单的，比起其他数据结构而言。就是用循环数组实现队列的时候判满条件有点小坑，不得以用了一个Size变量去记录队列中的元素个数进行判满。 还是就是循环链表实现的队列在toString输出元素的时候，现在写的好繁琐呀。感觉好傻！！必须优化之…..
2. 使用链表实现的这个队列自我感觉还是写的有点小帅，哈哈。自我陶醉一下….