一.代码部分
1.定义接口：
public interface Queue<E> {
void enqueue(E e);
E dequeue();
E getFront();
int getSize();
boolean isEmpty();
}
2.基于数组的实现
public class ArrayQueue<E> implements Queue<E> {
private ArrayList<E> arrayList;
public ArrayQueue(int capacity){
arrayList = new ArrayList<>(capacity);
}
public ArrayQueue(){
arrayList = new ArrayList<>();
}
@Override
public void enqueue(E e) {
arrayList.addLast(e);
}
@Override
public E dequeue() {
return arrayList.removeFirst();
}
@Override
public E getFront() {
return arrayList.get(0);
}
@Override
public int getSize() {
return arrayList.getSize();
}
@Override
public boolean isEmpty() {
return arrayList.isEmpty();
}
}
3.改进链表实现队列：
public class LinkedListQueue<E> implements Queue<E> {
//节点,用来存放数据：数据+下一个元素的引用
private class Node{
private E e;
private Node next;
public Node(E e,Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
public String toString(){
return e.toString();
}
}
private Node head;//头节点
private Node tail;//尾节点
private int size;
public LinkedListQueue(){
head = null;
tail = null;
size =0;
}
@Override
public void enqueue(E e) {
if (tail == null){
tail = new Node(e);
head = tail;
}else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
@Override
public E dequeue() {
if(isEmpty())
throw new IllegalArgumentException("empty");
Node retNode = head;
head = head.next;
retNode.next = null;
if (head == null){
tail = null;
}
size--;
return retNode.e;
}
@Override
public E getFront() {
if(isEmpty())
throw new IllegalArgumentException("empty");
return head.e;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size ==0;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("queue:front");
Node cur = head;
while (cur != null){
res.append(cur + "->");
cur = cur.next;
}
res.append("null tail");
return res.toString();
}
}
3.循环队列：
public class LoopQueue<E> {
private E[] data;
private int front;//队列头
private int tail;//队列尾
private int size;
/**
* 初始化容量的构造方法
* @param capacity
*/
public LoopQueue(int capacity){
data = (E[]) new Object[capacity+1]; //注意加一
front = 0;
tail = 0;
size = 0;
}
/**
* 无参的构造方法
*/
public LoopQueue(){
this(10);
}
public int getCapacity(){
return data.length-1;
}
public boolean isEmpty(){
return front == tail;
}
public int getSize(){
return size;
}
/**
* 改变数组容量
* @param newCapacity
*/
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity+1];
for (int i = 0; i < size; i++) {
newData[i] = data[(i+front)%data.length];
}
data = newData;
front = 0;
tail = size;
}
/**
* 入队
* @param e
*/
public void enqueue(E e){
if ((tail+1)%data.length == front){
resize(getCapacity()*2);
}
data[tail] = e;
tail = (tail+1)%data.length;//注意这里不是tail++
size++;
}
/**
* 出队
* @return
*/
public E dequeue(){
if (isEmpty()){
throw new IllegalArgumentException("can't dequeue");
}
E ret = data[front];
data[front] = null;
front = (front+1)%data.length;//注意这里不是front++
size--;
if(size == getCapacity()/4 && getCapacity()/2 != 0){
resize(getCapacity()/2);
}
return ret;
}
/**
* 队列头
* @return
*/
public E getFront(){
if (isEmpty()){
throw new IllegalArgumentException("queue is empty");
}
return data[front];
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("queue size =%d, capacity = %d\n"),size,getCapacity());
res.append("front [");
for (int i = front; i != tail; i = (i=1)%data.length) {
res.append(data[i]);
if((i+1)%data.length != tail){
res.append(",");
}
}
res.append("] tail");
return res.toString();
}
}