数据结构 队列以及Java代码实现

1. 队列

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

• 队尾(rear)——允许插入的一端
• 队头(front)——允许删除的一端

队列特点：先进先出(FIFO)

结构模型：

2.顺序循环队列

/**
 * Queue
 * 队列的基本操作
 * （1）清空队列
 * （2）判断是否为空
 * （3）元素的个数
 * （4）入队列
 * （5）出队列
 * （6）取对头元素
 * Created by heqianqian on 2017/7/14.
 */
public interface Queue<T> {

/**
 * 判断是否为空
 */
    boolean isEmpty();

/**
 * 入队列
 */
    void enQueue(T obj);

/**
 * 出队列
 */
    T deQueue();


/**
 * 取队头元素
 */
    T peek();

/**
 * 元素的个数
 */
    int size();


/**
 * 清空队列
 */
    void clear();
}

/**
 * ArrayQueue
 * 顺序循环队列
 * Created by heqianqian on 2017/7/14.
 */
public class ArrayQueue<T> implements Queue<T> {

private static final int DEFAULT_SIZE = 10;

private T[] queue;

private int front, rear;

private int size;

    @SuppressWarnings("unchecked")
public ArrayQueue() {
        front = rear = size = 0;
        queue = (T[]) new Object[DEFAULT_SIZE];
    }

    @Override
public boolean isEmpty() {
return size == 0;
    }

    @Override
public void enQueue(T obj) {
if ((rear == front) && (size > 0)) {//队列已满
            expand();
        }
//队尾插入元素
        queue[rear] = obj;
        rear = (rear + 1) % DEFAULT_SIZE;
        size++;
    }

/**
 * 扩容
 */
    @SuppressWarnings("unchecked")
private void expand() {
        T[] arr = (T[]) new Object[DEFAULT_SIZE * 2];
        System.arraycopy(queue, 0, arr, 0, size);
    }

    @Override
public T deQueue() {
if ((rear == front) && (size == 0)) {//队列为空
return null;
        }
//队头取元素
        T result = queue[front];
        front = (front + 1) % DEFAULT_SIZE;
        size--;
return result;
    }

    @Override
public T peek() {
return queue[front];
    }

    @Override
public int size() {
return size;
    }

    @Override
public void clear() {
        front = rear = size = 0;
    }

    @Override
public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
for (int i = 0; i < size - 1; i++) {
            sb.append(queue[i]).append(",");
        }
        sb.append(queue[size - 1]).append("]");
return sb.toString();
    }
}

3.链式队列

/**
 * Node
 * 链式队列的节点
 * Created by heqianqian on 2017/7/14.
 */
public class Node<T> {

public Node next;
public T data;

public Node(T data) {
this.data = data;
        next = null;
    }

    @Override
public String toString() {
return data.toString();
    }
}

/**
 * LinkedQueue
 * 链式循环队列
 * Created by heqianqian on 2017/7/14.
 */
public class LinkedQueue<T> implements Queue<T> {

private Node<T> front, rear;

private int size;

    @SuppressWarnings("unchecked")
public LinkedQueue() {
        front = rear = new Node(null);
        size = 0;
    }

    @Override
public boolean isEmpty() {
return size == 0;
    }

    @Override
public void enQueue(T obj) {
        Node<T> node = new Node<T>(obj);
//队尾插入
        rear.next = node;
        rear = node;
        size++;
    }

    @Override
    @SuppressWarnings("unchecked")
public T deQueue() {
//队头出队
if (size <= 0) {
return null;
        }
        T data = (T) front.next.data;
        front = front.next;
        size--;
return data;
    }

    @Override
public T peek() {
return (T) front.next.data;
    }

    @Override
public int size() {
return size;
    }

    @Override
public void clear() {
        size = 0;
        front = rear;
    }

    @Override
public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node<T> temp = front.next;
while (temp != rear) {
            sb.append(temp.data.toString()).append(",");
            temp = temp.next;
        }
        sb.append(temp.data).append("]");
return sb.toString();
    }
}