https://leetcode.com/discuss/interview-question/156969/Implement-Queue-using-fixed-size-array/
TODO:
http://fabian-kostadinov.github.io/2014/11/25/implementing-a-fixed-length-fifo-queue-in-java/
Assumption: The arrays hold 5 elements, each of which is the size of a pointer.
Our first level of abstraction is to use our stupid arrays to make a less stupid array, which has access in log(N) time.
Once we have an Array, with all of the capabilities of your typical array, implementing a queue, stack, deque, whatever, will be the normal way of doing so.
Our first level of abstraction is to use our stupid arrays to make a less stupid array, which has access in log(N) time.
Once we have an Array, with all of the capabilities of your typical array, implementing a queue, stack, deque, whatever, will be the normal way of doing so.
class Array {
Array(int size) {
this->size = size;
depth = max(0, log5(size)-1); // Depth 0 is for size <= 5
build_array(depth, head);
}
// Will hold 5^depth elements, which is likely greater than size, but you know
// what they say about premature optimization
void build_array(int depth, stupid_array arr) {
if (depth == 0) return;
for i = 0 to 4 {
arr[i] = new stupid_array;
build_array(depth-1, arr[i]);
}
}
(stupid_array, int) find_index(int idx)
{
return find_index(0, idx, head);
}
(stupid_array, int) find_index(int d, int idx, stupid_array arr)
{
int net_depth = depth - d;
int subarray_size = pow(5, net_depth-1);
if (subarray_size == 1) {
return (head, idx);
}
return find_index(d+1, idx % subarray_size, arr[idx / subarray_size]);
}
insert(void * value, int idx) {
stupid_array subarr;
int subidx;
(subarr, subidx) = find_index(idx);
subarr[subidx] = value;
}
void * get(int idx) {
stupid_array subarr;
int subidx;
(subarr, subidx) = find_index(idx);
return subarr[subidx];
}
stupid_array head;
int size, depth;
}
Now that we have an array that has a normal interface, and which has reasonably fast access of
https://github.com/allaboutjst/airbnbO(log(N)), we can easily create a queue
Implement a queue with a number of arrays, in which each array has fixed size.
2.Implement Queue with limited size of array: 使用double linkedlist
2. Implement Queue with limited size of array：方法二 ListNode with fixed size of array
public class QueueWithFixedArray {
private int fixedSize;
private int count;
private int head;
private int tail;
private List<Object> headList;
private List<Object> tailList;
public QueueWithFixedArray(int fixedSize) {
this.fixedSize = fixedSize;
this.count = 0;
this.head = 0;
this.tail = 0;
this.headList = new ArrayList<>();
this.tailList = this.headList;
}
public void offer(int num) {
if (tail == fixedSize - 1) {
List<Object> newList = new ArrayList<>();
newList.add(num);
tailList.add(newList);
tailList = (List<Object>) tailList.get(tail);
tail = 0;
} else {
tailList.add(num);
}
count++;
tail++;
}
public Integer poll() {
if (count == 0) {
return null;
}
int num = (int) headList.get(head);
head++;
count--;
if (head == fixedSize - 1) {
List<Object> newList = (List<Object>) headList.get(head);
headList.clear();
headList = newList;
head = 0;
}
return num;
}
public int size() {
return count;
}
}
TODO:
http://fabian-kostadinov.github.io/2014/11/25/implementing-a-fixed-length-fifo-queue-in-java/
