数据结构队列的java实现,包括线性和链式两种方式

实现的思路为:

采用泛型的方式,首先定义了一个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;
} }

随着复习进度,后续代码会陆续更新。

上一篇:jenkins了解一下,讲一下jenkins这个鬼东西


下一篇:利用对象思想来绘制canvas帧动画