算法 RingBuffer
2020-12-13 06:00
标签：div invalid lis array 就是 cee 实现 while return https://en.wikipedia.org/wiki/Circular_buffer microsoft on site面试问到到一个，当时有点紧张，然后用链表实现，最后写的也有些问题，要求的单元测试也没有完成。 两种实现，使用数组或者链表，相对来说不需要随机访问，使用链表会更好，实现上链表也更容易些。 接口定义，实际使用应该定义泛型接口 链表实现，定义了一个内部类存储节点 数组实现，如果说不好，可能就是需要分配连续空间，以及最大不能超过数组最大长度 测试，主要的边界情况是max=1，以及增加元素超过时如何处理。 算法 RingBuffer 标签：div invalid lis array 就是 cee 实现 while return 原文地址：https://www.cnblogs.com/lvjianwei/p/11161325.htmlpackage com.ljw.javatest;
// Ringbuffer is a circle, and has a head and tail.
// When add item, add item at tail, if item‘s quantity exceed max,
// then delete the head item.
public interface RingBuffer{
public void addItem(int value);
//return the oldest item
public Integer getItem();
//delege the oldest item
public void deleteItem();
//return item from head to tail
public Integer[] getAll();
}
package com.ljw.javatest;
public class RingBufferWithLinked implements RingBuffer{
class Node{
Integer value;
Node next;
Node(Integer value){
this.value=value;
}
}
private int max;
private int count;
private Node head;
private Node tail;
public RingBufferWithLinked(int max) throws Exception {
if(max){
throw new Exception("invalid max");
}
this.max=max;
this.count=0;
}
@Override
public void addItem(int value) {
if(head==null){
head=new Node(value);
tail=head;
count++;
return;
}
Node temp = new Node(value);
tail.next = temp;
tail = temp;
if (count max) {
count++;
return;
}
head=head.next;
}
@Override
public Integer getItem() {
if(head!=null){
return head.value;
}
return null;
}
@Override
public void deleteItem() {
if(head==null){
return;
}
head=head.next;
count--;
if(count==0){
head=tail=null;
}
}
@Override
public Integer[] getAll() {
if(head==null){
return null;
}
Integer[] result=new Integer[count];
int i=0;
Node temp=head;
while(temp!=null){
result[i++]=temp.value;
temp=temp.next;
}
return result;
}
}
package com.ljw.javatest;
import java.util.List;
public class RingBufferWithArray implements RingBuffer {
public static void main(String[] args) {
}
Integer[] buffer;
int head;
int tail;
int max;
int count;
public RingBufferWithArray(int max) throws Exception {
if (max ) {
throw new Exception("invalid max");
}
buffer = new Integer[max];
this.max = max;
count = 0;
head = -1;
tail = -1;
}
@Override
public void addItem(int value) {
if (count + 1 > max) {
buffer[head] = value;
tail = head;
if (head == max - 1) {
head = 0;
} else {
head++;
}
} else {
count++;
if (count == 1) {
head=tail=0;
buffer[head]=value;
}
else {
if (tail == max - 1) {
tail = 0;
buffer[tail] = value;
} else {
buffer[++tail] = value;
}
}
}
}
@Override
public Integer getItem() {
if (head == -1) {
return null;
} else {
return buffer[head];
}
}
@Override
public void deleteItem() {
if (count == 0) {
return;
}
buffer[head] = null;
count--;
if (count == 0) {
head = tail = -1;
}
if (head++ == max) {
head = 0;
}
}
@Override
public Integer[] getAll() {
if (head == -1) {
return null;
}
Integer[] result = new Integer[count];
for (int i = 0, temp = head; i ) {
if (temp == max) {
temp = 0;
}
result[i] = buffer[temp];
}
return result;
}
}
package com.ljw.javatest;
public class App {
public static void main(String[] args) throws Exception {
int max=3;//max=1;
RingBuffer rb=new RingBufferWithLinked(max);
rb.addItem(1);
print(rb.getItem()==1);
rb.deleteItem();
print(rb.getItem()==null);
int add=2;
for(int i=0;i