实现的思路为：
采用泛型的方式，首先定义了一个Queue的接口，然后通过实现该接口实现了线性和链式的两种形式的队列：
接口代码如下：
package com.peter.java.dsa.interfaces;
public interface Queue<T> {
/* put item at rear of queue; */
void insert(T data);
/* take item from front of queue */
T remove();
/* peek at front of queue */
T peek();
boolean isEmpty();
boolean isFull();
int size();
void clear();
}
线性栈的代码如下：
package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.Queue;
public class LinearQueue<T> implements Queue<T> {
private int capacity;
private T[] t;
private int front;
private int rear;
private int size;
public LinearQueue() {
// TODO Auto-generated constructor stub
capacity = 16;
t = (T[]) new Object[capacity];
front = -1;
rear = -1;
size = 0;
}
public LinearQueue(int capacity) {
this.capacity = capacity;
t = (T[]) new Object[capacity];
front = -1;
rear = -1;
size = 0;
}
@Override
public void insert(T data) {
// TODO Auto-generated method stub
if (isEmpty()) {
front = (front + 1) % t.length;
t[front] = data;
rear = (rear + 1) % t.length;
} else {
if (isFull()) {
resize();
}
rear = (rear + 1) % t.length;
t[rear] = data;
}
size++;
}
@Override
public T remove() {
// TODO Auto-generated method stub
T tmp = null;
if (!isEmpty()) {
tmp = t[front];
t[front] = null;
front = (front + 1) % t.length;
size--;
}
return tmp;
}
@Override
public T peek() {
// TODO Auto-generated method stub
T tmp = null;
if (!isEmpty()) {
tmp = t[front];
}
return tmp;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return front + rear == -2 && front == rear % t.length;
}
@Override
public boolean isFull() {
// TODO Auto-generated method stub
return front == rear % t.length;
}
@Override
public int size() {
// TODO Auto-generated method stub
return size;
}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuffer buffer = new StringBuffer();
buffer.append("Linear Queue Content:[");
if (front < rear) {
for (int i = front; i < rear + 1; i++) {
buffer.append(t[i] + ",");
}
} else {
for (int i = front; i < t.length; i++) {
buffer.append(t[i] + ",");
}
for (int i = 0; i < rear + 1; i++) {
buffer.append(t[i] + ",");
}
}
buffer.append("]");
buffer.replace(buffer.lastIndexOf(","), buffer.lastIndexOf(",") + 1, "");
return buffer.toString();
}
private void resize() {
int oldSize = t.length;
T[] tmp = (T[]) new Object[oldSize * 2];
for (int i = 0; i < oldSize; i++) {
tmp[i] = t[front];
front = (front + 1) % oldSize;
}
front = 0;
rear = oldSize - 1;
}
@Override
public void clear() {
// TODO Auto-generated method stub
front = -1;
rear = -1;
}
}
随着复习进度，后续代码会陆续更新。